Performance of repeat and inplace repeat operations.

[eendebakpt]

In a recent PR the performance of the repeat and inplace repeat methods was improved for the bytearray object (python/cpython#31856) by reducing the number of memcpy operations.

In python/cpython#31999 the same approach is used to improve the performance of array_inplace_repeat. In that PR some of the code is refactored into utility methods _PyBytes_Repeat and _PyBytes_RepeatInPlace . The code is faster for a high number of repeats, but for a lower number of repeats this is not clear (microbenchmarks on my system don't give answers). Perhaps there is some overhead in calling the utility functions.

The list and tuple objects also have repeat methods, but they do not use the memcpy operation.
In python/cpython@main...eendebakpt:performance/list_repeat a small improvement is made, but perhaps more can be gained by using the utility methods..

• Is there any overhead on the utility methods that should be eliminated?
• Is there a reason the list and tuple methods do not use memcpy? Perhaps for those objects the use case is mostly in repeats with a low number of repetitions and memcpy has a overhead on those.

Any thoughts or suggestions are welcome.

@sweeneyde

[gvanrossum]

It's not so easy for list/tuple, because their contents has refcounts that need to be updated. So probably there's less opportunity for improvement. (Feel free to submit a PR with measurements to prove me wrong though!)

[eendebakpt]

@gvanrossum I created a PR from the code I have: python/cpython#32045
There is an small performance gain for the benchmarks involving larger numbers of repeats.

list repeat 1: Mean +- std dev: [base] 139 ns +- 2 ns -> [v2] 133 ns +- 5 ns: 1.05x faster
list repeat 10: Mean +- std dev: [base] 173 ns +- 3 ns -> [v2] 175 ns +- 5 ns: 1.01x slower
list repeat 1000: Mean +- std dev: [base] 7.58 us +- 0.04 us -> [v2] 4.23 us +- 0.02 us: 1.79x faster
list repeat 5000: Mean +- std dev: [base] 36.8 us +- 0.4 us -> [v2] 23.4 us +- 0.5 us: 1.58x faster
list(1) repeat 1: Mean +- std dev: [base] 57.5 ns +- 0.8 ns -> [v2] 55.3 ns +- 1.0 ns: 1.04x faster
list repeat inplace 1: Mean +- std dev: [base] 76.8 ns +- 0.9 ns -> [v2] 74.4 ns +- 0.5 ns: 1.03x faster
list repeat inplace 10: Mean +- std dev: [base] 133 ns +- 2 ns -> [v2] 125 ns +- 1 ns: 1.07x faster
list repeat inplace 1000: Mean +- std dev: [base] 4.98 us +- 1.04 us -> [v2] 2.10 us +- 0.02 us: 2.37x faster
tuple repeat 1: Mean +- std dev: [base] 48.3 ns +- 0.9 ns -> [v2] 49.6 ns +- 1.6 ns: 1.03x slower
tuple repeat 10: Mean +- std dev: [base] 242 ns +- 2 ns -> [v2] 270 ns +- 2 ns: 1.12x slower
tuple repeat 1000: Mean +- std dev: [base] 9.75 us +- 0.10 us -> [v2] 7.15 us +- 0.35 us: 1.36x faster
tuple repeat 5000: Mean +- std dev: [base] 48.8 us +- 0.3 us -> [v2] 40.4 us +- 0.2 us: 1.21x faster
[control] list create: Mean +- std dev: [base] 46.5 ns +- 0.6 ns -> [v2] 43.8 ns +- 0.6 ns: 1.06x faster
[control] list concat: Mean +- std dev: [base] 44.3 ns +- 0.6 ns -> [v2] 42.3 ns +- 0.9 ns: 1.05x faster

Benchmark hidden because not significant (6): list(1) repeat 10, list(1) repeat 1000, list(1) repeat 5000, [control] list pop+append 1, [control] list pop+append 10, [control] list pop+append 200

Geometric mean: 1.14x faster

Performance tested with

import pyperf

runner = pyperf.Runner()


setup='a=[1,2]; b=[1,]; t=(1,2,3,4)'

for n in [1,10,1000, 5000]:
	runner.timeit(name=f"list repeat {n}",
              stmt=f"x=a*{n}; y=a*{n}",
              setup=setup)

for n in [1,10,1000, 5000]:
	runner.timeit(name=f"list(1) repeat {n}",
              stmt=f"x=b*{n};",
              setup=setup)

for n in [1,10,1000]:
	runner.timeit(name=f"list repeat inplace {n}",
              stmt=f"a=[1,2]; a*={n}",
              setup=setup)
              
for n in [1,10,1000, 5000]:
	runner.timeit(name=f"tuple repeat {n}",
              stmt=f"x=t*{n}; y=t*{n}",
              setup=setup)
              
for n in [1,10,200]:
	runner.timeit(name=f"[control] list pop+append {n}",
              stmt=f"x=a.pop(); a.append(1)",
              setup=setup)  
              

runner.timeit(name=f"[control] list create",
              stmt=f"x=[1,2,3]",
              setup=setup)                                       
              
runner.timeit(name=f"[control] list concat",
              stmt=f"x=a+b",
              setup=setup) 

The tests labelled with control involve operations not changed in the PR, so the timings should be unchanged (upto random fluctuations)