list() uses slightly more memory than list comprehension

by

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

More Related Contents:

  1. How to create the following lists with list comprehensions? [closed]
  2. Find a unique element in a list [closed]
  3. What does “list comprehension” and similar mean? How does it work and how can I use it?
  4. List comprehension on a nested list?
  5. Why does id({}) == id({}) and id([]) == id([]) in CPython?
  6. if else in a list comprehension [duplicate]
  7. Transpose a matrix in Python [duplicate]
  8. Why is a list comprehension so much faster than appending to a list?
  9. Why can tuples contain mutable items?
  10. List comprehension vs generator expression’s weird timeit results?
  11. Python string with space and without space at the end and immutability
  12. How to return a subset of a list that matches a condition [duplicate]
  13. Tuple or list when using ‘in’ in an ‘if’ clause?
  14. Python using enumerate inside list comprehension
  15. How to remove multiple items from a list in just one statement?
  16. List with duplicated values and suffix
  17. Comprehension on a nested iterables?
  18. remove None value from a list without removing the 0 value
  19. Why do two identical lists have a different memory footprint?
  20. How can I use list comprehensions to process a nested list?
  21. Why does list ask about __len__?
  22. How exactly is Python Bytecode Run in CPython?
  23. Are list comprehensions syntactic sugar for `list(generator expression)` in Python 3?
  24. sum each value in a list of tuples
  25. Duplicate elements in a list [duplicate]
  26. flatten list of list through list comprehension
  27. Converting List Comprehensions to For Loops in Python
  28. Why does creating a list from a list make it larger?
  29. Optimal method to find the max of sublist items within list
  30. deque.popleft() and list.pop(0). Is there performance difference?

Leave a Comment