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.)