CPython’s optimization for doubly linked lists in deque (amortizes 200% link memory overhead)

I was reading through CPython’s implementation for deque and noticed a simple but generally useful optimization to amortize memory overhead of node pointers and increase cache locality of elements by using fixed length blocks of elements per node, so sharing here.

I’ll apply this next when I have the pleasure of writing a doubly linked list.

From: Modules/_collectionsmodule.c#L88-L94

* Textbook implementations of doubly-linked lists store one datum * per link, but that gives them a 200% memory overhead (a prev and * next link for each datum) and it costs one malloc() call per data * element. By using fixed-length blocks, the link to data ratio is * significantly improved and there are proportionally fewer calls * to malloc() and free(). The data blocks of consecutive pointers * also improve cache locality.