Because :doc:`Sorted Containers<index>` is implemented in pure-Python, its performance depends directly on the Python runtime. :doc:`Sorted Containers<index>` is primarily developed, tested and benchmarked on CPython 3.7.
Not all runtimes are created equal. The graphs below compare :doc:`Sorted Containers<index>` running on the CPython 3.7, CPython 2.7, and PyPy runtimes. As of Python 3.7 the CPython 3.7 runtime is now faster than the CPython 2.7 runtime. The PyPy runtime displays much more variability due to its JIT-ed nature. Once the just-in-time compiler optimizes the code, performance is often two to ten times faster.
Performance of competing implementations are benchmarked against the CPython 3.7 runtime. An :doc:`implementation performance comparison<performance>` is also included with data from popular sorted container packages.
:doc:`Sorted Containers<index>` 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 :doc:`load factor performance comparison<performance-load>` is also provided.
Though these benchmarks exercise only one API repeatedly, an effort has also been made to simulate real-world workloads. The :doc:`simulated workload performance comparison<performance-workload>` contains examples with comparisons to other implementations, load factors, and runtimes.
.. currentmodule:: sortedcontainers
Graphs comparing :doc:`sortedlist` performance.
Initializing with a list of random numbers using :func:`SortedList.__init__`.
Randomly adding values using :func:`SortedList.add`.
Randomly testing membership using :func:`SortedList.__contains__`.
Counting objects at random using :func:`SortedList.count`.
Deleting objects at random using :func:`SortedList.__delitem__`.
Retrieving objects by index using :func:`SortedList.__getitem__`.
Finding the index of an object using :func:`SortedList.index`.
Iterating a SortedList using :func:`SortedList.__iter__`.
Removing the last object using :func:`SortedList.pop`.
Remove an object at random using :func:`SortedList.remove`.
Updating a SortedList with a large iterable using :func:`SortedList.update`.
Updating a SortedList with a small iterable using :func:`SortedList.update`.
Graphs comparing :doc:`sorteddict` performance.
Initializing with a list of pairs of random numbers using :func:`SortedDict.__init__`.
Given a key at random, test whether the key is in the dictionary using :func:`SortedDict.__contains__`.
Given a key at random, retrieve the value using :func:`SortedDict.__getitem__`.
Given a key at random, set the value using :func:`SortedDict.__setitem__`.
Given a key at random, delete the value using :func:`SortedDict.__delitem__`.
Iterate the keys of a SortedDict using :func:`SortedDict.__iter__`.
Given an existing key at random, set the value using :func:`SortedDict.__setitem__`.
Graphs comparing :doc:`sortedset` performance.
Initializing with a list of random numbers using :func:`SortedSet.__init__`.
Randomly add values using :func:`SortedSet.add`.
Randomly test membership using :func:`SortedSet.__contains__`.
Set difference using :func:`SortedSet.difference`.
Set difference using :func:`SortedSet.difference`.
Set difference using :func:`SortedSet.difference`.
Set difference using :func:`SortedSet.difference`.
Set difference using :func:`SortedSet.difference_update`.
Set difference using :func:`SortedSet.difference_update`.
Set difference using :func:`SortedSet.difference_update`.
Set difference using :func:`SortedSet.difference_update`.
Set intersection using :func:`SortedSet.intersection`.
Set intersection using :func:`SortedSet.intersection`.
Set intersection using :func:`SortedSet.intersection`.
Set intersection using :func:`SortedSet.intersection`.
Set intersection using :func:`SortedSet.intersection_update`.
Set intersection using :func:`SortedSet.intersection_update`.
Set intersection using :func:`SortedSet.intersection_update`.
Set intersection using :func:`SortedSet.intersection_update`.
Iterating a set using :func:`iter(SortedSet)`.
Remove the last item in a set using :func:`SortedSet.pop`.
Remove an item at random using :func:`SortedSet.remove`.
Set union using :func:`SortedSet.union`.
Set union using :func:`SortedSet.union`.
Set union using :func:`SortedSet.union`.
Set union using :func:`SortedSet.union`.
Set update using :func:`SortedSet.update`.
Set update using :func:`SortedSet.update`.
Set update using :func:`SortedSet.update`.
Set update using :func:`SortedSet.update`.
Set symmetric-difference using :func:`SortedSet.symmetric_difference`.
Set symmetric-difference using :func:`SortedSet.symmetric_difference`.
Set symmetric-difference using :func:`SortedSet.symmetric_difference`.
Set symmetric-difference using :func:`SortedSet.symmetric_difference`.
Set symmetric-difference using :func:`SortedSet.symmetric_difference_update`.
Set symmetric-difference using :func:`SortedSet.symmetric_difference_update`.
Set symmetric-difference using :func:`SortedSet.symmetric_difference_update`.
Set symmetric-difference using :func:`SortedSet.symmetric_difference_update`.
