Size of a Python list in memory

Question

I just experimented with the size of python data structures in memory. I wrote the following snippet:

import sys
lst1=[]
lst1.append(1)
lst2=[1]
print(sys.getsizeof(lst1), sys.getsizeof(lst2))

I got the following outputs on the following configurations:

• Windows 7 64bit, Python3.1: 52 40 (so lst1 has 52 bytes and lst2 has 40 bytes)
• Ubuntu 11.4 32bit with Python3.2: output is 48 32
• Ubuntu 11.4 32bit Python2.7: 48 36

Can anyone explain to me why the two sizes differ although both are lists containing a 1?

In the python documentation for the getsizeof function I found the following:

...adds an additional garbage collector overhead if the object is managed by the garbage collector.

Could this be the case in my little example?

Ader

lists aren't allocated incrementally, but in "chunks" (and the chunks get bigger as the list gets bigger). this is needed so that the amortised cost of appending data is low. so i guess the allocator is working differently in the two cases. but really, why do you care so much about how lists are allocated? uses sys.getsizeof() if you need to know teh size of something. – Jadeite

@andrew cooke: Please make that an answer, it's pretty much the whole deal. – Executive

@andrew-cooke I'm just curious about low level implementation and will not use this in a real world problem. – Ader

@halex: you could read the implementation, Python is open source. – Lightheaded

@Jochen: I was curious so I did that. See my answer below – Rowena

@riaz-rizvi I don't know why you deleted your answer but it was pretty good and clear. – Laudianism

Answer 1

Here's a fuller interactive session that will help me explain what's going on (Python 2.6 on Windows XP 32-bit, but it doesn't matter really):

>>> import sys
>>> sys.getsizeof([])
36
>>> sys.getsizeof([1])
40
>>> lst = []
>>> lst.append(1)
>>> sys.getsizeof(lst)
52
>>> 

Note that the empty list is a bit smaller than the one with [1] in it. When an element is appended, however, it grows much larger.

The reason for this is the implementation details in Objects/listobject.c, in the source of CPython.

Empty list

When an empty list [] is created, no space for elements is allocated - this can be seen in PyList_New. 36 bytes is the amount of space required for the list data structure itself on a 32-bit machine.

List with one element

When a list with a single element [1] is created, space for one element is allocated in addition to the memory required by the list data structure itself. Again, this can be found in PyList_New. Given size as argument, it computes:

nbytes = size * sizeof(PyObject *);

And then has:

if (size <= 0)
    op->ob_item = NULL;
else {
    op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);
    if (op->ob_item == NULL) {
        Py_DECREF(op);
        return PyErr_NoMemory();
    }
    memset(op->ob_item, 0, nbytes);
}
Py_SIZE(op) = size;
op->allocated = size;

So we see that with size = 1, space for one pointer is allocated. 4 bytes (on my 32-bit box).

Appending to an empty list

When calling append on an empty list, here's what happens:

• PyList_Append calls app1
• app1 asks for the list's size (and gets 0 as an answer)
• app1 then calls list_resize with size+1 (1 in our case)
• list_resize has an interesting allocation strategy, summarized in this comment from its source.

Here it is:

/* This over-allocates proportional to the list size, making room
* for additional growth.  The over-allocation is mild, but is
* enough to give linear-time amortized behavior over a long
* sequence of appends() in the presence of a poorly-performing
* system realloc().
* The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
*/
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

/* check for integer overflow */
if (new_allocated > PY_SIZE_MAX - newsize) {
    PyErr_NoMemory();
    return -1;
} else {
    new_allocated += newsize;
}

Let's do some math

Let's see how the numbers I quoted in the session in the beginning of my article are reached.

So 36 bytes is the size required by the list data structure itself on 32-bit. With a single element, space is allocated for one pointer, so that's 4 extra bytes - total 40 bytes. OK so far.

When app1 is called on an empty list, it calls list_resize with size=1. According to the over-allocation algorithm of list_resize, the next largest available size after 1 is 4, so place for 4 pointers will be allocated. 4 * 4 = 16 bytes, and 36 + 16 = 52.

Indeed, everything makes sense :-)

Rowena

That's the standard allocation strategy for List.append() across all programming languages / libraries that I've encountered. I think I would have guessed this is the cause without reading your answer (but now I have read it, so I can't really know). Anyway, nice detailed answer. – Yseult

@ripper234: yes, the allocation strategy is common, but I wonder about the growth pattern itself. Textbook examples of amortized-linear runtime are usually mentioning powers-of-2. This seems like an unusual pattern, that still satisfies the formulae for linear behavior - I find this very interesting – Rowena

interestingly the comment about "the growth pattern is:" doesn't actually describe the strategy in the code. it starts with a base over-allocation of 3 or 6 depending on which side of 9 the new size is, then it grows the over allocation by 1 every 8. (I suspect that comment predates the current version of the over-allocation strategy). – Whatley

@teepark: could you elaborate? i ran some back-of-the-envelope numbers and imho the code works according to the comment. Do keep in mind that once over-allocated to, say 8, the next "newsize" request will be for 9. – Rowena

yes you're right. what I didn't get was that it is essentially tracing the realloc(3)s that take place from appends in a loop. – Whatley

So, should I be using a numpy column_stack or something to append lists when loading files, instead of .append()? For better performance? – Ineffable

Two things not very clear. (a) Why is the size of an integer (28) larger than the size of a float or zero (24)? (b) Buttype(0) is an int, while the size is that of a float? – Laudianism

Answer 2

You're looking at how lists are allocated (and I think maybe you just wanted to see how big things were - in that case, use sys.getsizeof())

When something is added to a list, one of two things can happen:

1. The extra item fits in spare space.

2. Extra space is needed, so a new list is made, and the contents copied across, and the extra thing added.

Since (2) is expensive (copying things, even pointers, takes time proportional to the number of things to be copied, so grows as lists get large) we want to do it infrequently. So instead of just adding a little more space, we add a whole chunk. Typically the size of the amount added is similar to what is already in use - that way the maths works out that the average cost of allocating memory, spread out over many uses, is only proportional to the list size.

So what you are seeing is related to this behaviour. I don't know the exact details, but I wouldn't be surprised if [] or [1] (or both) are special cases, where only enough memory is allocated (to save memory in these common cases), and then appending does the "grab a new chunk" described above that adds more.

But I don't know the exact details - this is just how dynamic arrays work in general. The exact implementation of lists in Python will be finely tuned so that it is optimal for typical python programs. So all I am really saying is that you can't trust the size of a list to tell you exactly how much it contains - it may contain extra space, and the amount of extra free space is difficult to judge or predict.

A neat alternative to this is to make lists as (value, pointer) pairs, where each pointer points to the next tuple. In this way you can grow lists incrementally, although the total memory used is higher. That is a linked list (what Python uses is more like a vector or a dynamic array).

Eli's excellent answer explains that both [] and [1] are allocated exactly, but that appending to [] allocates an extra chunk. The comment in the code is what I am saying above (this is called "over-allocation" and the amount is porportional to what we have so that the average ("amortised") cost is proportional to size).

Jadeite

Answer 3

Here's a quick demonstration of the list growth pattern. Changing the third argument in range() will change the output so it doesn't look like the comments in listobject.c, but the result when simply appending one element seem to be perfectly accurate.

allocated = 0
for newsize in range(0,100,1):
    if (allocated < newsize):
        new_allocated = (newsize >> 3) + (3 if newsize < 9 else 6)
        allocated = newsize + new_allocated;
    print newsize, allocated

Waldenburg

Answer 4

formula changes based on the system architecture (size-36)/4 for 32 bit machines and (size-64)/8 for 64 bit machines

36,64 - size of an empty list based on machine 4,8 - size of a single element in the list based on machine

Ortiz