[RFC] optional fast iterators for set/map in libstdc++

[Jan Hubicka]

> Paolo Carlini wrote:
> > Paolo Carlini wrote:
> >>> implemented using only 2 bits rather than 16 bytes of overhead (and then
> >>> you can in principle get rid of the parent pointer, and end up actually
> >>> saving memory).
> >> Thanks Paolo. Then I also suggest exploring other ways to implement
> >> the same basic idea.
> > Note that the _Rb_tree_color enum can certainly host the two bits
> > without changing the memory layout of _Rb_tree_node_base. I wonder if we
> > could even implement some of this (not optimally, maybe) without
> > breaking binary compatibility... Paolo, any idea?
> 
> I don't think so, unfortunately.  You can do it without breaking memory
> layout, because there is padding after _M_color, or you can emulate
> bitfields within the enum. but from inspecting stl_tree.h, it looks like
> there is code doing "_M_left != NULL" that is included in every
> instantiation, then no, you'd break binary compatibility.

I was also playing a bit with RB trees on different benchmark.  Getting
rid of EH and marking things pure helped me with some CD-DCE
improvements to get rid of empty foreach style loops I was running into.

While we certainly can't beat iteration using single lookup and I am
quite convinced it is good idea, it might be interesting to bring the
iterator helpers inline (i.e. _Rb_tree_increment/_Rb_tree_decrement
functions so GCC can inline them at least at -O3.)  This should also
bring some benefits and should not be ABI breaking if done curefully.

Honza