Message363035
I think I have a decent way to isolate the memmove vs for-loop times, in Python code. Here are example results, five rounds of inserting with list.insert or with slice assignment. The times for each of the two ways are pretty stable:
insert slice
0.024221 0.006754
0.024157 0.006710
0.024015 0.006734
0.024206 0.006731
0.024123 0.006769
For each run, I build a list of length 2**20 and append one value. Then I can insert 2**17 more values without the list internally resizing.
Then I measure inserting at index -1 and consider that the baseline, as it includes all the overhead costs like function calls and other differences between the two insertion methods.
Then I measure inserting at index -500 and subtract the baseline time. This difference should reflect how long the memmove or the for-loop took, as that's the difference between inserting at -1 and at -500. It's what I showed in those results above.
I chose -500 here because the use case I have in mind is sortedcontainers.SortedList, which I think mostly involves lists of length 1000 or more (up to 2000), and insertions somewhere in the middle.
Results for index -50 instead:
insert slice
0.002479 0.002217
0.002546 0.002113
0.002566 0.002007
0.002425 0.002081
0.002555 0.002261
I'm btw running Python 3.8.1 32-bit on Windows 10 64-bit on an Intel i5-7200U.
Rest of this message is the benchmark code:
from timeit import repeat
statements = (
'a.insert(-1,0)',
'a.insert(-50,0)',
'a[-1:0] = 0,',
'a[-50:0] = 0,',
)
# Verify that the statements work and don't cause internal list resizes.
for stmt in statements:
a = [0] * 2**20
a.append(0)
size_before = a.__sizeof__()
stmt = compile(stmt, '', 'single')
for _ in range(2**17):
exec(stmt)
assert len(a) == 2**20 + 1 + 2**17
assert a.__sizeof__() == size_before
# Run the benchmark.
print(' insert slice')
for _ in range(5):
times = []
for stmt in statements:
t = min(repeat(stmt, 'a=[0]*2**20; a.append(0)', number=2**17, repeat=20))
times.append(t)
print('%10.6f' * 2 % (times[1] - times[0], times[3] - times[2])) |
|
Date |
User |
Action |
Args |
2020-03-01 02:06:32 | Stefan Pochmann | set | recipients:
+ Stefan Pochmann, tim.peters, rhettinger |
2020-03-01 02:06:31 | Stefan Pochmann | set | messageid: <1583028391.97.0.752129292214.issue39801@roundup.psfhosted.org> |
2020-03-01 02:06:31 | Stefan Pochmann | link | issue39801 messages |
2020-03-01 02:06:31 | Stefan Pochmann | create | |
|