Alex Rivera | Logout

Size of a Python list in memory

Asked 2011-08-30T17:29:01.260
95

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?

python python-3.x list
Edit
Report

2 Answers

176

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 l
answered 2011-08-30T17:49:35.213
11

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

answered 2011-08-30T17:44:32.100

Your Answer