[cfe-dev] libc++ red-black tree: halving the branches
matthieu.monrocq at gmail.com
Sat Apr 7 10:24:32 PDT 2012
Le 7 avril 2012 16:56, Dave Abrahams <dave at boostpro.com> a écrit :
> on Sat Apr 07 2012, David Chisnall <csdavec-AT-swan.ac.uk> wrote:
> > On 7 Apr 2012, at 14:28, Matthieu Monrocq wrote:
> >> If we are speaking alternative implementations of std::map and co,
> >> does anyone know if a Skip List has ever been used to implement
> >> those ? They are in theory equivalent to red-black trees and avl
> >> trees, but use randomness instead of rebalancing which make them
> >> *much* simpler: you don't need a book to code them.
> > Skip lists, in general, have very poor cache utilisation which affects
> > their performance in real code but doesn't always show up in
> > microbenchmarks. We based a lot of code around skip lists when they
> > were cool in the '90s and would now suffering for it if not for the
> > fact that computers became so fast in the intervening period that we
> > could strip out those caches completely and still be fast enough.
> Speaking of cache utilization, it's hard to beat btrees. I don't know
> if you can implement the requirements of std::map with btrees, though:
> OK, re-lurking...
> Dave Abrahams
> BoostPro Computing
One issue with the B-Tree family is that those are not node based
structures. std::map and al have the property that an object inserted
should be at a fixed place in memory throughout its lifetime which straight
B-Trees do not ensure at all (why with split and fusion of nodes).
To get better caching I only know of specializing the allocator at the
moment, so that all objects get allocated close to each other.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the cfe-dev