Performance Comparison

Measuring performance is a difficult task. All the benchmarks on this page are synthetic in the sense that they test one function repeatedly. Measurements in live systems are much harder to produce reliably. So take the following data with a grain of salt. That being said, a stated feature of the sortedcontainers Module is performance so it would be negligent not to produce this page with comparisons.

The source for all benchmarks can be found under the “tests” directory in the files prefixed “benchmark.” Measurements are made from the min, max, and average of 5 repetitions. In the graphs below, the line follows the average and at each point, the min/max displays the bounds. Note that the axes are log-log so properly reading two different lines would describe one metric as “X times” faster rather than “X seconds” faster. In all graphs, lower is better. Measurements are made by powers of ten: 10, 100, 1,000, 10,000, and 100,000.

Measurements up to 100,000,000 elements have been successfully tested but are impractical for publishing. Only a couple implementations (including sortedcontainers) are capable of handling so many elements. The major limiting factor at that size is memory. Consider the simple case of storing Python’s integers in a SortedList. Each integer object requires ~36 bytes so a hundred million elements will require about four gigabytes of memory. If the implemenation adds significant overhead then most systems will run out of memory. For all datasets which may be kept in memory, sortedcontainers is an excellent choice.

A good effort has been made to find competing implementations. Six in total were found with various list, set, and dict implementations.

rbtree
Provides a fast, C-implementation for dict and set data types. rbtree on PyPI
blist
Provides list, dict, and set containers based on the blist data-type. Implemented in Python and C. blist on PyPI
treap
Uses Cython for improved performance and provides a dict container. treap on PyPI
bintrees
Provides several tree-based implementations for dict and set containers. Fastest were AVL and Red-Black trees. Extends the conventional API to provide set operations for the dict type. Implemented in C. bintrees on PyPI
banyan
Provides a fast, C-implementation for dict and set data types. Offers some features also found in sortedcontainers like accessing the n-th item in a set or dict. banyan on PyPI
skiplistcollections
Pure-Python implementation based on skip-lists providing a limited-API for dict and set types. skiplistcollections on PyPI

Several competing implementations were omitted because they were not easily installable or failed to build.

rbtree from NewCenturyComputers
Pure-Python tree-based implementation. Not sure when this was last updated. Unlikely to be fast. rbtree from NewCenturyComputers
python-avl-tree from Github user pgrafov
Pure-Python tree-based implementation. Last updated 3 years ago. Unlikely to be fast. python-avl-tree from Github user pgrafov
pyavl
C-implementation for AVL tree-based dict and set containers. Claims to be fast. Last updated in 2012. Lacking documentation and failed to build on Windows. pyavl on PyPI

The most similar module to sortedcontainers is skiplistcollections given that each is implemented in Python. But as is displayed below, sortedcontainers is several times faster and provides a richer API. Often the pure-Python implementation in sortedcontainers is faster even than the C-implementation counterparts. Where it lacks, performance is generally on the same magnitude.

Because sortedcontainers is implemented in pure-Python, its performance depends directly on the Python runtime. A runtime performance comparison is also included with data from popular runtimes.

SortedContainers uses a segmented-list data structure similar to a B-tree limited to two levels of nodes. As part of the implementation, a load factor is used to determine how many values should be stored in each node. This can have a significant impact on performance and a load factor performance comparison is also provided.

A couple final notes about the graphs below. Missing data indicates the benchmark either took too long or failed. The set operations with tiny, small, medium, and large variations indicate the size of the container involved in the right-hand-side of the operation: tiny is exactly 10 elements; small is 10% of the size of the left-hand-side; medium is 50%; and large is 100%. The sortedcontainers module uses a different algorithm based on the size of the right-hand-side of the operation for a dramatic improvement in performance.

SortedList

Graphs comparing SortedList performance.

add

Randomly adding values using SortedList.add.

_images/SortedList-add.png

contains

Randomly testing membership using SortedList.__contains__.

_images/SortedList-contains.png

count

Counting objects at random using SortedList.count.

_images/SortedList-count.png

__delitem__

Deleting objects at random using SortedList.__delitem__.

_images/SortedList-delitem.png

__getitem__

Retrieving ojbects by index using SortedList.__getitem__.

_images/SortedList-getitem.png

index

Finding the index of an object using SortedList.index.

_images/SortedList-index.png

iter

Iterating a SortedList using SortedList.__iter__.

_images/SortedList-iter.png

pop

Removing the last object using SortedList.pop.

_images/SortedList-pop.png

remove

Remove an object at random using SortedList.remove.

_images/SortedList-remove.png

update_large

Updating a SortedList with a large iterable using SortedList.update.

_images/SortedList-update_large.png

update_small

Updating a SortedList with a small iterable using SortedList.update.

_images/SortedList-update_small.png

SortedDict

Graphs comparing SortedDict performance.

__contains__

Given a key at random, test whether the key is in the dictionary using SortedDict.__contains__.

_images/SortedDict-contains.png

__getitem__

Given a key at random, retrieve the value using SortedDict.__getitem__.

_images/SortedDict-getitem.png

__setitem__

Given a key at random, set the value using SortedDict.__setitem__.

_images/SortedDict-setitem.png

__delitem__

Given a key at random, delete the value using SortedDict.__delitem__.

_images/SortedDict-delitem.png

iter

Iterate the keys of a SortedDict using SortedDict.__iter__.

_images/SortedDict-iter.png

setitem_existing

Given an existing key at random, set the value using SortedDict.__setitem__.

_images/SortedDict-setitem_existing.png

SortedSet

Graphs comparing SortedSet performance.

add

Randomly add values using SortedSet.add.

_images/SortedSet-add.png

contains

Randomly test membership using SortedSet.__contains__.

_images/SortedSet-contains.png

difference_large

Set difference using SortedSet.difference.

_images/SortedSet-difference_large.png

difference_medium

Set difference using SortedSet.difference.

_images/SortedSet-difference_medium.png

difference_small

Set difference using SortedSet.difference.

_images/SortedSet-difference_small.png

difference_tiny

Set difference using SortedSet.difference.

_images/SortedSet-difference_tiny.png

difference_update_large

Set difference using SortedSet.difference_update.

_images/SortedSet-difference_update_large.png

difference_update_medium

Set difference using SortedSet.difference_update.

_images/SortedSet-difference_update_medium.png

difference_update_small

Set difference using SortedSet.difference_update.

_images/SortedSet-difference_update_small.png

difference_update_tiny

Set difference using SortedSet.difference_update.

_images/SortedSet-difference_update_tiny.png

intersection_large

Set intersection using SortedSet.intersection.

_images/SortedSet-intersection_large.png

intersection_medium

Set intersection using SortedSet.intersection.

_images/SortedSet-intersection_medium.png

intersection_small

Set intersection using SortedSet.intersection.

_images/SortedSet-intersection_small.png

intersection_tiny

Set intersection using SortedSet.intersection.

_images/SortedSet-intersection_tiny.png

intersection_update_large

Set intersection using SortedSet.intersection_update.

_images/SortedSet-intersection_update_large.png

intersection_update_medium

Set intersection using SortedSet.intersection_update.

_images/SortedSet-intersection_update_medium.png

intersection_update_small

Set intersection using SortedSet.intersection_update.

_images/SortedSet-intersection_update_small.png

intersection_update_tiny

Set intersection using SortedSet.intersection_update.

_images/SortedSet-intersection_update_tiny.png

iter

Iterating a set using iter(SortedSet).

_images/SortedSet-iter.png

pop

Remove the last item in a set using SortedSet.pop.

_images/SortedSet-pop.png

remove

Remove an item at random using SortedSet.remove.

_images/SortedSet-remove.png

union_large

Set union using SortedSet.union.

_images/SortedSet-union_large.png

union_medium

Set union using SortedSet.union.

_images/SortedSet-union_medium.png

union_small

Set union using SortedSet.union.

_images/SortedSet-union_small.png

union_tiny

Set union using SortedSet.union.

_images/SortedSet-union_tiny.png

update_large

Set update using SortedSet.update.

_images/SortedSet-update_large.png

update_medium

Set update using SortedSet.update.

_images/SortedSet-update_medium.png

update_small

Set update using SortedSet.update.

_images/SortedSet-update_small.png

update_tiny

Set update using SortedSet.update.

_images/SortedSet-update_tiny.png

symmetric_difference_large

Set symmetric-difference using SortedSet.symmetric_difference.

_images/SortedSet-symmetric_difference_large.png

symmetric_difference_medium

Set symmetric-difference using SortedSet.symmetric_difference.

_images/SortedSet-symmetric_difference_medium.png

symmetric_difference_small

Set symmetric-difference using SortedSet.symmetric_difference.

_images/SortedSet-symmetric_difference_small.png

symmetric_difference_tiny

Set symmetric-difference using SortedSet.symmetric_difference.

_images/SortedSet-symmetric_difference_tiny.png

symm_diff_update_large

Set symmetric-difference using SortedSet.symmetric_difference_update.

_images/SortedSet-symmetric_difference_update_large.png

symm_diff_update_medium

Set symmetric-difference using SortedSet.symmetric_difference_update.

_images/SortedSet-symmetric_difference_update_medium.png

symm_diff_update_small

Set symmetric-difference using SortedSet.symmetric_difference_update.

_images/SortedSet-symmetric_difference_update_small.png

symm_diff_update_tiny

Set symmetric-difference using SortedSet.symmetric_difference_update.

_images/SortedSet-symmetric_difference_update_tiny.png