Unrolled linked list

In computer programming, an unrolled linked list is a variation on the linked list which stores multiple elements in each node. It can drastically increase cache performance, while decreasing the memory overhead associated with storing list metadata such as references. It is related to the skip list and the B-tree.

Overview

A typical unrolled linked list node looks like this:

record node { "node" next "// reference to next node in list" "int" numElements "// number of elements in this node, up to maxElements" "array" elements "// an array of numElements elements, with space allocated for maxElements elements" }

Each node holds up to a certain maximum number of elements, typically just large enough so that the node fills a single cache line or a small multiple thereof. A position in the list is indicated by both a reference to the node and a position in the elements array. It's also possible to include a "previous" pointer for an unrolled doubly-linked linked list.

To insert a new element, we simply find the node the element should be in and insert the element into the elements array, incrementing numElements. If the array is already full, we first insert a new node either preceding or following the current one and move half of the elements in the current node into it.

To remove an element, similarly, we simply find the node it is in and delete it from the elements array, decrementing numElements. If numElements falls below maxElements ÷ 2 then we pull elements from adjacent nodes to fill it back up to this level. If both adjacent nodes are too low, we combine it with one adjacent node and then move some values into the other. This is necessary to avoid wasting space.

Performance

One of the primary benefits of unrolled linked lists is decreased storage requirements. All nodes (except at most one) are at least half-full. If many random inserts and deletes are done, the average node will be about three-quarters full, and if inserts and deletes are only done at the beginning and end, almost all nodes will be full. Assume that:
* "m" = maxElements, the size of each elements array;
* "v" = the overhead per node for references and element counts;
* "s" = the size of a single element.Then, the space used for "n" elements varies between $(v\; +\; sm)lceil\; n/m\; ceil$, roughly $(v/m\; +\; s)n$, and twice this value. For comparison, ordinary linked lists require $(v\; +\; s)n$ space, although "v" may be smaller, and arrays, one of the most compact data structures, require $sn$ space. Unrolled linked lists effectively spread the overhead "v" over a number of elements of the list. Thus, we see the most significant space gain when overhead is large, maxElements is large, or elements are small.

If the elements are particularly small, such as bits, the overhead can be as much as 64 times larger than the data on many machines. Moreover, many popular memory allocators will keep a small amount of metadata for each node allocated, increasing the effective overhead "v". Both these make unrolled linked lists more attractive.

Another advantage of unrolled linked lists is that they perform a number of operations, typically associated with arrays, much more quickly than ordinary linked lists. For example, when indexing into unrolled linked list, we can progress a node at a time rather than an element at a time, reducing the indexing time to O(n/m) instead of O(n).

Unrolled linked lists also perform sequential traversal much more rapidly, due to their cache behavior: iterating through an ordinary linked list of "n" elements triggers "n" cache misses in the worst case, and about "2nv/m" in the best case, assuming "v" and "s" are about the same size. Iterating through an unrolled linked list of "n" elements triggers only "2n/m" cache misses in the worst case and "n/m" in the best. Even arrays can do little better than this best case, with about "n/(m+v/s)" misses. When "v" is about "s", linked lists have twice as many cache misses as unrolled linked lists in the best case, and "m"/2 times as many in the worst case, which in practice can speed up list traversal by as much as 10 times or more.

See also

* CDR coding, another technique for decreasing overhead and improving cache locality in linked lists similar to unrolled linked lists.
* the skip list, a similar variation on the linked list, also offers fast traversal but hurts the advantages of linked lists (quick insert/deletion) less than an unrolled linked list
* the B-tree and T-tree, data structures that are similar to unrolled linked lists in the sense that each of them could be viewed as an "unrolled binary tree"