Crate chainlink[−][src]

Chainlink

use chainlink::LinkedList;
let mut list = LinkedList::new();
list.push_tail(1); // 1
list.push_head(2); // 2, 1
list.push_tail(3); // 2, 1, 3

assert_eq!(list.into_vec(), vec![2, 1, 3]);

Chainlink is an attempt to make a 100%-safe linked list in pure-Rust. The strategy to accomplish this is to use a generational-arena allocator backing the linked list instead of general-purpose pointers issued by a normal allocator. This has two main benefits.

  1. Because all our data is stored in a single vector, accesses and other operations on that vector should be extremely fast compared to a normal linked list, which is issued a new allocation for each node. Pointers issued by several calls to a system allocator tend to have worse cache locality than multiple elements of the same vector.

  2. Our pointer equivalents are just indices that are logically tied to a vector, and accesses to the vector are checked at runtime to ensure we’re within the bounds of valid memory. Since these types of runtime checks will panic and crash if they fail, any failed check is a bug and is expected to never happen. For that reason, we should expect the branch predictor for these checks to perform well and reduce the extra runtime cost, which was already unlikely to be a bottleneck in normal application code.

Drawbacks

This approach is not without its compromises.

  1. It’s memory-inefficient compared to a plain Vec. A normal vector will store only the data you give it behind its heap-allocated pointer. That represents perfect efficiency if you don’t count the padding between elements. Our LinkedList node currently uses 20 bytes to store a single u8. As the stored elements get larger, the effective inefficiency of using a doubly linked list will decrease. However, for small numbers of elements, consider using a normal Vec. It will have better cache efficiency due to using less space.

  2. We’re limited to about four billion elements that can each undergo about four billion revisions. Using generational-arena indices means that we have to store the generation of the elements alongside the pointer-equivalent usize vector offset. Instead of making every Index larger than a pointer, the underlying arena implementation, thunderdome, uses 32 bits for the generation and 32 bits for the vector offset. In practice, the minimum size of a node is 20 bytes and four billion of those nodes would take 80GB of memory. It’s unlikely you’re going to use 80GB of memory. Though, for a very long-lived application, you may bump up against the four-billion-times update limit. For reference, that’s about 120 updates per second over one year. We plan to implement parameterized arenas that can be more tailored to the API users’ needs.

Structs

IterLinks
LinkedList