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

Paolo Carlini paolo.carlini@oracle.com
Fri May 8 01:18:00 GMT 2009


Hi,
> I'd like some advice about this speedup to iterators for red-black
> trees.  The idea comes from developers of IBM's proprietary C++
> product who implemented it in the C++ library used on AIX.  Their
> users access the functionality with -Dsomething when compiling, but
> it could be done by adding a g++ option that defines the macro, like:
>
> -ffast-set-map-iterators
>
>   This option augments the base class for map<>, set<>, multimap<> and
>   multiset<> template classes to allow faster iterator operations.
>
>   Warning: -ffast-set-map-iterators causes GCC to generate code that
>   is not binary compatible with code generated without the option.
>   All code that operates on the same set or map objects must use the
>   same variant of this option.
>
> The functional changes are all within include/bits/stl_tree.h and have
> no effect on the compilation of src/tree.cc, which doesn't need to
> know the size of the class.  It uglifies the header with code
> protected by #ifdef __GLIBCXX_USE_FAST_SET_MAP_ITERATOR__.
>   
Closer to our normal naming conventions: _GLIBCXX_USE_FAST_SET_MAP_ITERATOR
> Why do this?  Because it speeds up 447.dealII from SPEC CPU2006.  On
> powerpc64-linux, the speedup over our usual peak options is 32% for
> -m32, 26% for -m64.  The two other CPU2006 benchmarks that use set
> and/or map are omnetpp and xalancbmk, which speed up between 1% and
> 1.4%.  Those speedups are based on the the middle result from 3 runs,
> using mainline from a couple of months ago.  I have not yet run
> benchmarks and any other targets.
>   
Benchmarks on x86_64 would be interesting. Maybe Richard can help with
this? That is particularly important because we may want to enable this
code unconditionally when we break the ABI.
> libstdc++ tests compiled with -D__GLIBCXX_USE_FAST_SET_MAP_ITERAOR__
> all pass.  I'm figuring out how to add tests for this option, possibly
> by finding a set of tests that provide good test coverage and
> including them in new tests files that define the macro.
>
> Would a patch like this be acceptable?  What changes might it need
> before formal submission?  Should there be a g++ option to enable it,
> like -ffast-set-map-iterators, or can we tell users to turn it on
> with -D?
>   
In general I think it would be acceptable, in particular considering its
size. I don't think it would be necessary to add a g++ option, a -D
would be ok, as for enabling debug-mode, for example. Documentation
should be also added to the library docs, of course.

Can you provide an informal explanation for the speed up?

Thanks,
Paolo.



More information about the Gcc-patches mailing list