Performance test, blist slower?

[apiszcz]

Python 3.7, Windows 10/64, blist 1.3.6

Multiple runs each end up with the similar timing

[elihunter173]

That should be expected. blist optimizes for arbitrary insertion, slicing, and indexing. Both Python and blist has O(1) appending and Python's list.append comparatively has very little to do because it doesn't have to maintain the blist's tree structure. So the overhead of that additional maintenance is what you're seeing here.

[frankencode]

The documentation states the underlying implementation uses a regular order statistic B+-tree. That means appending involves splitting the max node in the tree whenever it runs full and copying half of the contents to a new max node. I wonder what the cost is, when you remove the "str()" calls and insert integers instead. Because copying strings is usually more expensive that copying integers. Just my 2 cents.