{
  "$type": "site.standard.document",
  "canonicalUrl": "https://rednafi.com/python/preallocated-list/",
  "description": "Understand CPython list memory allocation: how lists store pointer references, grow dynamically, and when pre-allocation with [None]*n helps.",
  "path": "/python/preallocated-list/",
  "publishedAt": "2022-03-27T00:00:00.000Z",
  "site": "at://did:plc:fgtm2c26vfcj74rfmeggbyqj/site.standard.publication/3mnl6f7ob462z",
  "tags": [
    "Python",
    "Performance",
    "Data Structures"
  ],
  "textContent": "In CPython, elements of a list are stored as pointers to the elements rather than the values\nof the elements themselves. This is evident from the [list struct in CPython] that\nrepresents a list in C:\n\nAn empty list builds a PyObject and occupies some memory:\n\nThis returns:\n\nThe exact size of an empty list can vary across different Python versions and\nimplementations.\n\n> A single pointer to an element requires 8 bytes of space in a list. Whenever additional\n> elements are added to the list, Python dynamically allocates extra memory to accommodate\n> future elements without resizing the container. This implies, adding a single element to\n> an empty list will incite Python to allocate more memory than 8 bytes.\n\nLet's put this to test and append some elements to the list:\n\nThis returns:\n\nWait, the size of l should have been 64 bytes (56+8) but instead, it increased to 88\nbytes. This happens because in this case, Python over-allocated 32 extra bytes to\naccommodate future incoming elements. Now, if you append 3 more elements to the list, you'll\nsee that it doesn't increase the size because no re-allocation is happening here:\n\nThis prints:\n\nAdding a fifth element to the above list will increase the size of the list by 32 bytes (can\nbe different in other implementations) again:\n\nThis dynamic memory allocation makes lists so flexible, and since a list only holds\nreferences to the elements, it can house heterogenous objects without any issue. But this\nflexibility of being able to append any number of elements - without ever caring about\nmemory allocation - comes at the cost of slower execution time.\n\nAlthough usually, you don't need to think about optimizing this at all, there's a way that\nallows you to perform static pre-allocation of memory in a list instead of letting Python\nperform dynamic allocation for you. This way, you can make sure that Python won't have to\nperform dynamic memory allocation multiple times as your list grows.\n\nStatic pre-allocation will make your code go slightly faster. I had to do this once in a\ntightly nested loop and the 10% performance improvement was significant for the service that\nI was working on.\n\nPre-allocating memory in a list\n\nLet's measure the performance of appending elements to an empty list. I'm using IPython's\nbuilt-in %%timeit command to do it:\n\nNow, if you know the final size of the list beforehand, then you don't need to create an\nempty list and append elements to it via a loop. You can initialize the list with None and\nthen fill in the elements like this:\n\nThis is quite a bit faster than the previous snippet:\n\nBreadcrumbs\n\nFor simple cases demonstrated above, list comprehension is going to be quite a bit quicker\nthan the static pre-allocation technique. See for yourself:\n\nSo, I don't recommend performing micro-optimization without instrumenting your code first.\nHowever, list pre-allocation can still come in handy in more complex cases where you already\nknow the size of the final list, and shaving off a few micro-seconds makes a considerable\ndifference.\n\nFurther reading\n\n- [Create a list with initial capacity in Python]\n\n\n\n\n[list struct in CPython]:\n    https://github.com/python/cpython/blob/c19c3a09618ac400538ee412f84be4c1196c7bab/Include/cpython/listobject.h#L5\n\n[create a list with initial capacity in python]:\n    https://stackoverflow.com/questions/311775/create-a-list-with-initial-capacity-in-python",
  "title": "Pre-allocated lists in Python"
}