This is the mail archive of the
mailing list for the GCC project.
Re: [RFC] optional fast iterators for set/map in libstdc++
- From: Paolo Bonzini <bonzini at gnu dot org>
- To: janis187 at us dot ibm dot com
- Cc: libstdc++ at gcc dot gnu dot org, gcc-patches at gcc dot gnu dot org
- Date: Fri, 08 May 2009 08:08:49 +0200
- Subject: Re: [RFC] optional fast iterators for set/map in libstdc++
- References: <1241744347.6152.26.camel@janis-laptop>
> 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.