List is one of the most frequently used data structure in Python applications. The code for Python list object allocator is present in Python-2.7.5/Objects/listobject.c.
Python allocates list objects in heap and uses underlying malloc based APIs. List is a container of Python object references. In plain C terminology. it is a dynamic array of pointers.
Let’s understand basic creation and insertion APIs.
- list_resize(): A list is of type PyListObject and is equivalent to PyObject. Every resize request allocates more than asked size.
Allocation unit size is : (size_requested + (size_requested << 3 + (size_requested < 9 : 3 or 6) ).
It gives a growth pattern of (0, 4, 8, 16, 25, 35, 46, 58, 72, 88).
- free_list: Python keeps PyList_MAXFREELIST (defined to value 80) of free lists to save on lists allocation and deallocation.
- PyList_New(): A new list allocation requests is served from either a free list or a new GC tracked object creation of type PyListObject. Next, a malloc request is made for requested list size.
Size calculated: nbytes = size * sizeof(PyObject *);
Object allocation: PyListObject *op = free_list[numfree] OR PyObject_GC_New(PyListObject, &PyList_Type);
Memory allocation for references: op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);