CPython internal structures

Question

GAE has various limitations, one of which is size of biggest allocatable block of memory amounting to 1Mb (now 10 times more, but that doesn't change the question). The limitation means that one cannot put more then some number of items in list() as CPython would try to allocate contiguous memory block for element pointers. Having huge list()s can be considered bad programming practice, but even if no huge structure is created in program itself, CPython maintains some behind the scenes.

It appears that CPython is maintaining single global list of objects or something. I.e. application that has many small objects tend to allocate bigger and bigger single blocks of memory.

First idea was gc, and disabling it changes application behavior a bit but still some structures are maintained.

A simplest short application that experience the issue is:

a = b = []
number_of_lists = 8000000
for i in xrange(number_of_lists):
    b.append([])
    b = b[0]

Can anyone enlighten me how to prevent CPython from allocating huge internal structures when having many objects in application?

Answer 1

On a 32-bit system, each of the 8000000 lists you create will allocate 20 bytes for the list object itself, plus 16 bytes for a vector of list elements. So you are trying to allocate at least (20+16) * 8000000 = 20168000000 bytes, about 20 GB. And that's in the best case, if the system malloc only allocates exactly as much memory as requested.

I calculated the size of the list object as follows:

• 2 Pointers in the PyListObject structure itself (see listobject.h)
• 1 Pointer and one Py_ssize_t for the PyObject_HEAD part of the list object (see object.h)
• one Py_ssize_t for the PyObject_VAR_HEAD (also in object.h)

The vector of list elements is slightly overallocated to avoid having to resize it at each append - see list_resize in listobject.c. The sizes are 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ... Thus, your one-element lists will allocate room for 4 elements.

Your data structure is a somewhat pathological example, paying the price of a variable-sized list object without utilizing it - all your lists have only a single element. You could avoid the 12 bytes overallocation by using tuples instead of lists, but to further reduce the memory consumption, you will have to use a different data structure that uses fewer objects. It's hard to be more specific, as I don't know what you are trying to accomplish.