Repository navigation
Update list() to use the existing freelist #160858
Description
Feature or enhancement
list_vectorcall() currently allocates with PyType_GenericAlloc() so list() and list(iterable) always allocate new. [] and PyList_New() reuse an object when possible from the existing list freelist instead. Can reuse the freelist in the tp_vectorcall slot which only applies for the exact type.
I found this while profiling builtin constructor calls with callgrind (instructions per function). For list(t), about a third of the cost was PyType_GenericAlloc() plus the matching malloc/free, which [] never pays.
Microbenchmarks (pyperf, PGO+LTO, Linux x86-64, interleaved A/B, main vs patch):
| Benchmark | main | patch |
|---|---|---|
| list() | 21.2 ns | 15.3 ns: 1.38x faster |
| list(d) | 36.1 ns | 27.4 ns: 1.32x faster |
| list(t) | 30.3 ns | 23.9 ns: 1.27x faster |
| list(l) | 32.0 ns | 25.7 ns: 1.24x faster |
| list(r) | 43.6 ns | 36.0 ns: 1.21x faster |
Untouched controls ([], a list subclass, x + 1, len(l), l[0], tuple(l)) stay within the A/A noise (≤ 1.07x).
Benchmark script
import pyperf
runner = pyperf.Runner()
for stmt in ["list()", "list(t)", "list(l)", "list(r)", "list(d)", "L(t)", "[]",
"len(l)", "l[0]", "x + 1", "tuple(l)"]:
runner.timeit(stmt, stmt,
"t = (1, 2, 3); l = [1, 2, 3]; r = range(3); d = dict.fromkeys(t); x = 12345\n"
"class L(list): pass")./python bm_list.py --affinity=10-13 -o main.json # on main
./python bm_list.py --affinity=10-13 -o patch.json # on the patch
python -m pyperf compare_to main.json patch.json --table -GRuns were interleaved (main, patch, main, patch) on PGO+LTO builds.
pystats: list() now hits the freelist
Object counters for 100,000 executions (stats enabled only around the loop):
| statement | main: allocations / from freelist | patch: allocations / from freelist |
|---|---|---|
list() |
100,001 / 98,978 | 1 / 198,978 |
list(t) |
200,001 / 98,978 | 100,001 / 198,978 |
[] |
1 / 198,978 | 1 / 198,978 |
After warm-up, every list() object comes from the freelist, as with [].
The remaining allocation in list(t) is the item array.
- The list freelist was added in 2004 by Apply freelist technique to empty lists #40215..
list_vectorcall()was added in bpo-37207: Use vertorcall for list() #18928 and kept using the existing generic alloc.
Has this already been discussed elsewhere?
This is a minor feature, which does not need previous discussion elsewhere
Links to previous discussion of this feature:
No response
Activity
gh-160858: Use the list freelist in list() (gh-160859)