List() Uses Slightly More Memory Than List Comprehension

list() uses slightly more memory than list comprehension

I think you're seeing over-allocation patterns this is a sample from the source:

/* 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);

---

Printing the sizes of list comprehensions of lengths 0-88 you can see the pattern matches:

# create comprehensions for sizes 0-88
comprehensions = [sys.getsizeof([1 for _ in range(l)]) for l in range(90)]

# only take those that resulted in growth compared to previous length
steps = zip(comprehensions, comprehensions[1:])
growths = [x for x in list(enumerate(steps)) if x[1][0] != x[1][1]]

# print the results:
for growth in growths:
    print(growth)

Results (format is (list length, (old total size, new total size))):

(0, (64, 96)) 
(4, (96, 128))
(8, (128, 192))
(16, (192, 264))
(25, (264, 344))
(35, (344, 432))
(46, (432, 528))
(58, (528, 640))
(72, (640, 768))
(88, (768, 912))

---

The over-allocation is done for performance reasons allowing lists to grow without allocating more memory with every growth (better amortized performance).

A probable reason for the difference with using list comprehension, is that list comprehension can not deterministically calculate the size of the generated list, but list() can. This means comprehensions will continuously grow the list as it fills it using over-allocation until finally filling it.

It is possible that is will not grow the over-allocation buffer with unused allocated nodes once its done (in fact, in most cases it wont, that would defeat the over-allocation purpose).

list(), however, can add some buffer no matter the list size since it knows the final list size in advance.

---

Another backing evidence, also from the source, is that we see list comprehensions invoking LIST_APPEND, which indicates usage of list.resize, which in turn indicates consuming the pre-allocation buffer without knowing how much of it will be filled. This is consistent with the behavior you're seeing.

---

To conclude, list() will pre-allocate more nodes as a function of the list size

>>> sys.getsizeof(list([1,2,3]))
60
>>> sys.getsizeof(list([1,2,3,4]))
64

List comprehension does not know the list size so it uses append operations as it grows, depleting the pre-allocation buffer:

# one item before filling pre-allocation buffer completely
>>> sys.getsizeof([i for i in [1,2,3]]) 
52
# fills pre-allocation buffer completely
# note that size did not change, we still have buffered unused nodes
>>> sys.getsizeof([i for i in [1,2,3,4]]) 
52
# grows pre-allocation buffer
>>> sys.getsizeof([i for i in [1,2,3,4,5]])
68

List comprehension causes memory to exceed

You can use one for loop to achieve the output you wanted. Works for only even-sized lists.

a=[1,2,3,4,5,6]
n=len(a)//2
for x,y,i in zip(a[:n],a[n:][::-1],range(0,(2*n)+1,2)): #x=[1,2,3],y=[6,5,4],i=0,2,4
    a[i]=y
    a[i+1]=x
print(a)

output:

[6,1,5,2,4,3]

Generic code (works fine for both even-sized lists and odd-sized lists).

a=[1,2,3,4,5,6,7]
n=len(a)//2
last=a[n]
for x,y,i in zip(a[:n],a[n:][::-1],range(0,(2*n)+1,2)): #x=[1,2,3],y=[7,6,5],i=0,2,4
    a[i]=y
    a[i+1]=x
if len(a)%2 ==1:
    a[-1]=last

print(a)

OUTPUT:

[7, 1, 6, 2, 5, 3, 4]

NOTE : space complexity of zip is O(n).

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

Why do two identical lists have a different memory footprint?

When you write [None] * 10, Python knows that it will need a list of exactly 10 objects, so it allocates exactly that.

When you use a list comprehension, Python doesn't know how much it will need. So it gradually grows the list as elements are added. For each reallocation it allocates more room than is immediately needed, so that it doesn't have to reallocate for each element. The resulting list is likely to be somewhat bigger than needed.

You can see this behavior when comparing lists created with similar sizes:

>>> sys.getsizeof([None]*15)
184
>>> sys.getsizeof([None]*16)
192
>>> sys.getsizeof([None for _ in range(15)])
192
>>> sys.getsizeof([None for _ in range(16)])
192
>>> sys.getsizeof([None for _ in range(17)])
264

You can see that the first method allocates just what is needed, while the second one grows periodically. In this example, it allocates enough for 16 elements, and had to reallocate when reaching the 17th.

Why does the (deep) copy of a list consume more memory than the original list?

Lists use a resize policy that involves sometimes keeping spare space on the end to accommodate more elements, to guarantee amortized constant time appends. Some of your lists have more spare space on the end than others. Python doesn't promise how much spare space any list will have.

Difference in sizeof between a = [0] and a = [i for i in range(1)]

When the interpreter sees a = [0], it knows that it can build a list with just one element.

When it does a list comprehension, it first creates an empty list, then appends items as it goes. It doesn't know beforehand how big the list is going to be, even if it's iterating over something straightforward like range(1). So it tries to guess how much memory to allocate, and if it turns out that's not enough, it will have to dynamically increase the memory allocation. That's not cheap, so it may start with a generous guess.

Why do lists with the same data have different sizes?

When you append to a list, memory is over-allocated to the list for performance reasons so that multiple appends would not require corresponding reallocations of memory for the list which would slow the overall performance in the case of repeated appends.

The CPython source clearly describes this behaviour in a comment:

/* 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, ...
 * Note: new_allocated won't overflow because the largest possible value
 *       is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.
 */

In the other case, the list is constructed from a literal, and the size of the list reflects the size of the container itself and the references to each contained object.

The exact allocation behaviour may vary with other Python implementations (see list.append implementations for Jython and PyPy) and over-allocation is not guaranteed to exist.

Why is a sorted list bigger than an unsorted list

As Ignacio points out, this is due to Python allocating a bit more memory than required. This is done in order to perform O(1) .appends on lists.

sorted creates a new list out of the sequence provided, sorts it in place and returns it. To create the new list, Python extends an empty sized list with the one passed; that results in the observed over-allocation (which happens after calling list_resize). You can corroborate the fact that sorting isn't the culprit by using list.sort; the same algorithm is used without a new list getting created (or, as it's known, it's performed in-place). The sizes there, of course, don't differ.

It is worth noting that this difference is mostly present when:

• The original list was created with a list-comp (where, if space is available and the final append doesn't trigger a resize, the size is smaller).

• When list literals are used. There a PyList_New is created based on the number of values on the stack and no appends are made. Direct assigning to the underlying array is performed) which doesn't trigger any resizes and keeps size to its minimum:

So, with a list-comp:

l = [i for i in range(10)]

getsizeof(l)          # 192
getsizeof(sorted(l))  # 200

Or a list literal:

l = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

getsizeof(l)          # 144
getsizeof(sorted(l))  # 200

the sizes are smaller (more so with use of literals).

When creating through list, the memory is always over-allocated; Python knows the sizes and preempts future modifications by over-allocating a bit based on the size:

l = list(range(10))

getsizeof(l)          # 200
getsizeof(sorted(l))  # 200

So you get no observed difference in the sizes of the list(s).

---

As a final note, I must point out that this is behavior specific the C implementation of Python i.e CPython. It's a detail of how the language was implemented and as such, you shouldn't depend on it in any wacky way.

Jython, IronPython, PyPy and any other implementation might/might not have the same behavior.

---

Related Topics