On Sun, Sep 21, 2014 at 2:54 AM, Antoine Pitrou <solipsis@pitrou.net> wrote:
By the way, one should remember the PEP was written years ago. I don't
know how much the blist type has changed

From memory, below are the major changes that were made after the PEP was written.

Functionality:
  • Added sorteddict, sortedlist, sortedset, weaksortedlist, weaksortedset types.
  • Added a btuple type (works like a regular tuple but slices use copy-on-write).
Performance:
  • Added a cache to find the leaf nodes in one step for code that's dominated by __getitem__ operations.
  • When sorting, switch to a O(n) radix sort if all of the keys are C integers or floats.
  • Lots of fine-tuning.
(the author doesn't seem to provide a changelog, unfortunately), but

The changelog is at:
https://github.com/DanielStutzbach/blist/commits/master

according to the following
benchmarks there doesn't seem to be any remaining performance drawback
compared to list:

http://stutzbachenterprises.com/performance-blist

Microbenchmarks should always be taken with a grain of salt. :-)  I was hoping http://speed.python.org/ create an opportunity to make some macrobenchmark comparisons, but the project stalled.

--
Daniel Stutzbach