Unrolled linked list
   HOME

TheInfoList



OR:

In computer programming, an unrolled linked list is a variation on the
linked list In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes whi ...
which stores multiple elements in each node. It can dramatically increase cache performance, while decreasing the memory overhead associated with storing list metadata such as
reference A reference is a relationship between objects in which one object designates, or acts as a means by which to connect to or link to, another object. The first object in this relation is said to ''refer to'' the second object. It is called a ''nam ...
s. It is related to the
B-tree In computer science, a B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree generalizes the binary search tree, allowing fo ...
.


Overview

A typical unrolled linked list node looks like this: record node Each node holds up to a certain maximum number of elements, typically just large enough so that the node fills a single
cache line A CPU cache is a hardware cache used by the central processing unit (CPU) of a computer to reduce the average cost (time or energy) to access data from the main memory. A cache is a smaller, faster memory, located closer to a processor core, which ...
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 is also possible to include a ''previous'' pointer for an unrolled doubly linked list. To insert a new element, we 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, we find the node it is in and delete it from the elements array, decrementing numElements. If this reduces the node to less than half-full, then we move elements from the next node to fill it back up above half. If this leaves the next node less than half full, then we move all its remaining elements into the current node, then bypass and delete it.


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 maximum number of elements in 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/m + s)n and (2v/m + s)n. 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 of these make unrolled linked lists more attractive. Because unrolled linked list nodes each store a count next to the ''next'' field, retrieving the ''k''th element of an unrolled linked list (indexing) can be done in ''n''/''m'' + 1 cache misses, up to a factor of ''m'' better than ordinary linked lists. Additionally, if the size of each element is small compared to the cache line size, the list can be traversed in order with fewer cache misses than ordinary linked lists. In either case, operation time still increases linearly with the size of the list.


See also

*
CDR coding In computer science CDR coding is a compressed data representation for Lisp linked lists. It was developed and patented by the MIT Artificial Intelligence Laboratory, and implemented in computer hardware in a number of Lisp machines derived fro ...
*
Skip list In computer science, a skip list (or skiplist) is a Randomized algorithm, probabilistic data structure that allows O(\log n) Average-case complexity, average complexity for search as well as O(\log n) average complexity for insertion within an or ...
* T-tree * XOR linked list * Hashed array tree


References

*


External links


Implementation written in C

Another implementation written in Java

Implementation written in Golang


Pat Morin {{Data structures Linked lists