How Big Can a Python List Get

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.

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.

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

Is there a limit to how many items a list can contain?

Yes, there is a limit, sys.maxsize is the maximum number of entries a list can contain:

The largest positive integer supported by the platform’s Py_ssize_t type, and thus the maximum size lists, strings, dicts, and many other containers can have.

How do I get the number of elements in a list (length of a list) in Python?

The len() function can be used with several different types in Python - both built-in types and library types. For example:

>>> len([1, 2, 3])
3

Memory errors and list limits?

First off, see How Big can a Python Array Get? and Numpy, problem with long arrays

Second, the only real limit comes from the amount of memory you have and how your system stores memory references. There is no per-list limit, so Python will go until it runs out of memory. Two possibilities:

1. If you are running on an older OS or one that forces processes to use a limited amount of memory, you may need to increase the amount of memory the Python process has access to.
2. Break the list apart using chunking. For example, do the first 1000 elements of the list, pickle and save them to disk, and then do the next 1000. To work with them, unpickle one chunk at a time so that you don't run out of memory. This is essentially the same technique that databases use to work with more data than will fit in RAM.

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

Time Complexity dealing with List of size 10**6

By iterating on your data backwards, as suggested by @Mad Physicist, you can get an algorithm needing much less memory, and also being faster:

def get_total(data):
    tot = sum(data)
    smallest_tail = deque()
    no_discount = []
    i = len(data) - 1 # manually handle the index
    for x in reversed(data):
        while smallest_tail:
            s = smallest_tail[-1]
            if s >= x: # s won't be next smaller for anyone because of x
                smallest_tail.pop()
            else:
                tot -= s
                break
        if not smallest_tail:
            no_discount.append(i)
        smallest_tail.append(x)
        i -= 1
    return tot, list(reversed(no_discount))

comparing with your current solution (on my machine):

:data = list(np.array(np.random.randint(1, 10**5, 10**6, dtype='int64')))
:get_total_dz(data) == get_total(data)
True
:%timeit r = get_total_dz(data) # yours, replacing 'len(stack) > 0' with 'stack'
672 ms ± 6.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
:%timeit r = get_total(data) # mine
435 ms ± 2.29 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Create a list with initial capacity in Python

Warning: This answer is contested. See comments.

def doAppend( size=10000 ):
    result = []
    for i in range(size):
        message= "some unique object %d" % ( i, )
        result.append(message)
    return result

def doAllocate( size=10000 ):
    result=size*[None]
    for i in range(size):
        message= "some unique object %d" % ( i, )
        result[i]= message
    return result

Results. (evaluate each function 144 times and average the duration)

simple append 0.0102
pre-allocate  0.0098

Conclusion. It barely matters.

Premature optimization is the root of all evil.

---

Related Topics