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

[Janis Johnson <janis187 at us dot ibm dot com>]

On Fri, 2009-05-08 at 08:08 +0200, Paolo Bonzini wrote:
> > 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.
> 
> This looks almost like threaded trees (see GNU libavl), which can be
> 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).  I'm not sure about the speed benefits of threaded
> trees, but +33% in the overhead is quite dramatic.

My patch is based on "Speeding up STL Set/Map Usage in C++ Applications"
by Dibyendu Das, Madhavi Valluri, Michael Wong, and Chris Cambly of IBM.
That paper is part of a book and costs money to download, although I can
ask about sending the paper to specific people who ask for it.

The paper describes previous work including use of AVL trees and
B-trees, and discusses the relative merits of various approaches.

Janis