Load Factor Performance Comparison

Sorted Containers 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 page compares three load factors on containers with as many as ten of million elements.

No single load factor is universally superior. The best load factor for your purposes will depend on your usage pattern. Originally, Sorted Containers used a load factor of 100 but that changed in release 0.8.5 to 1,000 due to the SortedList.__delitem__ benchmark which was dramatically impacted. Most benchmarks perform slightly better with a load factor of 100 but each is competitive with alternate loads. For an in-depth analysis of the load factor read Performance at Scale.

Performance of competing implementations are benchmarked against the CPython 3.6 runtime. An implementation performance comparison is also included with data from popular sorted collections packages.

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

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.

Sorted List

Graphs comparing Sorted List performance.

__init__

Initializing with a list of random numbers using SortedList.__init__().

_images/SortedList_load-init.png

add

Randomly adding values using SortedList.add().

_images/SortedList_load-add.png

contains

Randomly testing membership using SortedList.__contains__().

_images/SortedList_load-contains.png

count

Counting objects at random using SortedList.count().

_images/SortedList_load-count.png

__delitem__

Deleting objects at random using SortedList.__delitem__().

_images/SortedList_load-delitem.png

__getitem__

Retrieving ojbects by index using SortedList.__getitem__().

_images/SortedList_load-getitem.png

index

Finding the index of an object using SortedList.index().

_images/SortedList_load-index.png

iter

Iterating a SortedList using SortedList.__iter__().

_images/SortedList_load-iter.png

pop

Removing the last object using SortedList.pop().

_images/SortedList_load-pop.png

remove

Remove an object at random using SortedList.remove().

_images/SortedList_load-remove.png

update_large

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

_images/SortedList_load-update_large.png

update_small

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

_images/SortedList_load-update_small.png

Sorted Dict

Graphs comparing Sorted Dict performance.

__init__

Initializing with a list of pairs of random numbers using SortedDict.__init__().

_images/SortedDict_load-init.png

__contains__

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

_images/SortedDict_load-contains.png

__getitem__

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

_images/SortedDict_load-getitem.png

__setitem__

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

_images/SortedDict_load-setitem.png

__delitem__

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

_images/SortedDict_load-delitem.png

iter

Iterate the keys of a SortedDict using SortedDict.__iter__().

_images/SortedDict_load-iter.png

setitem_existing

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

_images/SortedDict_load-setitem_existing.png

Sorted Set

Graphs comparing Sorted Set performance.

__init__

Initializing with a list of random numbers using SortedSet.__init__().

_images/SortedSet_load-init.png

add

Randomly add values using SortedSet.add().

_images/SortedSet_load-add.png

contains

Randomly test membership using SortedSet.__contains__().

_images/SortedSet_load-contains.png

difference_large

Set difference using SortedSet.difference().

_images/SortedSet_load-difference_large.png

difference_medium

Set difference using SortedSet.difference().

_images/SortedSet_load-difference_medium.png

difference_small

Set difference using SortedSet.difference().

_images/SortedSet_load-difference_small.png

difference_tiny

Set difference using SortedSet.difference().

_images/SortedSet_load-difference_tiny.png

difference_update_large

Set difference using SortedSet.difference_update().

_images/SortedSet_load-difference_update_large.png

difference_update_medium

Set difference using SortedSet.difference_update().

_images/SortedSet_load-difference_update_medium.png

difference_update_small

Set difference using SortedSet.difference_update().

_images/SortedSet_load-difference_update_small.png

difference_update_tiny

Set difference using SortedSet.difference_update().

_images/SortedSet_load-difference_update_tiny.png

intersection_large

Set intersection using SortedSet.intersection().

_images/SortedSet_load-intersection_large.png

intersection_medium

Set intersection using SortedSet.intersection().

_images/SortedSet_load-intersection_medium.png

intersection_small

Set intersection using SortedSet.intersection().

_images/SortedSet_load-intersection_small.png

intersection_tiny

Set intersection using SortedSet.intersection().

_images/SortedSet_load-intersection_tiny.png

intersection_update_large

Set intersection using SortedSet.intersection_update().

_images/SortedSet_load-intersection_update_large.png

intersection_update_medium

Set intersection using SortedSet.intersection_update().

_images/SortedSet_load-intersection_update_medium.png

intersection_update_small

Set intersection using SortedSet.intersection_update().

_images/SortedSet_load-intersection_update_small.png

intersection_update_tiny

Set intersection using SortedSet.intersection_update().

_images/SortedSet_load-intersection_update_tiny.png

iter

Iterating a set using iter(SortedSet)().

_images/SortedSet_load-iter.png

pop

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

_images/SortedSet_load-pop.png

remove

Remove an item at random using SortedSet.remove().

_images/SortedSet_load-remove.png

union_large

Set union using SortedSet.union().

_images/SortedSet_load-union_large.png

union_medium

Set union using SortedSet.union().

_images/SortedSet_load-union_medium.png

union_small

Set union using SortedSet.union().

_images/SortedSet_load-union_small.png

union_tiny

Set union using SortedSet.union().

_images/SortedSet_load-union_tiny.png

update_large

Set update using SortedSet.update().

_images/SortedSet_load-update_large.png

update_medium

Set update using SortedSet.update().

_images/SortedSet_load-update_medium.png

update_small

Set update using SortedSet.update().

_images/SortedSet_load-update_small.png

update_tiny

Set update using SortedSet.update().

_images/SortedSet_load-update_tiny.png

symmetric_difference_large

Set symmetric-difference using SortedSet.symmetric_difference().

_images/SortedSet_load-symmetric_difference_large.png

symmetric_difference_medium

Set symmetric-difference using SortedSet.symmetric_difference().

_images/SortedSet_load-symmetric_difference_medium.png

symmetric_difference_small

Set symmetric-difference using SortedSet.symmetric_difference().

_images/SortedSet_load-symmetric_difference_small.png

symmetric_difference_tiny

Set symmetric-difference using SortedSet.symmetric_difference().

_images/SortedSet_load-symmetric_difference_tiny.png

symm_diff_update_large

Set symmetric-difference using SortedSet.symmetric_difference_update().

_images/SortedSet_load-symmetric_difference_update_large.png

symm_diff_update_medium

Set symmetric-difference using SortedSet.symmetric_difference_update().

_images/SortedSet_load-symmetric_difference_update_medium.png

symm_diff_update_small

Set symmetric-difference using SortedSet.symmetric_difference_update().

_images/SortedSet_load-symmetric_difference_update_small.png

symm_diff_update_tiny

Set symmetric-difference using SortedSet.symmetric_difference_update().

_images/SortedSet_load-symmetric_difference_update_tiny.png