Repository navigation
Improve performance for list.insert() and del list[i] in free-threaded builds #158790
Description
Activity
#!/usr/bin/env python3 """pyperf benchmark for list.insert() / del list[i] element shifting. Usgae: PYTHONPATH=... <interpreter> bench_list_shift.py -o result.json -p 1 -n 10 python -m pyperf compare_to base.json patched.json --table --table-format md Each benchmark function performs one workload iteration; pyperf calibrates the number of loops per value. Results are compared with ``pyperf compare_to`` in the accompanying report. """ import pyperf def bench_del_front(n=100_000, k=2_000): lst = list(range(n)) for _ in range(k): del lst[0] def bench_del_mid(n=100_000, k=2_000): lst = list(range(n)) for _ in range(k): del lst[len(lst) // 2] def bench_insert_front(n=100_000, k=2_000): lst = list(range(n)) for _ in range(k): lst.insert(0, None) def bench_insert_mid(n=100_000, k=2_000): lst = list(range(n)) for _ in range(k): lst.insert(len(lst) // 2, None) def _small(n, k): # insert(0) and del[0] both shift ~n elements; the size stays n lst = list(range(n)) for _ in range(k): lst.insert(0, None) del lst[0] def bench_small_n8(n=8, k=200_000): _small(n, k) def bench_small_n16(n=16, k=200_000): _small(n, k) def bench_small_n32(n=32, k=200_000): _small(n, k) def bench_small_n1000(n=1000, k=20_000): _small(n, k) def bench_sliding_window(n=1000, k=50_000): # deque-like pattern: push to the front, pop from the back lst = list(range(n)) for i in range(k): lst.insert(0, i) lst.pop() def bench_control_del_last(n=100_000): # no shift: exercise the unchanged "delete last element" guard path lst = list(range(n)) for _ in range(n): del lst[-1] def bench_control_append(n=1_000_000): # no shift: unrelated fast path, should stay flat lst = [] append = lst.append for i in range(n): append(i) BENCHMARKS = [ ("del_front_n100k_k2k", bench_del_front), ("del_mid_n100k_k2k", bench_del_mid), ("insert_front_n100k_k2k", bench_insert_front), ("insert_mid_n100k_k2k", bench_insert_mid), ("small_n8_k200k", bench_small_n8), ("small_n16_k200k", bench_small_n16), ("small_n32_k200k", bench_small_n32), ("small_n1000_k20k", bench_small_n1000), ("sliding_window_n1000_k50k", bench_sliding_window), ("control_del_last_n100k", bench_control_del_last), ("control_append_n1M", bench_control_append), ] if __name__ == "__main__": runner = pyperf.Runner() for name, func in BENCHMARKS: runner.bench_func(name, func)
The benchmark is produced by AI and verified by me.
- added a commit that references this issue
on Oct 7, 2026
Feature or enhancement
ins1()(used bylist.insert()) andlist_ass_item_lock_held()shift the list with one atomic release store per element in free-threaded builds. Those atomic stores prevent the compiler from vectorizing the loops, making them much slower thanmemmove()for large shifts. I propose using the existingptr_wise_atomic_memmove()helper here. It usesmemmove()as a fast path when the list is owned by the current thread and is not shared, and keeps the atomic element-wise stores for lists that other threads can observe.The default (GIL) build keeps the current loops because the compiler can optimize them directly in the calling function, and they perform better in benchmarks.
pyperf, free-threaded release build (--disable-gil, -O3):
Compiling both versions in GIL mode produces the same code for
ins1()andlist_ass_item_lock_held(), so the default build is not affected.This continues gh-129069, which introduced
ptr_wise_atomic_memmove().Has this already been discussed elsewhere?
No response given
Links to previous discussion of this feature:
No response
Linked PRs