Subj : Re: OO compilers and efficiency
To   : comp.programming
From : websnarf
Date : Sat Jul 23 2005 08:15 pm

Josh Sebastian wrote:
> 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.

Properly swapping the contents of a CBString requires a full swap of
three entries.  A single swap requires the equivalent of three pointer
or word moves.  Since CBStrings are derived from struct tagbstring, and
I haven't added any virtual entries, you *can* in fact swap two
CBStrings as so:

    struct tagbstring tmp = (struct tagbstring) a;
    (struct tagbstring) a = (struct tagbstring) b;
    (struct tagbstring) b = tmp;

But of course, this is the equivalent of a grand total of 9 word moves.
 Remember that in C its just 1.  So I don't quite see how you think its
not 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.

That's because this is really C code in disguise.  You are using the
features of C++ merely as substitutes for exactly what is available to
you in C.  I.e., its kind of hard to call this "OO" unless you call the
original C code "OO" as well.

Remember what the OP said:

>> Does everyone drop into C for critical code?
>>
>> Or am I the only one who worries about this stuff?  Is it a
>> concern or should I kind of push it back into the recesses
>> of my mind and say the wastefulness is part of the tradeoff
>> for programming OO code?

So the key question still outstanding was: does OO cause inefficiencies
in code?  If you manage to transform my example into something isn't OO
and also doesn't have efficiency problems, then I don't know what
you've proven.

> [...] 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).

Thats a silly parathetical.  Whether or not that declaration is on the
stack depends on whether or not its in the scope of a function, not in
the control structure of a loop.

My intention is to compare OO to non-OO and I just picked the two
languages with those two features that I know at least a little about
to illustrate the point.

> [...] 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);

Dude -- this is *exactly* the same as the C code.  You're *literally*
using new and delete as if they were just malloc() and free().  I mean,
you've got void *'s in there -- what the hell is that?  Is this what OO
is all about?

> 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.

I don't think you understand -- my original C code does exactly what
you are doing here already.  Your claim that most C ADTs don't do this
is almost certainly untrue.  At least its untrue of any ADT that I have
ever created in C.

You can't completely avoid any fragmentation of the heap since you have
to create at least one CBString in the inner loop.  CBString's contain
built-in logic that reduces long term heap fragmentation.

> > 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.

Ok, but am I going to find C code in disguise?  I've looked through the
STL sources, and am generally unimpressed.  A trie is a recursive tree
with a certain node layout.  So in C you use a custom allocator that
malloc's memory in big blocks of nodes at a time, and dishes them out
one at a time.  So when you destroy them at the end, you just nail all
the blocks, and invalidate the top-pointer.  What are you going to do
in C++?   My guess is the same thing using C++ syntax instead of C
syntax, then declare victory because you wrote code that is not
reproducible in any other OO language.

So is the answer to the OP's question: you don't write code that is
really C code, but rather, you translate it to C++ equivalents that
behaves exactly like it was C code, so that the compiler can produce
the same result?

-- 
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

.