Why does the capacity of List in Python reduced to 10 instead of 8 after removing elements?

Question

Why capacity has reduced to 10 instead of 8?

#Do not remove the below import statement
import sys
'''This function provides the capacity, size and space left in the list.
You can invoke it to get the details of the list'''

def list_details(lst):

    #Number of elements that can be stored in the list
    print("Capacity:", (sys.getsizeof(lst)-36)//4)

    #Number of elements in the list
    print("Size:", len(lst))

    #Number of elements that can be accommodated in the space left
    print("Space Left:", ((sys.getsizeof(lst)-36) - len(lst*4))//4)

    #formula changes based on the system architecture
    #(size-36)/4 for 32 bit machines and
    #(size-64)/8 for 64 bit machines
    # 36, 64 - size of an empty list based on machine
    # 4, 8 - size of a single element in the list based on machine

marias_lst=[]
print("Empty list created!!!")
print("List details:")
list_details(marias_lst)
for i in range(0,10):
    marias_lst.append(1)

print("List details After adding 10 elements :")
list_details(marias_lst)
for i in range(0,3):
    marias_lst.remove(1)

print("List details after removing 3 elements:")
list_details(marias_lst)

I am using the above program to understand how the growth of lists in python takes place. My doubt is when I add 1 element, the capacity raises to 4 I add 5 elements, the capacity raises to 8 I add 10 elements, the capacity raises to 16

now when I am removing 3 elements after adding 10 elements, I get the following output

Empty list created!!!
List details:
Capacity: 0
Size: 0
Space Left: 0
List details After adding 10 elements :
Capacity: 16
Size: 10
Space Left: 6


List details after removing 3 elements:
Capacity: 10
Size: 7
Space Left: 3

Why not the capacity is 8 and space left 1?

**EDIT 1 ** on a 32-bit machine python interpreter, Our list growth is like demonstrated below

>>> import sys
>>> sys.getsizeof([])
36
>>> sys.getsizeof([1])
40
>>> lst = []
>>> lst.append(1)
>>> sys.getsizeof(lst)
52

Just a side note, a `list` will always have more space than the actual elements. That is to prevent frequent copying of elements, when there is no space left. — user1767754, Jan 21 '18 at 04:49
Why do you expect the size of the list to be immediately contracted? — Stephen Rauch, Jan 21 '18 at 04:49
@user1767754 I agree, you're right that a python list reserves some space in advance for the coming elements. — Ash Upadhyay, Jan 21 '18 at 04:52
@cᴏʟᴅsᴘᴇᴇᴅ I have made an edit to my question where I answered the calculation of this `sys.getsizeof(lst)-36` nw to give a more context to why we are dividing it with 4 We divide by 4 because 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. Please use this [link](https://stackoverflow.com/questions/7247298/size-of-list-in-memory/7247542) for more context. I am searching for an answer which helps me to understand how it shrinks :) — Ash Upadhyay, Jan 21 '18 at 05:00
Sure, upvoted. I think this is a decent question, but needs a little retagging... — cs95, Jan 21 '18 at 05:08
You might want to post your answer in https://stackoverflow.com/questions/11129546/python-sys-getsizeof-reports-same-size-after-items-removed-from-list-dict onto here as a self-answer instead. — metatoaster, Jan 21 '18 at 05:42
Thanks @metatoaster There I have explained how the list grows :) If you refer my previous comments you'll get an idea that I am looking for the answer of the way it shrinks :) I am aware about The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ... Do you have any clues? — Ash Upadhyay, Jan 21 '18 at 05:44
For some reason, you expected 8. Python has given you no reason to expect 8. There are many possible resize policies the implementers could have picked, which could have produced capacities such as 7, 9, 16, or other options. If you assumed some particular resize policy, well, making assumptions about how your tech works is a very dangerous thing to do. — user2357112, Jan 21 '18 at 05:45
@user2357112 I would rather say that I am not assuming anything since I went through the documentation given here [PyList_new](https://github.com/python/cpython/blob/2f37d372927a4c2c843e2813c32354979c682919/Objects/listobject.c) please go through the lines 42 onwards. — Ash Upadhyay, Jan 21 '18 at 05:47
That's not documentation. That's a code comment. It's also not saying what you think it is; it's describing *growth*, not shrinkage, and that's only the growth pattern for appending items to a fresh empty list one by one. — user2357112, Jan 21 '18 at 05:52
@user2357112 Oh yes that just /* List object implementation */ That's what I got when it comes to growth and I verified it using the above code that I had asked in question. So, you're right that I am looking for the shrinkage pattern. You have any clues? — Ash Upadhyay, Jan 21 '18 at 05:54

score 4 · Accepted Answer · answered Jan 21 '18 at 06:07

4

There's no reason to expect the capacity to be 8. There's also no reason to expect the capacity to be 10 again if you run this on a new Python version, or a different implementation (like PyPy). The fact that it happened to be 10 is an implementation detail you should not rely on and not expect to remain unchanged.

The capacity happened to be 10 because remove-ing down to less elements than half the capacity triggered a shrinkage, and (for now, on modern CPython) the resize routine calculates the overallocation as

new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

When newsize is 7, this produces a 3-element overallocation, for a new capacity of 10.

answered Jan 21 '18 at 06:07

user2357112

260,549
28
431
505

for now I accept your answer, can you please show us that the output is different on different implementations that you've mentioned above? – Ash Upadhyay Jan 21 '18 at 06:11
2

@AshUpadhyay: That's really the wrong mindset to have here. That said, I'm not familiar enough with any alternate Python implementation codebases to point you to their resize policy implementations, but [this is what happens](https://ideone.com/xvgBHP) if you try to measure the size of a list on PyPy 2.6.0. – user2357112 Jan 21 '18 at 06:24
I apologize for that if you think that is a wrong mindset. I had accepted your answer as I mentioned to you. I was just asking that since you are saying that, did you really check it for different implementation as well. Because whatever I asked I had a valid justification. I didn't mean to offend you. – Ash Upadhyay Jan 21 '18 at 06:30
Anyways, that said, I got my answer and I really thank you for your genuine answer i wouldn't have thought it that way, otherwise. – Ash Upadhyay Jan 21 '18 at 06:32

Why does the capacity of List in Python reduced to 10 instead of 8 after removing elements?

1 Answers1