gh-94603: micro optimize list.pop #94604

eendebakpt · 2022-07-06T12:44:58Z

This PR optmizes list.pop

Benchmark results

x=[1,2]; x.pop(0): Mean +- std dev: [m2] 81.8 ns +- 2.5 ns -> [pr_special] 68.9 ns +- 2.0 ns: 1.19x faster
x=[1,2]; x.pop(1): Mean +- std dev: [m2] 65.4 ns +- 2.1 ns -> [pr_special] 64.4 ns +- 0.6 ns: 1.02x faster
x=[]; x.insert(0,1); x.pop(0): Mean +- std dev: [m2] 111 ns +- 3 ns -> [pr_special] 80.2 ns +- 1.1 ns: 1.38x faster
list(0): insert(0, None) + pop(0): Mean +- std dev: [m2] 78.4 ns +- 0.8 ns -> [pr_special] 62.1 ns +- 1.3 ns: 1.26x faster
list(1): insert(0, None) + pop(1): Mean +- std dev: [m2] 59.7 ns +- 0.4 ns -> [pr_special] 57.7 ns +- 0.9 ns: 1.04x faster
list(2): insert(0, None) + pop(1): Mean +- std dev: [m2] 66.9 ns +- 0.6 ns -> [pr_special] 55.5 ns +- 1.8 ns: 1.20x faster
list(10): insert(0, None) + pop(1): Mean +- std dev: [m2] 71.9 ns +- 0.6 ns -> [pr_special] 62.4 ns +- 2.8 ns: 1.15x faster
list(100): insert(0, None) + pop(1): Mean +- std dev: [m2] 108 ns +- 4 ns -> [pr_special] 93.5 ns +- 3.3 ns: 1.16x faster
list(10000): insert(0, None) + pop(1): Mean +- std dev: [m2] 5.41 us +- 0.02 us -> [pr_special] 5.37 us +- 0.02 us: 1.01x faster

Benchmark hidden because not significant (2): x=[1]; x.pop(0), sortedcontainer

Geometric mean: 1.12x faster

Benchmark code

import pyperf
import sortedcontainers


runner = pyperf.Runner()

runner.timeit(name=f"x=[1]; x.pop(0)",stmt='x=[1]; x.pop(0)')
runner.timeit(name=f"x=[1,2]; x.pop(0)", stmt='x=[1,2]; x.pop(0)')
runner.timeit(name=f"x=[1,2]; x.pop(1)",stmt='x=[1,2]; x.pop(1)')
runner.timeit(name=f"x=[]; x.insert(0,1); x.pop(0)",stmt='x=[]; x.insert(0,1); x.pop(0)')
runner.timeit(name=f"list(0): insert(0, None) + pop(0)", stmt="lst.insert(0, None); lst.pop(0)", setup='lst=[]')

for n in [ 1, 2, 10, 100, 10_000]:
    runner.timeit(name=f"list({n}): insert(0, None) + pop(1)",
	      stmt="lst.insert(0, None); lst.pop(1)", setup=f'import random; lst=[random.random() for ii in range({n})]')

setup ="import random; import sortedcontainers; sc=sortedcontainers.SortedList(); x=[random.random() for n in range(1_00_000)]"

runner.timeit(name=f"sortedcontainer", stmt="[sc.add(v) for v in x]", setup=setup)

Issue: gh-94603

corona10 · 2022-07-08T05:15:59Z

@serhiy-storchaka is the expert who can decide these kinds of micro-optimization is worth applying :)

Objects/listobject.c

Co-authored-by: Dong-hee Na <donghee.na92@gmail.com>

serhiy-storchaka · 2022-07-09T07:19:06Z

I am a bit surprised to see a significant difference in that microbenchmarks. The method call adds an overhead, and since this method is not idempotent, you need to add even more expensive code to create a list or adding an item in the existing list list at every iteration, so I expected the difference be rather unnoticeable. But I repeated microbenchmarking myself and confirm the results. It looks interesting.

Now, we need to analyze, why we get such significant speedup, can the optimization be generalized to other methods, can we get the same results with simpler changes?

Objects/listobject.c

Co-authored-by: Dong-hee Na <donghee.na92@gmail.com>

optimize list.pop

79ac0ff

bedevere-bot added the awaiting review label Jul 6, 2022

AlexWaygood added type-feature performance labels Jul 6, 2022

blurb-it bot and others added 2 commits Jul 6, 2022

📜🤖 Added by blurb_it.

4cf3c19

fix news item

4db7ec5

corona10 requested a review from serhiy-storchaka Jul 8, 2022

corona10 reviewed Jul 8, 2022

View changes

Objects/listobject.c Outdated Show resolved Hide resolved

Update Objects/listobject.c

1512885

Co-authored-by: Dong-hee Na <donghee.na92@gmail.com>

corona10 reviewed Jul 10, 2022

View changes

Objects/listobject.c Outdated Show resolved Hide resolved

Update Objects/listobject.c

58e38d6

Co-authored-by: Dong-hee Na <donghee.na92@gmail.com>

gh-94603: micro optimize list.pop #94604

gh-94603: micro optimize list.pop #94604

eendebakpt commented Jul 6, 2022 •

edited by bedevere-bot

corona10 commented Jul 8, 2022

serhiy-storchaka commented Jul 9, 2022

gh-94603: micro optimize list.pop #94604

Are you sure you want to change the base?

gh-94603: micro optimize list.pop #94604

Conversation

eendebakpt commented Jul 6, 2022 • edited by bedevere-bot

corona10 commented Jul 8, 2022

serhiy-storchaka commented Jul 9, 2022

eendebakpt commented Jul 6, 2022 •

edited by bedevere-bot