sbral

Skew Lists

sbral::SkewList provides a Skew N-ary Random Access List, an immutable data structure which combines the performance characteristics of lists and trees, with O(log index) index and update operations, and O(1) push and pop. They were first described in Chris Okasaki's 1995 paper, "Purely Functional Random-Access Lists", and have aged remarkably well.

You should consider using them if you need a persistent list with excellent performance, and don't need features like insertion, removal, splitting, or concatenation (all of which are O(N)).

By default SkewList uses Rc internally and cannot be shared between threads. You can opt into thread safety by adding the threadsafe feature flag.

Details

sbral groups elements into chunks of 16 elements before inserting them into the backing array. Because of this, up to 16 elements may be cloned when you call .clone() or .get_mut(). If this is expensive or impossible for your elements, you'll need to wrap them in Rc or Arc as appropriate.

Allocating and following pointers are slow operations, so most tree-like data structures like sbral group values together into arrays, to amortize the cost of allocation and reduce memory overhead and overall tree depth. In sbral's case these arrays are 16 elements long, so when you clone a SkewList, up to 16 elements will be cloned (those awaiting insertion as a new chunk) and when you update a value, all 16 neighboring elements may be cloned (if there are other references to them). If cloning is expensive or impossible, you'll need to wrap your elements in a Rc or Arc.

sbral also seeks to improves performance by having a higher branching factor, which again reduces tree depth - this is what makes it a skew n-ary list rather than a skew binary list.

Performance

These benchmarks show the performance of the basic collection operations that sbral supports. I chose a few different libraries to compare against that provided the same features as SkewList - push, pop, Index, and IndexMut. (As it turned out, all of them were vectors.) They are im_rc::Vector, dogged::DVec, and rpds::Vector. In addition, I included std::vec::Vec from the standard library, to provide a baseline. Each one is tested as a collection of usizes.

As with any microbenchmarks, these are fairly artificial and don't always reflect how the data structure would be used in real life. Take them with a grain of salt, and test using your own data before deciding to use one over another!

Build

This measures the time taken to create a new collection and add N elements to it (essentially, (0..N).collect()).

Append

This measures the time taken to add 1000 elements to an existing collection of N elements. The time taken to clone the collection is not counted. This is intended to test larger sizes than are practical to build from scratch.

Vec drops out partway through, due to excessive delay. While the time spent cloning isn't included in the measurements, it still takes place, and becomes prohibitive around 1 million entries.

Lookup First

This measures the time taken to sum the first 1000 elements (or as many as are in the list), retrieved in random order. While indexing into a skew list is O(log N) in the worst case, the expected case is O(log index).

Choosing a number of elements to sum up is difficult: values belonging to a partial chunk can always be accessed in O(1), and smaller ranges will weight measurements toward it. The buffer is beneficial when accessing recently-added values, and a benchmark should reflect that, but it should also seek to measure the underlying collection's performance.

Lookup Last

This is the aforementioned worst case: accessing the last (least recently added) values takes O(log N).

Lookup Scattered

This divides the size of the collection into 1000 equal ranges, chooses a random index within each of those ranges, and then shuffles those indexes, retrieves them and sums their values. This is intended to measure looking up unpredictable values, while ensuring they are not biased towards the start or the end of the collection.

Update First

Similar to Lookup First, this accesses the first 1000 elements in random order and adds 1 to each of them. All the tested immutable data structures only clone values when necessary: if you never clone the collection, they will modify it in place. In this case, the collection is cloned once at the start (not measured) and then modified 1000 times. As with Append, Vec drops out early due to excessive setup time.

Update Last

There's not much to say here. This is analogous to Lookup Last.

Update Scattered

Analogous to Lookup Scattered.

Clone

This measures the time to clone a collection of the given size. In a language that carefully controls mutation like Rust does, fast and memory-efficient clones are the only feature persistent data structures offer over mutable ones, so it's important that this be as fast as possible.

Drop

This measures the time to drop the entirety of a collection of the given size. This is probably a rare occurrence, but it might offer an indication of the time taken when dropping some portion of it.

Further Reading

• The original paper and thesis cover how skew lists work and why they have the performance characteristics they do.
• The Wikipedia article on skew binary numbers is not bad either.
• Bootstrapping One-Sided Flexible Arrays explores similar data structures, along with different ways to trade off between lookup and update time.
• fral is a much more straightforward implementation of a skew binary list in Rust.
• The Haskell nested-sequence library is another implementation that uses n-ary lists.