Tiered Vector

Overview

This Rust crate provides an implementation of a tiered vector as described in the paper Tiered Vector by Goodrich and Kloss II, published in 1998 (and subsequently in 1999).

• https://www.researchgate.net/publication/225174363_Tiered_Vectors_Efficient_Dynamic_Arrays_for_Rank-Based_Sequences

This data structure supports efficient get and update operations with a running time of O(1) as well as insert and remove operations on the order of O(√N). It uses a collection of circular buffers to achieve this with a space overhead on the order of O(√N).

Performance

Expect random remove/insert operations on a tiered vector to be orders of magnitude faster than a standard vector. Note that the benchmarks use different values because using an equal number for both data structures would take much too long.

Examples

A simple example copied from the unit tests.

let mut tiered = Vector::<usize>::new();
assert!(tiered.is_empty());
for value in (1..=16).rev() {
    tiered.insert(0, value);
}
assert!(!tiered.is_empty());
for (index, value) in (1..=16).enumerate() {
    assert_eq!(tiered[index], value);
}

Supported Rust Versions

The Rust edition is set to 2024 and hence version 1.85.0 is the minimum supported version.

Troubleshooting

Memory Leaks

Finding memory leaks with Address Sanitizer is fairly easy and seems to work best on Linux. A Docker container with bash access and Rust nightly installed can be found in the containers directory.

cd containers
docker compose build --pull
docker compose run leaktest
sh leak.sh

If no problems were detected, a single line of output will appear. When done, clean up the docker artifacts.

exit
docker compose down

References

• [1]: Tiered Vector (1998)
  • There is a 1999 version that lacks psuedo-code but is largely the same.

Other Implementations

• mettienne/tiered-vector
  • C++ templates variation by Bille, Christiansen, Ettienne, and Gørtz from their Fast Dynamic Arrays paper.
• PhilipCramer/Tiered-Vector
  • Rust implementation with a different underlying structure.
• art-w/varray (OCaml)
• taitaisama/TieredVector (D)
• layesUddin/Tiered-Vector (C)
• igushev/IgushArray (C/C++)
  • No reference to tiered vectors but appears to be the same thing.