<br><br><div class="gmail_quote">Le 7 avril 2012 16:56, Dave Abrahams <span dir="ltr"><<a href="mailto:dave@boostpro.com">dave@boostpro.com</a>></span> a écrit :<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="HOEnZb"><div class="h5"><br>
on Sat Apr 07 2012, David Chisnall <<a href="http://csdavec-AT-swan.ac.uk" target="_blank">csdavec-AT-swan.ac.uk</a>> wrote:<br>
<br>
> On 7 Apr 2012, at 14:28, Matthieu Monrocq wrote:<br>
><br>
>> If we are speaking alternative implementations of std::map and co,<br>
>> does anyone know if a Skip List has ever been used to implement<br>
>> those ? They are in theory equivalent to red-black trees and avl<br>
>> trees, but use randomness instead of rebalancing which make them<br>
>> *much* simpler: you don't need a book to code them.<br>
><br>
> Skip lists, in general, have very poor cache utilisation which affects<br>
> their performance in real code but doesn't always show up in<br>
> microbenchmarks.  We based a lot of code around skip lists when they<br>
> were cool in the '90s and would now suffering for it if not for the<br>
> fact that computers became so fast in the intervening period that we<br>
> could strip out those caches completely and still be fast enough.<br>
<br>
</div></div>Speaking of cache utilization, it's hard to beat btrees.  I don't know<br>
if you can implement the requirements of std::map with btrees, though:<br>
<br>
<a href="https://github.com/boostcon/2011_presentations/raw/master/tue/proposed_b_tree_library.pdf" target="_blank">https://github.com/boostcon/2011_presentations/raw/master/tue/proposed_b_tree_library.pdf</a><br>
<a href="http://blip.tv/boostcon/the-proposed-boost-b-tree-library-5349968" target="_blank">http://blip.tv/boostcon/the-proposed-boost-b-tree-library-5349968</a><br>
<br>
OK, re-lurking...<br>
<div class="HOEnZb"><div class="h5"><br>
--<br>
Dave Abrahams<br>
BoostPro Computing<br>
<a href="http://www.boostpro.com" target="_blank">http://www.boostpro.com</a><br>
</div></div></blockquote></div><br>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).<br>
<br>To get better caching I only know of specializing the allocator at the moment, so that all objects get allocated close to each other.<br><br>-- Matthieu<br>