🔒 question about the default python list

[hallow holly]

how does python know the size/length of a list in its default implementation? does it store a length variable of type int of size 64 bits, before init'ing the array itself?

also how much extra space in allocated per the length of the initilaized list? 2*len(lst) is pre-allocated? in order to make amortized time complexity O(1) for the append method

[jovial pecan]

@hallow holly

Python help channel opened

Remember to:

• Ask your Python question, not if you can ask or if there's an expert who can help.
• Show a code sample as text (rather than a screenshot) and the error message, if you've got one.
• Explain what you expect to happen and what actually happens.

:warning: Do not pip install anything that isn't related to your question, especially if asked to over DMs.

Closes after a period of inactivity, or when you send !close.

[glossy nacelle]

Python's list is similar to C++ STL vector of pointers.

This means that yes, length is stored and there is pre-allocated memory to make appending quick.

The implementation is here https://github.com/python/cpython/blob/3.12/Objects/listobject.c

https://github.com/python/cpython/blob/3.12/Objects/listobject.c#L31-L45 resizing to be ready for new elements - see the comment I marked before definition

[hallow holly]

im not really sure how to read this C code, could you explain it or maybe just answer my original questions?

[glossy nacelle]

You can read the comments tho

E.g. What happens when new size is smaller?

If the newsize falls lower than half
the allocated size, then proceed with the realloc() to shrink the list.

Over-allocation for growth is described as "mild" - it's not always doubled but it's proportional to the size + padded to be a multiple of 4

The growth pattern is: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...

And the formula after that is:
new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;

• then it's checked whether it's close to already existing over-allocation or not etc (read comments and the ifs for details)

https://github.com/python/cpython/blob/94e6644584d9cb08a4edcd1027e288386184816b/Include/cpython/listobject.h#L5-L22 the definition of the struct itself
The type of the allocated and current length is Py_ssize_t which is long... Which is not long long, so the size is actually 32-bit int, not 64-bit like you thought.

[hallow holly]

I see, thank you very much

!close

[jovial pecan]

Python help channel closed

This help channel has been closed and it's no longer possible to send messages here. If your question wasn't answered, feel free to create a new post in #1035199133436354600. To maximize your chances of getting a response, check out this guide on asking good questions.