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.
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.
Graphs comparing Sorted List performance.
Graphs comparing Sorted Dict performance.
Given a key at random, test whether the key is in the dictionary using
Graphs comparing Sorted Set performance.
Iterating a set using