Subj : Re: OO compilers and efficiency
To   : comp.programming
From : Josh Sebastian
Date : Sat Jul 23 2005 03:00 am

websnarf@gmail.com wrote:
> sebasttj@gmail.com wrote:
> > websnarf@gmail.com wrote:
> > > Here's a trick I'd like to see "improved C++ code" for (requires
> > > bstrlib, which can be found at http://bstring.sf.net/):
> > >
> > >    /* The C++ way */
> > >    a = CBString ("end");
> > >    for (i=0; i < 100000; i++) {
> > >        a = CBString (&tbstrTable[i%8]) + a;
> > >    }
> >
> > a = CBString("end");
> > for(int i=0; i!=100000; ++i) {
> >   CBString t(&tbstrTable[i%8]);
> >   t += a;
> >   swap(t, a);
> > }
> >
> > And code a swap function for CBString along the lines of the one for
> > the STL containers (ie, O(1) time).
>
> Ok, but you're still losing, since the O(1) here is slower than a
> single pointer assignment.  The point being that the alternate is going
> to be immediately destroyed, and thus doesn't require the precise
> maintenance that C++ semantics will give you.

I'm not sure what your last sentence means, and my only guess is you
don't understand what I meant by an STL-style swap function. Generally,
it is just a pointer swap (if, for example, you're using the pimpl
idiom) or the swap of a few built-in types. Yes, that will take longer
than simply assigning a pointer. No, it doesn't take much longer. If
the code is *really* critical, you opitimize more.

CBString* a = new CBString("end");
for(int i=0; i!=100000; ++i) {
  CBString* t = new CBString(&tbstrTable[i%8]);
  *t += *a;
  delete a;
  a = t;
}

That, of course, looks remarkably similar to your C version. I didn't
bother posting that earlier because I assumed you wanted to keep your
objects on the stack (which sometimes offers a performance advantage,
and definitely offers a maintainability advantage). But it puts us on
the road to something even better:

void* p = operator new(sizeof(CBString));
void* q = operator new(sizeof(CBString));
CBString* a = new (p) CBString("end");
for(...) {
  CBString* t = new (q) CBString(...);
  *t += *a;
  a->~CBstring();
  q = a;
  a = t;
}
operator delete(q);

This contains an additional pointer assignment in the loop, but it
moves *all* memory allocation and deallocation outside the loop. Most C
ADTs don't allow you to do that kind of thing; if you were to benchmark
it, I'd be interested in seeing the results. Plus, you won't end up
with a fragmented heap.

> C++ does not provide for implicit block allocation, and block
> deallocation.  The fact that you can change new and delete, doesn't
> change the languages interaction with these which is "one at a time".

Alexandrescu's _Modern C++ Design_, chapter 4, provides an example of
how to do exactly that. I'm sure there are better references, as that
is a pragmatic rather than theoretical book, but the principles are
there.

Josh

.