: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 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, :doc:`Sorted Containers<index>` used a load factor of 100 but that changed in release 0.8.5 to 1,000 due to the :ref:`SortedList.__delitem__<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 :doc:`Performance at Scale<performance-scale>`.

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 collections packages.

Because :doc:`Sorted Containers<index>` is pure-Python, its performance also depends directly on the Python runtime. A :doc:`runtime performance comparison<performance-runtime>` 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 :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`.