Repository navigation
Use freelist for range object, iterator objects and other often used objects #126703
Description
Activity
I would be willing to shepherd/champion such a PR. Back in the day we chose not to do this presumably because the added code complexity was not worth it. However, with Sam's consistent implementation of freelists, that point is now moot. Freelists are really simple to add mostly.
However, may I suggest trying first with medium ints? We can re-benchmark pyperformance with it. If you're not interested, just let me know and I can take over for medium ints.
I started with
rangebecause the ints are more complex (either do only the medium ints, or use a more complex scheme with a size based freelists).I already have a working branch for the medium int case, see main...eendebakpt:cpython:int_freelist. Once I have some more benchmarks and statistics I will open a PR.
Reacted by Ken JinReacted by Erlend E. Aasland- changed the title
[-]Use freelist for range and range_iter objects[/-][+]Use freelist for range and iter objects[/+]on Dec 21, 2024 Also for iter objects for list and tuple we can gain performance in microbenchmarks:
bench_list: Mean +- std dev: [iter_main] 180 ns +- 9 ns -> [iter_pr] 161 ns +- 2 ns: 1.12x faster bench_tuple: Mean +- std dev: [iter_main] 186 ns +- 16 ns -> [iter_pr] 169 ns +- 22 ns: 1.10x faster bench_range: Mean +- std dev: [iter_main] 186 ns +- 1 ns -> [iter_pr] 180 ns +- 3 ns: 1.04x faster Geometric mean: 1.09x fasterScript:
import pyperf def bench_list(loops): range_it = iter(range(loops)) lst = list(range(5)) t0 = pyperf.perf_counter() for ii in range_it: x = 0 for ii in lst: x += ii return pyperf.perf_counter() - t0 def bench_tuple(loops): range_it = iter(range(loops)) tpl = tuple(range(5)) t0 = pyperf.perf_counter() for ii in range_it: x = 0 for ii in tpl: x += ii return pyperf.perf_counter() - t0 def bench_range(loops): range_it = iter(range(loops)) r = range(5) t0 = pyperf.perf_counter() for ii in range_it: x = 0 for ii in r: x += ii return pyperf.perf_counter() - t0 # %timeit bench_list(1000) if __name__ == "__main__": runner = pyperf.Runner() runner.bench_time_func("bench_list", bench_list) runner.bench_time_func("bench_tuple", bench_tuple) runner.bench_time_func("bench_range", bench_range)To determine for which objects a freelist should be added (or removed) some statistics have been gathered. The data is gathered by adding some additional statistics functionality (branch: main...eendebakpt:cpython:wip_stats) and running the pyperformance benchmarks (minus some benchmarks that do not run on my system).
Most object allocations are tracked via generic calls like
_PyObject_Newor_PyObject_NewVar(using thetype->tp_name). Some objects allocate memory allocated directly (e.g. lists and tuples), for these objects manually statistics have been added. Not all objects have been added manually, so a few will be missing from the statistics.Here are the results on the types most often allocated and the number of freelist allocations:
Allocations Counts _PyLong_New 514.4M _PyLong_New_digits_2 369.5M list_iterator 215.6M builtin_function_or_method 165.6M generator 146.7M tuple_iterator 133.0M method 120.2M _PyLong_New_digits_1 104.2M StopIteration 94.7M function 88.7M _safe_key 72.0M range 65.8M coroutine 59.4M cell 46.7M range_iterator 44.1M frame 42.5M dict_items 41.7M Fraction 30.0M xml.etree.ElementTree.Element 30.0M _PyLong_New_digits_3 28.4M builtin_method 28.1M Vector 27.2M traceback 24.7M decimal.Decimal 24.0M dict_itemiterator 21.5M PyFloat_FromDouble_alloc 19.9M tuple 16.5M PyList_New_allocate 16.0M list 10.7M Tree 12.0M IndexError 11.0M iterator 10.0M set_iterator 9.3M re.Match 8.6M Node 8.1M weakref.ReferenceType 8.0M AttributeError 7.9M dict 7.8M set 6.7M Point 6.3M frozenset 6.3M StopAsyncIteration 6.0M async_generator 6.0M Ray 5.9M KeyError 4.8M mappingproxy 4.7M collections._deque_iterator 4.6M _PyLong_New_digits_4 4.2M GVector 4.2M map 3.8M halfstate_t 3.3M _pickle.Pickler 3.2M Markup 2.9M enumerate 2.7M str_ascii_iterator 2.4M posix.DirEntry 2.1M sqlite3.Cursor 2.0M C 2.0M _json.Encoder 1.9M list_reverseiterator 1.8M Text 1.8M Freelist allocations Counts ints 2064.0M floats 1461.5M tuples[index] 1251.7M lists 451.0M slices 347.0M dicts 150.0M async_gen_asends 100.1M async_gens 94.1M dictkeys 42.9M unicode_writers 1.9M contexts 511282 futureiters 495349 Some observations:
-
Most allocations are of type
int(via_PyLong_New). There is already a freelist for compacts ints that is working well (the ratio allocations/freelist is about 1:4). There is a large number of allocations with 2 or 3 digits (not covered by the freelist). So perhaps extending the freelist to cover ints with digits of size 2 (and 3) is worthwhile. Note that most hash values are ints with 2 digits. There are still some allocations of ints with 1 digit. Perhaps the freelist size can be increased, or bulk allocation of freelist objects (see Use a principled, and consistent, implementation of freelists. faster-cpython/ideas#132) -
Also high in the number of allocations are iterators (tuple_iter, list_iter, range_iterator, PySeqIter_new). Adding freelists is relatively easy. Perhaps we can combine the freelist for these iterators (we then need to update the type, but otherwise they can be shared). A prototype of a shared freelist for different iterators is in main...eendebakpt:cpython:iter_freelists
For the iterators the freelist size can probably be small. -
There are many allocations for types
builtin_function_or_method,generator,methodandfunction. For themethodadding a freelist is standard (inObjects/classobject.c). Thebuiltin_function_or_methodhappens often (for example a new object of this type is generated when for a listx=[1,2]one callsx.append). The adaptive interpreter seems to reduce the number ofbuiltin_function_or_methodobjects significantly, but still we could add a freelist. This requires some thought, as thePyCMethod_Newcan either allocate for aPyCMethodObjector aPyCFunctionObject, see.cpython/Objects/methodobject.c
Lines 81 to 105 in 71de839
Thefunctionandgeneratorobjects don't seem to fit standard freelist at first glance. -
The
StopIterationis in the top stats. Seems like a good candidate for a freelist, together withIndexError. The implementation (inObjects/exceptions.c) uses macros to define several variations of exceptions. Maybe they can be combined in a freelist, but this requires some more thinking. -
There is the
_safe_keyobject showing up. This is probably from pprint. Is that a performance bottleneck? Maybe not, it is a python class so overhead of allocation is probably small. Not sure which benchmark is triggering this one -
tupleandlistare still allocated a lot. However, the 8 milliontupleallocations seem okay with 625 million freelist results fromtuple! -
There are some objects specific for pyperformance benchmarks (e.g. the
Vectorclass from bm_raytrace andGVectorclass from bm_chaos). AlsoFractionis there. Perhaps we can create a freelist for thePyType_GenericAllocbased on the size? Code is here: https://github.com/python/cpython/blob/71de839ec987bb67b98fcfecfc687281841a713c/Objects/typeobject.c#L2213C1-L2213C21? -
For lists we can use a size based freelist (just as for tuple). The reason for doing this would be to avoid having to allocate/deallocate the space for the list items on each freelist pop/push. Data suggest that most list allocations happen for < 20 items (see figure below). One issue with lists is that they can be resized. So perhaps we are allocating many lists of small size, but when deallocating the lists can be larger.
Reacted by Ken Jin, Maxim Martynov, Erlend E. Aasland, Michael Droettboom and Mikhail Efimov-
Wow, excellent investigative work!
- changed the title
[-]Use freelist for range and iter objects[/-][+]Use freelist for range object, iterator objects and other often used objects[/+]on Jan 7, 2025 - added a commit that references this issue
on Jun 7, 2025 Closing as the most important PRs have been merged. There are still a couple open, they can be decided upon by a core dev (probably after rebasing at this stage).
Feature or enhancement
Proposal:
We can add freelists for the
rangeobject and various iter objects to improve performance. Using the new methods from #121934 the amount of code needed for adding a freelist is quite small. A prototype implementation is here:main...eendebakpt:cpython:iter_freelists
main...eendebakpt:cpython:range_freelist
@markshannon In faster-cpython/ideas#132 (comment) you noted that freelists should be used for all types. Is adding freelists in a similar style to the already existing freelists a good approach? We could also try to make a more generic construction (for example inside
PyObject_New/PyObject_Free), but that would have a much larger impact and I cannot oversee all consequences.The freelists from the prototype improve performance of
rangein microbenchmarks:Benchmark script
Allocations from freelist 2,004,971,371 39.8%
Frees to freelist 2,005,350,418
Allocations 3,034,877,938 60.2%
Allocations to 512 bytes 3,008,791,812 59.7%
Allocations to 4 kbytes 18,648,072 0.4%
Allocations over 4 kbytes 7,438,054 0.1%
Frees 3,142,033,922
Allocations from freelist 2,064,126,652 40.8%
Frees to freelist 2,064,499,538
Allocations 2,989,239,063 59.2%
Allocations to 512 bytes 2,963,207,194 58.6%
Allocations to 4 kbytes 18,596,157 0.4%
Allocations over 4 kbytes 7,435,712 0.1%
Frees 3,096,349,170