List Growth Factor

@rhettinger

Hello amazing Python people :-) I want to preface this by acknowledging that I don't have experience implementing programming language internals, so I may be missing crucial information. More, it's my first interaction with the CPython community.

I've been recently watching an interesting analysis on array growth factors. At one point there was a comparison of CPython's growth factor ~1.125 and other languages — based on this Wikipedia section. The video highlights that such choice focuses more on memory savings rather than performance. I believe this ratio might be too conservative for today's speed/space trade-off considerations — perhaps it's a good time to revisit it and hopefully make faster-cpython!

While searching for sources for this issue, I came across a comment from @rhettinger — an amazing presenter!:

We should definitely revisit the over-allocation strategy. I last worked on the existing strategy back in 2004. Since then, the weighting of the speed/space trade-off considerations have changed.

I'm not a CPython developer either, but I decided to do some casual benchmarking this week to hopefully contribute to the discussion.

I skimmed the source in Objects/ and concluded that dicts and sets already use a larger growth factor. I'm guessing this is because resizing them is more expensive - rather than just being a memory copy, it involves reinserting all the elements. The code for Unicode objects usually precalculates sizes exactly instead of using a growth factor. That leaves list, bytes, and bytearray.

I wrote four quick patches so that I could benchmark growth factors of 1.5 and 2, both for list only and for all three types. I tried to match the style of the existing code as closely as possible. For example, I'd personally avoid the floating point operations here in favor of moving the calculation out of the if, but I kept the logic as-is to avoid biasing the benchmarks.

The following 22 benchmarks were failing, but that still left the majority working so I decided to continue.

async_tree
async_tree_cpu_io_mixed
async_tree_cpu_io_mixed_tg
async_tree_eager
async_tree_eager_cpu_io_mixed
async_tree_eager_cpu_io_mixed_tg
async_tree_eager_io
async_tree_eager_io_tg
async_tree_eager_memoization
async_tree_eager_memoization_tg
async_tree_eager_tg
async_tree_io
async_tree_io_tg
async_tree_memoization
async_tree_memoization_tg
async_tree_tg
chameleon
coverage
sqlalchemy_declarative
sqlalchemy_imperative
sqlite_synth
tornado_http

My setup is Debian 12, an Intel i7-11700KF CPU with a big air cooler, and GCC 12.2.0. The benchmarks were run in a bare-bones window manager session; the X server was running, but potentially CPU-intensive services like Syncthing were stopped. I used commit 2b47f46d7dc30d27b2486991fea4acd83553294b of CPython and 9e29e3f69595fed2b74a8dab081ce9caf1640cd9 of pyperformance.

Here are the geometric means of the runtime ratios of all benchmarks:

Growth factor	Speed compared to `main`
1.5 for `list`	1.011x faster
2 for `list`	1.009x faster
1.5 for `list`, `bytes`, and `bytearray`	1.006x faster
2 for `list`, `bytes`, and `bytearray`	1.005x faster

It looks like raising the growth factor for list to 1.5 speeds up CPython by 1%, but it's not a good idea to raise the factor further or to do that for bytes and bytearray.

I'm not sure how much of that is real and how much is statistical noise, so I'd appreciate reproductions. I've included the steps and files below, in the "Reproduction steps" section.

Per-benchmark results

I've only included the statistically significant benchmarks because this post is long enough already.

Growth factor 1.5 for list:

Benchmark	Time (main)	Time (patched)	Change	Significance
deepcopy_memo	24.2 us	23.2 us	1.04x faster	t=35.19
django_template	31.4 ms	30.6 ms	1.03x faster	t=18.37
gc_traversal	3.68 ms	3.35 ms	1.10x faster	t=55.95
genshi_text	19.1 ms	18.7 ms	1.02x faster	t=9.48
json_dumps	9.92 ms	9.66 ms	1.03x faster	t=16.34
logging_silent	81.0 ns	76.6 ns	1.06x faster	t=22.57
mako	8.86 ms	9.05 ms	1.02x slower	t=-11.01
nbody	71.9 ms	73.7 ms	1.02x slower	t=-5.20
nqueens	72.8 ms	74.3 ms	1.02x slower	t=-7.40
pickle_dict	25.7 us	24.9 us	1.03x faster	t=15.65
pprint_pformat	1.35 sec	1.32 sec	1.03x faster	t=13.55
pprint_safe_repr	660 ms	643 ms	1.03x faster	t=14.22
regex_dna	159 ms	154 ms	1.03x faster	t=35.81
regex_v8	20.0 ms	18.2 ms	1.10x faster	t=115.82
tomli_loads	1.59 sec	1.62 sec	1.02x slower	t=-8.67
unpack_sequence	35.0 ns	35.8 ns	1.02x slower	t=-13.84

Growth factor 2 for list:

Benchmark	Time (main)	Time (patched)	Change	Significance
async_generators	369 ms	357 ms	1.03x faster	t=20.62
bench_thread_pool	846 us	870 us	1.03x slower	t=-3.28
comprehensions	14.5 us	13.8 us	1.05x faster	t=40.60
deepcopy_memo	24.2 us	23.1 us	1.05x faster	t=37.64
fannkuch	316 ms	303 ms	1.04x faster	t=28.08
gc_traversal	3.68 ms	3.53 ms	1.04x faster	t=21.33
logging_silent	81.0 ns	77.3 ns	1.05x faster	t=17.57
nbody	71.9 ms	73.7 ms	1.02x slower	t=-5.07
nqueens	72.8 ms	71.1 ms	1.02x faster	t=14.96
pickle	9.66 us	10.1 us	1.05x slower	t=-3.20
pickle_dict	25.7 us	25.1 us	1.02x faster	t=10.62
pprint_safe_repr	660 ms	645 ms	1.02x faster	t=10.85
pyflate	353 ms	331 ms	1.07x faster	t=37.42
regex_compile	111 ms	109 ms	1.02x faster	t=22.16
scimark_monte_carlo	53.8 ms	52.5 ms	1.02x faster	t=24.85
scimark_sor	95.2 ms	93.0 ms	1.02x faster	t=9.88
typing_runtime_protocols	148 us	140 us	1.06x faster	t=16.16
unpack_sequence	35.0 ns	36.2 ns	1.03x slower	t=-30.09
xml_etree_parse	121 ms	117 ms	1.04x faster	t=17.88

Growth factor 1.5 for list, bytes, and bytearray:

Benchmark	Time (main)	Time (patched)	Change	Significance
coroutines	18.8 ms	18.4 ms	1.02x faster	t=8.64
deepcopy_memo	24.2 us	23.2 us	1.04x faster	t=24.35
deltablue	2.55 ms	2.61 ms	1.02x slower	t=-13.85
gc_traversal	3.68 ms	3.43 ms	1.07x faster	t=35.53
genshi_text	19.1 ms	18.7 ms	1.02x faster	t=6.57
logging_silent	81.0 ns	78.4 ns	1.03x faster	t=16.89
pprint_pformat	1.35 sec	1.32 sec	1.03x faster	t=13.74
pprint_safe_repr	660 ms	644 ms	1.02x faster	t=10.27
regex_v8	20.0 ms	19.4 ms	1.03x faster	t=34.50
unpack_sequence	35.0 ns	33.4 ns	1.05x faster	t=43.97
unpickle_list	4.11 us	4.03 us	1.02x faster	t=7.33

Growth factor 2 for list, bytes, and bytearray:

Benchmark	Time (main)	Time (patched)	Change	Significance
async_generators	369 ms	360 ms	1.02x faster	t=14.15
comprehensions	14.5 us	14.1 us	1.03x faster	t=22.81
deepcopy_memo	24.2 us	23.2 us	1.04x faster	t=22.23
fannkuch	316 ms	324 ms	1.03x slower	t=-19.33
gc_traversal	3.68 ms	3.54 ms	1.04x faster	t=19.75
logging_silent	81.0 ns	76.3 ns	1.06x faster	t=17.48
mako	8.86 ms	9.14 ms	1.03x slower	t=-12.63
nqueens	72.8 ms	71.3 ms	1.02x faster	t=14.67
pickle_list	3.81 us	3.89 us	1.02x slower	t=-6.68
regex_dna	159 ms	149 ms	1.07x faster	t=80.65
regex_effbot	2.26 ms	2.16 ms	1.05x faster	t=18.57
regex_v8	20.0 ms	19.0 ms	1.05x faster	t=41.66
scimark_sparse_mat_mult	3.46 ms	3.37 ms	1.03x faster	t=10.57
tomli_loads	1.59 sec	1.63 sec	1.03x slower	t=-9.18
typing_runtime_protocols	148 us	141 us	1.05x faster	t=12.58
unpack_sequence	35.0 ns	33.8 ns	1.04x faster	t=27.90

Original result files here: json-results.tar.gz.

Reproduction steps

Download the source files here: patches-config-and-script.tar.gz.

Put the patches and benchmark.conf in ~/pybench.

Install pyperformance:

pipx uninstall pyperformance
pipx install 'git+https://github.com/python/pyperformance.git@9e29e3f69595fed2b74a8dab081ce9caf1640cd9'

Clone CPython:

cd ~/pybench
git clone 'https://github.com/python/cpython'

Stop unnecessary programs, then tune the system for benchmarks:

sudo ~/.local/pipx/venvs/pyperformance/bin/pyperf system tune

Now you can benchmark main and the patched versions:

cd ~/pybench
pyperformance compile benchmark.conf 2b47f46d7dc30d27b2486991fea4acd83553294b main
for patch in patches/*.patch; do
    pyperformance compile --patch "$patch" benchmark.conf 2b47f46d7dc30d27b2486991fea4acd83553294b main
done

If you want, you can also use my script to screen-scrape pyperformance's output and calculate the geometric means:

mkdir -p results-txt
pyperformance compare -O table json/2025-04-21_21-15-main-2b47f46d7dc3.json.gz json/patch/2025-04-21_21-15-main-2b47f46d7dc3-patch-0001-Change-list-growth-factor-to-1.5.json.gz >results-txt/list-1.5.txt
# And so on for all the other comparisons you want to do, then:
./geomean-from-pyperformance-output.py results-txt/*

Navigation Menu

Repository navigation

List Growth Factor #718

Per-benchmark results

Reproduction steps

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

List Growth Factor #718

Description

Activity

pkkm commented on Apr 27, 2025

Per-benchmark results

Reproduction steps

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions