<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Fri, Mar 28, 2014 at 2:54 PM, Marko Rauhamaa <span dir="ltr"><<a href="mailto:marko@pacujo.net" target="_blank">marko@pacujo.net</a>></span> wrote:<br>

<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">The blist implementation, which I have taken a quick glance at,<br>

</blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
buys cache locality at the price of block copying; I have no data to<br>
decide if the tradeoff is a good one.<br></blockquote><div><br></div><div>There's actually a compile-time parameter so that you can tune the tradeoff by adjusting how wide each of blist's nodes are. Like most tradeoffs, whether it's good or bad depends on what you're trying to do.  RedBlack trees are very similar to a B-tree with a node-width of 4:</div>

<div><a href="http://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Analogy_to_B-trees_of_order_4">http://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Analogy_to_B-trees_of_order_4</a><br></div><div><br></div><div>blist's sorteddict is written in Python on top of the blist type (which is written in C).  Because of the Python layer, it's slower by a constant factor compared to pure-C implementations in microbenchmarks.<br>

</div></div><div><br></div>-- <br>Daniel Stutzbach
</div></div>