Wandering Thoughts archives


How CPython optimizes allocations for some built-in types

Due to writing yesterday's entry, I got curious enough to go see how CPython handles the creation of some of the built-in types, and what sorts of optimizations it does. The necessary disclaimer is that this is for CPython 2.5.1; it doesn't necessarily apply to other versions of CPython, and it probably doesn't apply at all to other Python implementations (although I expect that they have their own tricks). Thus, the best use for this is as an illustration of the sorts of optimizations that can be done and are often done in this area.

First is a somewhat subtle advantage that built-in types have: there are specific bytecode operations for directly creating new tuples, lists, and dicts, so creating any of them doesn't require the regular name dispatch process. (Well, assuming that you use the direct syntax instead of perversely calling 'list()' or the like; if you invoke the type, it is a regular function invocation.)

After that there are a number of type-specific optimizations:

  • tuples have a fixed empty tuple that is returned for all uses of '()', and also have a cache of already-allocated C-level tuple structures for tuples with between 1 and 20 elements; each element count can have up to 2,000 such tuples ready to be used.

    (Since tuples are used heavily inside the interpreter, I assume that this optimization is a useful win.)

  • lists keep a 'recently released' list of up to 80 C-level list structures that can be reused without having to allocate memory. Since empty lists don't require anything besides the basic C-level list structure, this means that repeatedly allocating and releasing an empty list probably won't churn memory.

    You do churn memory if you are allocating and releasing non-empty lists, because the actual list of what's in the list is stored in a separate memory area that is allocated and released every time through.

  • dicts keep a 'recently released' list of up to 80 C-level dict structures. I believe that these are fully ready-to-go empty dictionaries, with everything necessary allocated.

  • plain (byte) strings specifically intern both the empty string and all single-character strings.

  • unicode strings intern the empty string and single-character strings that are in the Latin-1 range (duplicating what plain strings do). They also keep a 'recently released' list of up to 1024 C-level unicode string structures; unlike lists, the memory blob used for the actual string contents is not released if it's 9 Unicode characters or less.

A number of other built-in types have special allocation schemes and special caches, such as integers and floats, but that's beyond the scope of this entry. (Plus, I do not feel like skimming through the C implementation of every built in type.)

python/BuiltinCreationOptimizations written at 01:56:22; Add Comment

Page tools: See As Normal.
Login: Password:
Atom Syndication: Recent Pages, Recent Comments.

This dinky wiki is brought to you by the Insane Hackers Guild, Python sub-branch.