_Rb_tree + allocator observations

[Matt Austern]

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