Re: _Rb_tree + allocator observations

[Matt Austern <austern at apple dot com>]

On Nov 12, 2003, at 9:02 AM, Paolo Carlini wrote:

> Chris Lattner wrote:
>
> > I've noticed that libstdc++ goes through a lot of contortions to 
> > support
> > allocators which are "stateless", but it doesn't bother to optimize 
> > lots
> > of other obvious cases.
> >
> > For example, assume an implementation of a custom allocator does not
> > implement _Alloc_traits: the allocator is probably stateless, but it 
> > will
> > still have space allocated for it in the _Rb_tree structure.  Why not
> > derive from the allocator object itself somehow to take advantage of 
> > the
> > empty base class optimization?
> Hi Chris. Just a naive observation: if I merge in my mind some 
> obervations
> Nathan made a few years ago:
>
>    http://www.cantrip.org/emptyopt.html
>
> with this comment from stl_tree.h
>
>    // Base class to encapsulate the differences between old SGI-style
>    // allocators and standard-conforming allocators.  In order to avoid
>    // having an empty base class, we arbitrarily move one of rb_tree's
>    // data members into the base class.
>
> I strongly suspect that, as quite often happens, the root of the 
> problem is
> that some old parts of our STL should be updated to take advantage of 
> the
> features provided by the current g++ (or other modern compilers for 
> that
> matter ;)
>
> Nathan, do you have somehing to add, out of the top of your head?

Dunno if Nathan has something to add, but I do.  I wrote that comment,
and the code it applies to.  I wrote it for reasons that are no longer
relevant.  (I was supporting two versions of the allocator interface,
one of which nobody cares about anymore, and I was supporting the SGI
compiler, which at the time didn't optimize empty base classes.)

It's possible to make *huge* simplifications in that code.  I should
get around to doing that.

			--Matt