schmidt@crimee.ics.uci.edu (Doug Schmidt) (06/12/90)
Every so often the issue of `assignment to this' is raised on
comp.lang.c++. Up until recently I've not had a reason to use this
technique, but recently I've been writing a C++ version of William
Pugh's `skip list' abstract data type and by using `assignment to
this' I was able to speed up my program by about 27%.
There are two basic ways to declare and allocate skip list Nodes,
one way uses explicit assignment to the this pointer:
----------------------------------------
// version 1
class Node
{
private:
KEY_TYPE key;
VALUE_TYPE value;
Node *forward[1]; /* variable sized array of forward pointers */
public:
Node (int level = 0, KEY_TYPE k = 0, VALUE_TYPE v = 0)
{
int size = sizeof *this + sizeof (*this->forward) * level;
this = (Node *) new char[size];
this->key = k;
this->value = v;
}
};
----------------------------------------
The other way requires an additional call to operator new (all uses of
class Node in my program occur off the freestore, so there are
actually two calls of operator new for each dynamic allocation of a
Node):
----------------------------------------
// version 2
class Node
{
private:
KEY_TYPE key;
VALUE_TYPE value;
Node **forward; /* dynamically allocated array of forward pointers */
public:
Node (int level = 0, KEY_TYPE k = 0, VALUE_TYPE v = 0)
: key (k), value (v), forward (new Node *[level + 1]) {}
};
----------------------------------------
Sooo, my question is:
Assuming that `assignment to this' becomes an obsolete, deprecated,
non-supported feature in future releases of C++/cfront, what language
features are available to provide the same degree of efficiency
and elegance as `assignment to this' for examples like the one I
describe above?
Note that overloading class-specific operator new does not appear to
help matters much, since there is not a clean way of passing the
number of *levels* to operator new (obviously a global variable or
public static class data member could be used to communicate the
number of levels to Node::operator new , but that seems like even more
of a hack then allowing `assigning to this'.
I would be interested to know of anyone who has either run into this
problem and/or found a clean, concise, and efficient solution.
thanks,
Doug
--
Any man's death diminishes me, | schmidt@ics.uci.edu (ARPA)
Because I am involved in Mankind; | office: (714) 856-4043
And therefore never send to know for whom the bell tolls;
It tolls for thee -- John Donnejimad@microsoft.UUCP (Jim ADCOCK) (06/13/90)
In article <2674265E.26227@paris.ics.uci.edu> schmidt@crimee.ics.uci.edu (Doug Schmidt) writes: .... >class Node >{ >private: > KEY_TYPE key; > VALUE_TYPE value; > Node *forward[1]; /* variable sized array of forward pointers */ > >public: > Node (int level = 0, KEY_TYPE k = 0, VALUE_TYPE v = 0) > { > int size = sizeof *this + sizeof (*this->forward) * level; > > this = (Node *) new char[size]; > this->key = k; > this->value = v; > } >}; .... > Assuming that `assignment to this' becomes an obsolete, deprecated, > non-supported feature in future releases of C++/cfront, what language > features are available to provide the same degree of efficiency > and elegance as `assignment to this' for examples like the one I > describe above? There are actually two non-portable hacks being used in the above program. One is the obsolete "feature" of assigning to this. The other is the never-a feature of flowing a variable length array off the end of a structure [Even though Bjarne mentions this unfortunate hack in his 1986 book, see his comments in "The Annotated C++ Reference" instead.] Both these hacks have been deprecated for several years. Compilers can generate significantly better code if they know that games are not going to be played with "this." Thus compiler writers can choose to support obsolete hacks, or they can choose to generate significantly better code for people who write within the language. I believe most compiler writers will choose to support people who write within the language, not people who write hacks outside of the language. Likewise the hack of flowing off the end of a structure. Compilers can can say: "huh, forward is only one element long, I can access that using my special one word addressing mode." Or one segmented machines: "Oh, that structure is only eight bytes long. Sure I can place it at 1234:FFF0, no problem." Or compilers in debug mode can check to make sure that access is kept within the bounds of a structure. Or hardware can be designed with special fast access and/or bounds checks for known small structures. Or compilers can be designed with different tradeoffs for structures and arrays: 16bit offsets are big enough for structures, 32bit offsets are good for arrays.... Please don't constrain compiler writers by asking for special support for your favorite programming hacks. This only causes everyone's generated code to be worse, so that a few hackers out their can play their games. If you must write non-portable hacks to get the performance you need, use assembly and/or good old pessimizing C compilers.
pkturner@cup.portal.com (Prescott K Turner) (06/14/90)
schmidt@crimee.ics.uci.edu (Doug Schmidt) writes: [example of class with variable-sized component] > Assuming that `assignment to this' becomes an obsolete, deprecated, > non-supported feature in future releases of C++/cfront, what language > features are available to provide the same degree of efficiency > and elegance as `assignment to this' for examples like the one I > describe above? I agree with Jim Adcock that both assignment to 'this' and using the last member of the class as a variable-sized array are hacks to be avoided. Even without hacks, it is possible to be more efficient than the clean second solution you describe, in which the constructor calls 'new' a second time to get separate storage for the variable-sized part. Instead of doing all of the work in the constructor, create a function which returns a pointer to Node. This function can easily call malloc or new to get enough storage for both the class part and the variable-sized array part. This function would pass the location of the array to the constructor, when creating the object with a class-specific operator 'new'. Since this class-specific operator 'new' would just put the object where it was told; only one allocation of dynamic memory would occur. (Note that for maximum portability one must worry about alignment when determining where, within the one chunk of memory, to put the Node and its associated array.) -- Prescott K. Turner, Jr. Language Processors, Inc. 959 Concord St., Framingham, MA 01701 USA (508) 626-0006 x232 UUCP: ...sun!cup.portal.com!pkturner Internet: pkturner@cup.portal.com