Crate fast_list

fast-list

A doubly linked list using [SlotMap] for improved cache locality, and to solve the ABA problem.

✅ On average ~2-3x faster than std::collections::LinkedList for all operations.

✅ On average ~2-3x faster than Vec & VecDeque for random insertions (random removals are about the same as of now)

✅ Only slightly slower than Vec & VecDeque for most other operations.

✅ Safe against [ABA problem] by using a [SlotMaps] internally, which means you can safely iterate & mutate the list across multiple threads. An advantage over just using a SlotMap is that the order when iterating is not arbitrary.

✅ Using indices into a stack allocated arena (slotmap) instead of pointers for improved cache locality.

✅ Written in 100% safe Rust.

Examples

Multithreaded iteration & mutation

use fast_list::LinkedList;
use std::thread;
use std::sync::{Arc, Mutex};

let mut list = LinkedList::new();
let indexes = Arc::new(list.extend(0..10_000));

// You can also get the ordered indexes with something like this:
// let indexes = Arc::new(
//     list.cursor_next(list.head.unwrap()).collect::<Vec<_>>()
// );

let list_mut = Arc::new(Mutex::new(list));

let mut threads = Vec::new();
for _ in 0..3 {
    let list_mut = Arc::clone(&list_mut);
    let indexes = Arc::clone(&indexes);
    let t = thread::spawn(move || {
        for index in indexes.iter().take(9_000)  {
            list_mut.lock().unwrap().remove(*index); // returns None if the index does not exist
        }
    });
    threads.push(t);
}



for t in threads {
    t.join().unwrap();
}

// Even though remove() is called 9000*3 times, only 9000 items are removed.
{
    assert_eq!(list_mut.lock().unwrap().head().unwrap().value, 9_000);
}

Structure

LinkedList - The main struct that holds the list.

// A doubly linked list using SlotMap for better cache performance than a linked list using pointers, and which also solves the ABA problem.
pub struct LinkedList<T = ()> {
    // The index of the first item in the list.
    pub head: Option<LinkedListIndex>,
    // The index of the last item in the list.
    pub tail: Option<LinkedListIndex>,
    // The items in the list.
    items: SlotMap<LinkedListIndex, LinkedListItem<T>>,
}

LinkedListIndex - An index into the list.

new_key_type! {
    /// A newtype for the index of an item in the list.
    pub struct LinkedListIndex;
}

LinkedListItem - An item in the list.

pub struct LinkedListItem<T> {
    /// The index of the item in the list.
    pub index: LinkedListIndex,
    /// The value of the item.
    pub value: T,
    /// The index of the next item in the list.
    pub next_index: Option<LinkedListIndex>,
    /// The index of the previous item in the list.
    pub prev_index: Option<LinkedListIndex>,
}

LinkedListWalker - [unstable] A walker type (like in petgraph) which can be used to iterate over the list.

Structs

• LinkedList
  A doubly linked list using SlotMap for better cache performance than a linked list using pointers, and which also solves the ABA problem.
• LinkedListIndex
  A newtype for the index of an item in the list.
• LinkedListItem
• LinkedListWalker
• WalkerIter
  A walker and its context wrapped into an iterator.

Traits

• Walker
  Shamelessly stolen/inspired by https://docs.rs/petgraph/0.4.13/src/petgraph/visit/traversal.rs.html#355-370 A walker is a traversal state, but where part of the traversal information is supplied manually to each next call.