[cfe-dev] libc++ red-black tree: halving the branches

[Matthieu Monrocq]

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:
>
>
> https://github.com/boostcon/2011_presentations/raw/master/tue/proposed_b_tree_library.pdf
> http://blip.tv/boostcon/the-proposed-boost-b-tree-library-5349968
>
> OK, re-lurking...
>
> --
> Dave Abrahams
> BoostPro Computing
> http://www.boostpro.com
>

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.

-- Matthieu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20120407/8137e4b6/attachment.html>