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 SortedContainers is performance so we would be remiss 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 mean of 5 repetitions. In the graphs below, the line follows the mean 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: 100 through 1,000,000.
Measurements up to 10,000,000,000 elements have been successfully tested and benchmarks. Read Performance at Scale for details. 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 CPython’s integers in a SortedList. Each integer object requires ~24 bytes so one hundred million elements will require about three 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.
- Provides a fast, C-implementation for dict and set data types. rbtree on PyPI
- Provides list, dict, and set containers based on the blist data-type. Implemented in Python and C. blist on PyPI
- Uses Cython for improved performance and provides a dict container. treap on PyPI
- 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
- 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
- Pure-Python implementation based on skip-lists providing a limited API for dict and set types. skiplistcollections on PyPI
- Pure-Python implementation of sorted list based solely on a list. Feature-poor and inefficient for writes but included because it is written by Raymond Hettinger and linked from the official Python docs. sortedcollection on ActiveState
Several competing implementations were omitted because they were not easily installable or failed to build.
- C-implementation that only supports Python 2. Performance was measured in
correspondence with the module author. Performance was generally very good
__delitem__. At scale, deleting entries became exceedingly slow. ruamel.ordereddict on PyPI
- 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 in 2010. Unlikely to be fast. python-avl-tree from Github user pgrafov
- C-implementation for AVL tree-based dict and set containers. Claims to be fast. Lacking documentation and failed to build. 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.
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.
Though these benchmarks exercise only one API repeatedly, an effort has also been made to simulate real-world workloads. The simulated workload performance comparison contains examples with comparisons to other implementations, load factors, and runtimes.
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.
Graphs comparing SortedList performance.
Initializing with a list of random numbers.
Graphs comparing SortedDict performance.
Initializing with a list of pairs of random numbers.
Given a key at random, test whether the key is in the dictionary using SortedDict.__contains__.
Graphs comparing SortedSet performance.
Initializing with a list of random numbers.