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

[Paolo Carlini <paolo dot carlini at oracle dot com>]

Jan Hubicka wrote:
> 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.
>   
Let's experiment with this, but frankly I'm not it's the way to go:
those functions are called only by the various operator++ and operator--
and I suspect a better way to achieve this kind of performance
improvement while avoiding code bloat would be a recoding of the
functions using those operators to not just call the operators
repeatedly in a loop (as the user would do), instead do something a
little lower level. In fact this is a recurring theme for the iterators
of the containers: very often the most efficient way to implement
algorithms involves knowing something about the lower level
implementation of the containers, instead of using the public interface
of the iterators, see, e.g. the optimized way we have now implemented to
fill std::deque, using a special overload of std::fill for
deque::iterator which knows the segmented nature of deque and does *not*
call operator++ on the deque::iterator for each element.

Paolo.