Why do Python list sizes in memory not match documentation?

Question

I've been trying to gain a better understanding of how Python allocates memory for lists when the list is being extended by appending. This question covers the basics well and explains the memory increments increase in size as the length of the list increases. This article is an explaination of the source code that can be found here.

I want to ask about this explanation:

/* 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().
 * Add padding to make the allocated size multiple of 4.
 * The growth pattern is:  0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...
 * 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.
 */
new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;
/* Do not overallocate if the new size is closer to overallocated size
 * than to the old size.
 */

And specifically, this calculation:

new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;

My understanding of this calculation is the new memory allocation will be equal to the newsize (the current size triggering the increase) + the newsize right rolled three bits (an effective divide by eight) + 6. This is then ANDed with the 1's complement of 3 so the last two bits are forced to zero to make the value divisible by 4.

I used this code to generate my lists and report the sizes:

a = [i for i in range(108)]
print(sys.getsizeof(a))  # 920 bytes

b = [i for i in range(109)]
print(sys.getsizeof(b))  # 1080 bytes

At 109 elements the resize is triggered an newsize now equals 928 bytes

The calculation above should look like this:

1048 bytes is less than the reported size of 1060 bytes.

The documentation states that this process may not work well with small lists so I tried a bigger list. I won't reproduce this in binary.

a = [i for i in range(10640)]
print(sys.getsizeof(a))  # 85176 bytes

b = [i for i in range(10641)]
print(sys.getsizeof(b))  # 95864 bytes

[85184 + (86184 >> 3) + 6] = 95838 bytes

This will drop to 95836 when the "& ~3" is applied. Again, short of the 95864 reported.

Why is the reported resize greater then the calculated resize?

Why don't you try triggering a resize by using append or the likes? Two list comprehensions aren't really a great comparision (Plus there probably is more code related to the list comprehension that's not in the file you are looking at). — Abdul Aziz Barkat
– Abdul Aziz Barkat, Commented Mar 22, 2024 at 9:27
I did. That's how I found the crossover points. The code provided is just shorter than "for i in range(1000): a.append(i)" but it gives the same results. — Andrew H
– Andrew H, Commented Mar 23, 2024 at 1:28

Homer512 · Accepted Answer · 2024-03-22 10:16:16Z

0

I believe your mistake is that you do this computation on bytes. You have to do it on elements instead and then add the overhead of an empty list object.

Here is a quick simulation of [i for i in range(109)]:

size = 0
used = 0
for _ in range(109):
    used += 1
    if used > size:
        size = (used + ((used >> 3) + 6)) & ~3

print(f"allocated array size: {size * 8}")
print(f"full list size: {size * 8 + sys.getsizeof([])}")
print(f"should be the same as {sys.getsizeof([i for i in range(109)])}")

allocated array size: 1024

full list size: 1080

should be the same as 1080

The factor of 8 is sizeof(void*) in C and would be 4 on a 32 bit system.

edited Mar 22, 2024 at 10:16

answered Mar 22, 2024 at 10:08

Homer512

15.1k2 gold badges16 silver badges35 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Andrew H Over a year ago

Works perfectly. Thank you. This problem comes originally from this YouTube video (youtube.com/watch?v=fwxjMKBMR7s) comparing prime sieves and looking at the memory overheads. I suspect the comparison of array sizes may be off. Now I have a way of investigating. Thank you.

Collectives™ on Stack Overflow

Why do Python list sizes in memory not match documentation?

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related