# 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.7 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__()`.

### add

Randomly adding values using `SortedList.add()`.

### contains

Randomly testing membership using `SortedList.__contains__()`.

### count

Counting objects at random using `SortedList.count()`.

### __delitem__

Deleting objects at random using `SortedList.__delitem__()`.

### __getitem__

Retrieving objects by index using `SortedList.__getitem__()`.

### index

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

### iter

Iterating a SortedList using `SortedList.__iter__()`.

### pop

Removing the last object using `SortedList.pop()`.

### remove

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

### update_large

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

### update_small

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

## Sorted Dict

Graphs comparing Sorted Dict performance.

### __init__

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

### __contains__

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

### __getitem__

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

### __setitem__

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

### __delitem__

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

### iter

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

### setitem_existing

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

## Sorted Set

Graphs comparing Sorted Set performance.

### __init__

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

### add

Randomly add values using `SortedSet.add()`.

### contains

Randomly test membership using `SortedSet.__contains__()`.

### difference_large

Set difference using `SortedSet.difference()`.

### difference_medium

Set difference using `SortedSet.difference()`.

### difference_small

Set difference using `SortedSet.difference()`.

### difference_tiny

Set difference using `SortedSet.difference()`.

### difference_update_large

Set difference using `SortedSet.difference_update()`.

### difference_update_medium

Set difference using `SortedSet.difference_update()`.

### difference_update_small

Set difference using `SortedSet.difference_update()`.

### difference_update_tiny

Set difference using `SortedSet.difference_update()`.

### intersection_large

Set intersection using `SortedSet.intersection()`.

### intersection_medium

Set intersection using `SortedSet.intersection()`.

### intersection_small

Set intersection using `SortedSet.intersection()`.

### intersection_tiny

Set intersection using `SortedSet.intersection()`.

### intersection_update_large

Set intersection using `SortedSet.intersection_update()`.

### intersection_update_medium

Set intersection using `SortedSet.intersection_update()`.

### intersection_update_small

Set intersection using `SortedSet.intersection_update()`.

### intersection_update_tiny

Set intersection using `SortedSet.intersection_update()`.

### iter

Iterating a set using `iter(SortedSet)()`.

### pop

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

### remove

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

### union_large

Set union using `SortedSet.union()`.

### union_medium

Set union using `SortedSet.union()`.

### union_small

Set union using `SortedSet.union()`.

### union_tiny

Set union using `SortedSet.union()`.

### update_large

Set update using `SortedSet.update()`.

### update_medium

Set update using `SortedSet.update()`.

### update_small

Set update using `SortedSet.update()`.

### update_tiny

Set update using `SortedSet.update()`.

### symmetric_difference_large

Set symmetric-difference using `SortedSet.symmetric_difference()`.

### symmetric_difference_medium

Set symmetric-difference using `SortedSet.symmetric_difference()`.

### symmetric_difference_small

Set symmetric-difference using `SortedSet.symmetric_difference()`.

### symmetric_difference_tiny

Set symmetric-difference using `SortedSet.symmetric_difference()`.

### symm_diff_update_large

Set symmetric-difference using `SortedSet.symmetric_difference_update()`.

### symm_diff_update_medium

Set symmetric-difference using `SortedSet.symmetric_difference_update()`.

### symm_diff_update_small

Set symmetric-difference using `SortedSet.symmetric_difference_update()`.

### symm_diff_update_tiny

Set symmetric-difference using `SortedSet.symmetric_difference_update()`.