Size of List in Memory

Size of list in memory

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

Memory Size of list python

Lists always display this pattern if they are grown with append.

A key point to understand, sys.getsizeof doesn't account for the objects referenced in the list, only the size of the list object itself. Now, Python list objects are implemented as array lists underneath the hood, so essentially there is a PyObject header (like, 16 byte overhead or some such), then a primitive array of PyObject pointers (which is why they can be heterogenous, and reference themselves).

This underlying array is overallocated, and it's re-sized in such a way to guarantee amortized constant-time .append operations.
Stated another way, Python list objects have amortized constant-time .append, so doing something like for x in range(N): my_list.append(0) is a linear time operation, because the underlying buffer is not re-allocated on each iteration.

Look, you see the same pattern with any object, like None:

In [24]: import sys
    ...:
    ...: memory_size = {}
    ...:
    ...: for length in range(50):
    ...:     lst = []
    ...:     for length_loop in range(length):
    ...:         lst.append(None)
    ...:     memory_size[length] = sys.getsizeof(lst)
    ...:

In [25]: memory_size
Out[25]:
{0: 72,
 1: 104,
 2: 104,
 3: 104,
 4: 104,
 5: 136,
 6: 136,
 7: 136,
 8: 136,
 9: 200,
 10: 200,
 11: 200,
 12: 200,
 13: 200,
 14: 200,
 15: 200,
 16: 200,
 17: 272,
 18: 272,
 19: 272,
 20: 272,
 21: 272,
 22: 272,
 23: 272,
 24: 272,
 25: 272,
 26: 352,
 27: 352,
 28: 352,
 29: 352,
 30: 352,
 31: 352,
 32: 352,
 33: 352,
 34: 352,
 35: 352,
 36: 440,
 37: 440,
 38: 440,
 39: 440,
 40: 440,
 41: 440,
 42: 440,
 43: 440,
 44: 440,
 45: 440,
 46: 440,
 47: 536,
 48: 536,
 49: 536}

And just to convince you, here is your self-referening list:

In [26]: import sys
    ...:
    ...: memory_size = {}
    ...:
    ...: for length in range(50):
    ...:     lst = []
    ...:     for length_loop in range(length):
    ...:         lst.append(lst)
    ...:     memory_size[length] = sys.getsizeof(lst)
    ...:

In [27]: memory_size
Out[27]:
{0: 72,
 1: 104,
 2: 104,
 3: 104,
 4: 104,
 5: 136,
 6: 136,
 7: 136,
 8: 136,
 9: 200,
 10: 200,
 11: 200,
 12: 200,
 13: 200,
 14: 200,
 15: 200,
 16: 200,
 17: 272,
 18: 272,
 19: 272,
 20: 272,
 21: 272,
 22: 272,
 23: 272,
 24: 272,
 25: 272,
 26: 352,
 27: 352,
 28: 352,
 29: 352,
 30: 352,
 31: 352,
 32: 352,
 33: 352,
 34: 352,
 35: 352,
 36: 440,
 37: 440,
 38: 440,
 39: 440,
 40: 440,
 41: 440,
 42: 440,
 43: 440,
 44: 440,
 45: 440,
 46: 440,
 47: 536,
 48: 536,
 49: 536}

The discrepencies in the individual size come down to things like Python version and system architecture (on a 32-bit system, pointers are 4 bytes instead of 8, for example, and different Python versions are free to change implementation details like the size of an empty list). Note, the above was run on Python 3.7, if I use another environemnt:

(base) juanarrivillaga@173-11-109-137-SFBA ~ % python -c "import sys; print(f'{sys.version}\nEmpty List Size: {sys.getsizeof([])}')"
3.8.1 (default, Jan  8 2020, 16:15:59)
[Clang 4.0.1 (tags/RELEASE_401/final)]
Empty List Size: 56

Difference between list and NumPy array memory size

getsizeof is not a good measure of memory use, especially with lists. As you note the list has a buffer of pointers to objects elsewhere in memory. getsizeof notes the size of the buffer, but tells us nothing about the objects.

With

In [66]: list(range(4))
Out[66]: [0, 1, 2, 3]

the list has its basic object storage, plus the buffer with 4 pointers (plus some growth room). The numbers are stored else where. In this case the numbers are small, and already created and cached by the interpreter. So their storage doesn't add anything. But larger numbers (and floats) are created with each use, and take up space. Also a list can contain anything, such as pointers to other lists, or strings or dicts, or what ever.

In [67]: arr = np.array([i for i in range(4)])   # via list
In [68]: arr
Out[68]: array([0, 1, 2, 3])
In [69]: np.array(range(4))            # more direct
Out[69]: array([0, 1, 2, 3])
In [70]: np.arange(4)
Out[70]: array([0, 1, 2, 3])           # faster

arr too has a basic object storage with attributes like shape and dtype. It too has a databuffer, but for a numeric dtype like this, that buffer has actual numeric values (8 byte integers), not pointers to Python integer objects.

In [71]: arr.nbytes
Out[71]: 32

That data buffer only takes 32 bytes - 4*8.

For this small example it's not surprising that getsizeof returns the same thing. The basic object storage is more significant than where the 4 values are stored. It's when working with 1000's of values, and multidimensional arrays that memory use is significantly different.

But more important is the calculation speeds. With an array you can do things like arr+1 or arr.sum(). These operate in compiled code, and are quite fast. Similar list operations have to iterate, at slow Python speeds, though the pointers, fetching values etc. But doing the same sort of iteration on arrays is even slower.

As a general rule, if you start with lists, and do list operations such as append and list comprehensions, it's best to stick with them.

But if you can create the arrays once, or from other arrays, and then use numpy methods, you'll get 10x speed improvements. Arrays are indeed faster, but only if you use them in the right way. They aren't a simple drop in substitute for lists.

What is the memory size of an ArrayList in Java

You can use something like Runtime.getRuntime().totalMemory() and its counterpart Runtime.getRuntime().freeMemory() to get an educated guess, but that doesn't account for objects that are GC'ed between calls.

How Big can a Python List Get?

According to the source code, the maximum size of a list is PY_SSIZE_T_MAX/sizeof(PyObject*).

PY_SSIZE_T_MAX is defined in pyport.h to be ((size_t) -1)>>1

On a regular 32bit system, this is (4294967295 / 2) / 4 or 536870912.

Therefore the maximum size of a python list on a 32 bit system is 536,870,912 elements.

As long as the number of elements you have is equal or below this, all list functions should operate correctly.

How allocation of memory for `list` works in Python? Why size of list is not same as combined sum of its objects?

Lists in python doesn't contain the object itself. They just store the reference to the object. Hence, the size of object at any index is not proportional to size of the list. For example:

>>> import sys
>>> my_list = [10, "my_str", {}]

>>> sys.getsizeof(my_list[0])  # it is memory used by int
24
>>> sys.getsizeof(my_list[1])  # it is memory used by str
43
>>> sys.getsizeof(my_list[2])  # it is memory used by dict
280

>>> sys.getsizeof(my_list)  # and it is memory used by your list object itself
96

Here, size of my_list is 96 Bytes, whereas my_list[2] alone is 280 Bytes.

---

Answering your questions:

The size of a[0] is 28. When I multiply 28*3=84, how size of list a is 88?

As I mentioned above, list just holds the reference to objects, not the objects itself. Hence the memory used by list and memory used by each of it's objects are not going to be same.

When I subtract address of a[1] - a[0] i.e. 10914528 -10914496 = 32 How I am getting 28 when I use size of function?

a[1] and a[0] refer two independent objects, memory allocation of which is not guaranteed to be contagious.

id of a is 139954746492104. Then how id of a[0] is 10914496?

Same as above. Because both display two independent objects.

Why do tuples take less space in memory than lists?

I assume you're using CPython and with 64bits (I got the same results on my CPython 2.7 64-bit). There could be differences in other Python implementations or if you have a 32bit Python.

Regardless of the implementation, lists are variable-sized while tuples are fixed-size.

So tuples can store the elements directly inside the struct, lists on the other hand need a layer of indirection (it stores a pointer to the elements). This layer of indirection is a pointer, on 64bit systems that's 64bit, hence 8bytes.

But there's another thing that lists do: They over-allocate. Otherwise list.append would be an O(n) operation always - to make it amortized O(1) (much faster!!!) it over-allocates. But now it has to keep track of the allocated size and the filled size (tuples only need to store one size, because allocated and filled size are always identical). That means each list has to store another "size" which on 64bit systems is a 64bit integer, again 8 bytes.

So lists need at least 16 bytes more memory than tuples. Why did I say "at least"? Because of the over-allocation. Over-allocation means it allocates more space than needed. However, the amount of over-allocation depends on "how" you create the list and the append/deletion history:

>>> l = [1,2,3]
>>> l.__sizeof__()
64
>>> l.append(4)  # triggers re-allocation (with over-allocation), because the original list is full
>>> l.__sizeof__()
96

>>> l = []
>>> l.__sizeof__()
40
>>> l.append(1)  # re-allocation with over-allocation
>>> l.__sizeof__()
72
>>> l.append(2)  # no re-alloc
>>> l.append(3)  # no re-alloc
>>> l.__sizeof__()
72
>>> l.append(4)  # still has room, so no over-allocation needed (yet)
>>> l.__sizeof__()
72

Images

I decided to create some images to accompany the explanation above. Maybe these are helpful

This is how it (schematically) is stored in memory in your example. I highlighted the differences with red (free-hand) cycles:

That's actually just an approximation because int objects are also Python objects and CPython even reuses small integers, so a probably more accurate representation (although not as readable) of the objects in memory would be:

Useful links:

• tuple struct in CPython repository for Python 2.7
• list struct in CPython repository for Python 2.7
• int struct in CPython repository for Python 2.7

Note that __sizeof__ doesn't really return the "correct" size! It only returns the size of the stored values. However when you use sys.getsizeof the result is different:

>>> import sys
>>> l = [1,2,3]
>>> t = (1, 2, 3)
>>> sys.getsizeof(l)
88
>>> sys.getsizeof(t)
72

There are 24 "extra" bytes. These are real, that's the garbage collector overhead that isn't accounted for in the __sizeof__ method. That's because you're generally not supposed to use magic methods directly - use the functions that know how to handle them, in this case: sys.getsizeof (which actually adds the GC overhead to the value returned from __sizeof__).

What are the memory requirements for large python list?

There's a handy function sys.getsizeof() (since Python 2.6) that helps with this:

>>> import sys
>>> sys.getsizeof(1)  # integer
12
>>> sys.getsizeof([]) # empty list
36
>>> sys.getsizeof(()) # empty tuple
28
>>> sys.getsizeof((1,))  # tuple with one element
32

From that you can see that each integer takes up 12 bytes, and the memory for each reference in a list or tuple is 4 bytes (on a 32-bit machine) plus the overhead (36 or 28 bytes respectively).

If your result has tuples of length 17 with integers, then you'd have 17*(12+4)+28 or 300 bytes per tuple. The result itself is a list, so 36 bytes plus 4 per reference. Find out how long the list will be (call it N) and you have 36+N*(4+300) as the total bytes required.

Edit: There's one other thing that could significantly affect that result. Python creates new integer objects as required for most integer values, but for small ones (empirically determined to be the range [-5, 256] on Python 2.6.4 on Windows) it pre-creates them all and re-uses them. If a large portion of your values are less than 257 this would significantly reduce the memory consumption. (On Python 257 is not 257+0 ;-)).

Exceeding the size of lists in python

It's a more complex algorithm, perhaps technically not counting as the sieve, but one approach is to not remove all multiples of a given prime at once, but queue the next multiple (along with the prime). This could be used in a generator implementation. The queue will still end up containing a lot of (multiples of) primes, but not as many as by building then filtering a list.

First few steps done manually, to show the principle...

• 2 is prime - yield and queue (4, 2)
• 3 is prime - yield and queue (6, 3)
• 4 is composite - replace (4, 2) with (6, 2) in the queue
• 5 is prime - yield and queue (10, 5)
• 6 is composite - replace (6, 2) with (8, 2) and (6, 3) with (9, 3)

Note - the queue isn't a FIFO. You will always be extracting the tuples with the lowest first item, but new/replacement tuples don't (usually) have the highest first item and (as with 6 above) there will be duplicates.

To handle the queue efficiently in Python, I suggest a dictionary (ie hashtable) keyed by the first item of the tuple. The data is a set of second item values (original primes).

As suggested elsewhere, test with small targets before trying for the big one. And don't be too surprised if you fail. It may still be that you need too many heap-allocated large integers at one time (in the queue) to complete the solution.

---

Related Topics