Size of a Python list in memory

by

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 🙂

More Related Contents:

  1. How do you find min and max without using min and max function [duplicate]
  2. How to create the following lists with list comprehensions? [closed]
  3. Unable to use convert strings into integers for a for loop
  4. User input integer list [duplicate]
  5. how to unpack a tuple in this form (‘abc’, [20, 20])? [closed]
  6. Getting a map() to return a list in Python 3.x
  7. How to return dictionary keys as a list in Python?
  8. What do ellipsis […] mean in a list?
  9. Access multiple elements of list knowing their index
  10. Are lists thread-safe?
  11. Why is a list comprehension so much faster than appending to a list?
  12. Python 3 turn range to a list
  13. Getting only element from a single-element list in Python?
  14. Extending list returns None [duplicate]
  15. Check if all elements of a list are of the same type
  16. How can I generate a list of consecutive numbers?
  17. Print list of lists in separate lines
  18. Understand Python swapping: why is a, b = b, a not always equivalent to b, a = a, b?
  19. Why do I get “List index out of range” when trying to add consecutive numbers in a list using “for i in list”? [duplicate]
  20. Initializing 2D array in Python
  21. Best way to check if an item is present in a list of lists? [duplicate]
  22. How to apply a function to each sublist of a list in python?
  23. How do I return dictionary keys as a list in Python?
  24. Changing one dict changes all dicts in a list of dicts [duplicate]
  25. Appending to list in Python dictionary [duplicate]
  26. How to sort a list of strings in reverse order without using reverse=True parameter?
  27. Deleting consonants from a string in Python
  28. How does str.startswith really work?
  29. Skip elements on a condition based in a list comprehension in python
  30. Converting string to tuple without splitting characters

Leave a Comment