Wandering Thoughts archives

2011-06-05

A subtle difference between tuples and lists in CPython

There are of course any number of differences between tuples and lists, but today I discovered a subtle and interesting one: tuples have a non-zero __itemsize__, and lists do not. Or to put it in a more comprehensible way, in CPython tuples are variable-size blobs and lists are not.

Wait, what? Lists are clearly variable sized things, in fact more variable sized that tuples since a tuple is immutable once created. It turns out that that difference is exactly why tuples are variable-sized blobs and lists are not.

Both lists and tuples must store a variable-sized array of items somewhere. As covered in HowSlotsWorkI, the CPython runtime allows the fundamental blob of storage for a Python object instance to have a variable amount of additional data tacked on the end. However, you cannot resize an instance blob once it has been created. Because tuples are immutable, the size of their item array doesn't change once a tuple instance has been created and they can directly store their item array on the end of their C-level blob, saving a separate memory allocation and a pointer. However, lists can and do change the size of their item array after creation and so must store their item array in a separate chunk of storage so they can freely resize it as the particular list grows and shrinks.

One of the consequences of this is the traditional one: you can't subclass tuple with anything that has a non-empty __slots__.

(In theory this makes tuples slightly more memory efficient than lists. In practice the differences are small enough that they're unlikely to matter unless you have a huge number of items.)

PS: as you might expect, dict is another variable sized Python thing that has a zero __itemsize__.

python/TupleListSlots written at 00:55:03; Add Comment


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

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