This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author Stefan Pochmann
Recipients Stefan Pochmann, rhettinger, tim.peters
Date 2020-03-01.02:06:31
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1583028391.97.0.752129292214.issue39801@roundup.psfhosted.org>
In-reply-to
Content
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]))
History
Date User Action Args
2020-03-01 02:06:32Stefan Pochmannsetrecipients: + Stefan Pochmann, tim.peters, rhettinger
2020-03-01 02:06:31Stefan Pochmannsetmessageid: <1583028391.97.0.752129292214.issue39801@roundup.psfhosted.org>
2020-03-01 02:06:31Stefan Pochmannlinkissue39801 messages
2020-03-01 02:06:31Stefan Pochmanncreate