Balanced trees

Dan Stromberg drsalists at
Tue Mar 18 20:26:09 CET 2014

On Mon, Mar 17, 2014 at 3:05 PM, Marko Rauhamaa <marko at> wrote:
> Joshua Landau <joshua at>:
>> The thing we really need is for the blist containers to become stdlib
>> (but not to replace the current list implementation).
> Very interesting. Downloaded blist but didn't compile it yet. It *could*
> be the missing link.
> I would *love* to see some comparative performance results between
> blist.sorteddict and an AVL tree.

I added blist.sorteddict and removed (temporarily) Pypy and Jython.
The results are at

In short, blist.sorteddict didn't do that well, despite being in C.
In the random workloads, blist.sorteddict was dead last.  In the
sequential workloads blist.sorteddict fell somewhere in the middle.

I excluded Pypy and Jython because blist.sorteddict probably doesn't
run on them.


More information about the Python-list mailing list