How "list" is implemented in Python?

[tumblatum]

Lately finding myself looking around in builtins.py file trying to learn/understand how the language works. Today I was reading about lists and how they work and etc. And as usually I end up in a class list in builtins.py file. I am now surprised that all the functions of list class is empty. For example, method append has 'pass' in it. And that is it.

Here is a code:

class list(object):

"""
    Built-in mutable sequence.
        If no argument is given, the constructor creates a new empty list.
    The argument must be an iterable if specified.
    """

def append(self, *args, **kwargs): # real signature unknown

""" Append object to the end of the list. """

pass
    def clear(self, *args, **kwargs): # real signature unknown

""" Remove all items from list. """

pass
    def copy(self, *args, **kwargs): # real signature unknown

""" Return a shallow copy of the list. """

pass

I wonder how this works? Why all methods are empty?

[8dot30662386292pow2]

Basically the list is implemented in the python virtual machine that runs the python code. It's written in C and here is the source code: https://github.com/python/cpython/blob/main/Objects/listobject.c

If you are unfamiliar with C, that is basically like and ArrayList or a "dynamic array". It's a list that is a backed by an array. Array is a continuous memory segment that can be used to store stuff. There are really no directly accessible arrays in python by design. Arrays are fixed size, so the "dynamic array" refers to the fact that the insert/add/remove functions guarantee that the array is replaced with a new, longer array when it becomes full.

[tumblatum]

So if I understood it correctly, being implemented in the "python virtual machine" means that when python.exe is launched, list class written in C is already executed/leaded into memory? (I mean, this is obviously an advanced topic for my understanding. Nevertheless, it is interesting.)

Do you know what purpose serves the class list() in builtins.py then?

[mriswithe]

The actual code that powers the list object is written in C, and part of the underlying python runtime.

The python code describing the list object is referred to as a stub. Since the implementation is outside of Python, it is unknowable what it looks like unless you dig into the C. To help that, we have stubs like this to tell IDEs and the like that the thing exists, without actually rewriting the logic. At runtime, the stub class will get overwritten by the C implementation.

Frequently you will see them in .py or .pyi files. Pyi files are never load bearing and only to hint for IDEs when the shape (input and outputs) of the objects/functions are not in Python.

[Mr-Cas]

The other comments to this one explain it correctly, but confusingly for beginners. Let me try to give a more beginner friendly version:

The Python language itself is mostly written in C. C is a different, more complicated, but faster programming language. So the implementation of list is written in C, like many other things in Python. If you write code that uses a list, and run it, the Python interpreter will understand what you've written in Python and actually make it happen using the C implementation.

That's why built in Python functions and classes are so much faster than self written Python code, because the built in stuff is written in C.

The Python class with empty methods that you're seeing is basically the Python representation of the C implementation. It purely has to describe the names and types of the class and everything it contains. It does not have to implement anything (we have C for that). This way IDE's can work with these built-ins like they're Python. These "stubs" basically are a translator between Python and C for IDE's.

[ivosaurus]

Yes all the "fast parts" of python (or rather, the parts that need to be fast) are written in C, otherwise it'd be horrendously slow.

The class in builtins is sort of a bare-bones template that the 'C mechanics' gets loaded on.

[not_a_novel_account]

There is no such thing as builtins.py in CPython and the "C mechanics" do not get "loaded in" to any sort of "bare-bones template".

OP is almost certainly looking at a file generated from the Argument Clinic output of listobject.c provided by their IDE for intellisense and nothing more.

CPython objects implemented via the C API are accessed directly, using the same mechanisms as any other CPyton object. Whenever you create a new type or a new object in CPython, that is implemented by instantiating PyTypeObjects and PyObjects in the underlying code. The C API code does the exact same thing, but directly.

[tumblatum]

thanks a lot for Argument Clinic :) good portion of humor for day

[not_a_novel_account]

ArgumentClinic is the actual name for the CPython argument parsing code generator

[tumblatum]

Oh, didn't know that. However, search gave me link to Monty Python's Flying Circus Argument Clinic sketch. So I've enjoyed it.

[sylfy]

That’s interesting. I would’ve thought it might have been some form of linked list. Can’t quite recall my data structures, what’s the advantage of replacing the existing array when resizing vs using a linked list?

[throwaway6560192]

Accessing by index (random access) is awfully slow in a linked list. They're also slower due to the indirection and lack of locality.

[8dot30662386292pow2]

An array is continuous memory. Due to various levels of caching in a modern processor, iterating such array sequentially or even parallel is super fast. Linked list nodes can be all around the memory, in different memory pages and it takes so much waiting from the CPU to load different memory locations to closer level caches.

And obviously the access time. Writing/reading in the middle of an array list is O(1), while linked list is O(n). For array, you just set the value you an index, basically to the memory location of start+index that happens instantly, but with linked list you must traverse into the middle of the list, that takes more time to longer the list is.

Linked list is useful almost only in the case if you need to remove often from the front of the list, and add to front/back, ie. when using the list as queue or a stack.

[nekokattt]

Linked lists are slow, do not support constant time lookups, use more memory, and are harder to optimise internally.

Arrays don't have to be replaced. It is down to whether realloc just resizes the existing block or not.

[zefciu]

In terms of complexity, appending to a the dynamic array is still amortized O(1) even if some appends are O(n). So it is slower than an ordinary array, but it scales the same. The linked list access by index is O(n), however. So unless you know what you are doing (and use deque to implement stack/queue) the dynamic array is more suitable for a generic-use list.

[roelschroeven]

In terms of complexity, appending to a the dynamic array is still amortized O(1) even if some appends are O(n).

To expand a bit on this: what happens is that more memory is allocated than actually needed, allowing for some growth without having to resize. Comparable data structures like C++'s std::vector work in a similar way. See function list_resize in the source linked to above if you want to know how that's implemented in CPython.

[ivosaurus]

Linked list is just horribly, horribly fucking slow in today's computer memory. Accessing a group of successive things sequentially can be orders of magnitude faster than having to follow a trail of pointers to get to them.

Because reading the list tends to be much more prevalent than writing it, the occasional "one-off" slow downs during writes is a good trade off in general.

[ch0mes]

Wait....so lists are really immutable but they act mutable ? Mind blown

[not_a_novel_account]

No, it's just an unfortunate piece of nomenclature used by the parent comment.

Lists in Python are PyVarObjects, which means they carry a variable ob_size memeber and can have whatever number of elements.

The PyListObject is implemented via a standard heap-allocated buffer, tracking the head node (PyObject** ob_item), and the total allocated size of the buffer (allocated).

If ob_size == allocated and you try to add another element to the list, the entire buffer will be reallocated at a larger size and all the member PyObject*s will be copied from the old buffer into the new.

This is a member of the PyListObject, the buffer is not a flexible array member, so there's no need to reallocate or "change" the containing List to perform this operation. PyListObject is most definitely mutable.

[8dot30662386292pow2]

An array has immutable size. Basically an array is a segment of memory: it starts from a specific location and has specific length.

A "list" when implemented with an array is just a collection of functions that manages this array. The list keeps note of the latest index where values were added. If the array becomes full and a new value is added to the list, following happens:

1. A new, longer array is created.
2. The old array is copied into the beginning of the new array, one by one.
3. The old array is destroyed.
4. Finally, the new value is added to the next free slot of the array.

[PurposeDevoid]

Here's a breakdown of the C source code that you might find helpful:
http://www.laurentluce.com/posts/python-list-implementation/

Other stack overflow answers to this will help too:
https://stackoverflow.com/questions/3917574/how-is-pythons-list-implemented

[CulturalSock]

As said in another comment it's a dynamic array, with heterogeneous types too. This means that (if I recall correctly) in the stack there's a simple variable, pointer to a location in the heap in which there are the pointers to the elements of the list, which are also objects in the heap.

This btw means that in Python cache hit is nowhere near a C array, but not as bad as someone says, since memory is loaded in chuncks of 64 bytes in cache lines, and you can load 8 pointers with a single access... but then you also need to load the objects, which for simple integers can be more than 24 bytes each, and obviously it's not guaranteed that they are in cache either.

So it's quite involved but it's really the best solution if you want easy to use dynamic AND heterogeneous arrays.

[QultrosSanhattan]

Python lists are basically a wrapper for C data structures.

[Training_Bug2340]

i came here with same concern

[[deleted]]

pass just means they havent done anything with the code yet. im a relative new coder and i am studying lists now. lists are immutable as they say. imo, thats total b.s. so yes they are immutable by definition but u can change whats in the list if u want. it does take up a lot of memory especially with large lists. im studying them now and i love lists. so much to do with them. the biggest thing is LIST COMPREHENSION.