Why does this code take 123 ms vs the excpected 12 ms?

[layssi]

#This is running in Pycharm and Conda

from sortedcontainers import SortedList, SortedSet, SortedDict
import timeit
import random

def test_speed(data,sorted_data):
for val in data: #Accessing this is not an issue
sorted_data.add(val)

data = []
numpts = 10 ** 5
for i in range(numpts):
data.append(random.random())
print(f'Num of pts:{len(data)}')

sorted_data = SortedList()
n_runs=10
result = timeit.timeit(stmt='test_speed(data,sorted_data)', globals=globals(), number=n_runs)
print(f'Speed is {1000*result/n_runs:0.0f}ms')

[grantjenks]

Your benchmark is simply different from mine. See tests/benchmark_sortedlist.py

@register_test
def add(func, size):
    for val in lists[size][::100]:
        func(val)

The size of the SortedList is 10**5 but the benchmark does 10**3 add operations. Reducing the number of operations makes it possible to scale to higher sizes. It’s not going to take the same time on your machine as my machine. The charts are provided for relative performance comparison, not absolute.

[layssi]

This same test takes 15ms. Why does inserting one reduces performance by 10X ?

def test_speed1(data):
SortedList(data)

[grantjenks]

I don’t follow. Needs repro.

[layssi]

from sortedcontainers import SortedList, SortedSet, SortedDict
import timeit
import random

def test_speed1(data):
SortedList(data)

def test_speed2(data):
sorted_data = SortedList()
for val in data:
sorted_data.add(val)

data = []
numpts = 10 ** 5
for i in range(numpts):
data.append(random.random())
print(f'Num of pts:{len(data)}')

sorted_data = SortedList()
n_runs=10
result = timeit.timeit(stmt='test_speed1(data)', globals=globals(), number=n_runs)
print(f'Speed1 is {1000*result/n_runs:0.0f}ms')

n_runs=10
result = timeit.timeit(stmt='test_speed2(data)', globals=globals(), number=n_runs)
print(f'Speed2 is {1000*result/n_runs:0.0f}ms')

[layssi]

Speed1 is 14ms
Speed2 is 119ms
Adding one item at a time is very slow in comparison

[grantjenks]

init() uses Python’s highly optimized sorted() function while add() cannot.

[layssi]

Thank you.