How is tuple implemented in CPython?

Question

I've been trying to learn how CPython is implemented under the scenes. It's great that Python is high level, but I don't like treating it like a black box.

With that in mind, how are tuples implemented? I've had a look at the source (tupleobject.c), but it's going over my head.

I see that PyTuple_MAXSAVESIZE = 20 and PyTuple_MAXFREELIST = 2000, what is saving and the "free list"? (Will there be a performance difference between tuples of length 20/21 or 2000/2001? What enforces the maximum tuple length?)

Answer 1

As a caveat, everything in this answer is based on what I've gleaned from looking over the implementation you linked.

It seems that the standard implementation of a tuple is simply as an array. However, there are a bunch of optimizations in place to speed things up.

First, if you try to make an empty tuple, CPython instead will hand back a canonical object representing the empty tuple. As a result, it can save on a bunch of allocations that are just allocating a single object.

Next, to avoid allocating a bunch of small objects, CPython recycles memory for many small lists. There is a fixed constant (PyTuple_MAXSAVESIZE) such that all tuples less than this length are eligible to have their space reclaimed. Whenever an object of length less than this constant is deallocated, there is a chance that the memory associated with it will not be freed and instead will be stored in a "free list" (more on that in the next paragraph) based on its size. That way, if you ever need to allocate a tuple of size n and one has previously been allocated and is no longer in use, CPython can just recycle the old array.

The free list itself is implemented as an array of size PyTuple_MAXSAVESIZE storing pointers to unused tuples, where the nth element of the array points either to NULL (if no extra tuples of size n are available) or to a reclaimed tuple of size n. If there are multiple different tuples of size n that could be reused, they are chained together in a sort of linked list by having each tuple's zeroth entry point to the next tuple that can be reused. (Since there is only one tuple of length zero ever allocated, there is never a risk of reading a nonexistent zeroth element). In this way, the allocator can store some number of tuples of each size for reuse. To ensure that this doesn't use too much memory, there is a second constant PyTuple_MAXFREELIST that controls the maximum length of any of these linked lists within any bucket. There is then a secondary array of length PyTuple_MAXSAVESIZE that stores the length of the linked lists for tuples of each given length so that this upper limit isn't exceeded.

All in all, it's a very clever implementation!

Answer 2

Because in the course of normal operations Python will create and destroy a lot of small tuples, Python keeps an internal cache of small tuples for that purpose. This helps cut down on a lot of memory allocation and deallocation churn. For the same reasons small integers from -5 to 255 are interned (made into singletons).

The PyTuple_MAXSAVESIZE definition controls at the maximum size of tuples that qualify for this optimization, and the PyTuple_MAXFREELIST definition controls how many of these tuples keeps around in memory. When a tuple of length < PyTuple_MAXSAVESIZE is discarded, it is added to the free list if there is still room for one (in tupledealloc), to be re-used when Python creates a new small tuple (in PyTuple_New).

Python is being a little clever about how it stores these; for each tuple of length > 0, it'll reuse the first element of each cached tuple to chain up to PyTuple_MAXFREELIST tuples together into a linked list. So each element in the free_list array is a linked list of Python tuple objects, and all tuples in such a linked list are of the same size. The only exception is the empty tuple (length 0); only one is ever needed of these, it is a singleton.

So, yes, for tuples over length PyTuple_MAXSAVESIZE python is guaranteed to have to allocate memory separately for a new C structure, and that could affect performance if you create and discard such tuples a lot.

If you want to understand Python C internals, I do recommend you study the Python C API; it'll make it easier to understand the various structures Python uses to define objects, functions and methods in C.