segment-array 1.0.1

Segment array (growable, append-only) data structure.
Documentation

Segment Array

This Rust crate contains an implementation of a segment array (also known as a segmented list), as described in this blog post:

A data structure with constant time indexing, stable pointers, and works well with arena allocators. ... The idea is straight forward: the structure contains a fixed sized array of pointers to segments. Each segment is twice the size of its predecessor. New segments are allocated as needed. ... Unlike standard arrays, pointers to a segment array’s items are always valid because items are never moved. Leaving items in place also means it never leaves "holes" of abandoned memory in arena allocators. The layout also allows us to access any index in constant time.

The functionality, memory layout, and performance of this implementation should be very similar to that of the C implementation.

The overhead of the bit-shifts and logarithm operations required for every push operation seems to outweigh the amortized O(1) of the basic geometrically growing Vec array. The main benefit of a segment array is that it works well with arena memory allocators.

This data structure is meant to hold an unknown, though likely large, number of elements, otherwise Vec would be more appropriate. An empty array will have a hefty size of around 224 bytes.

For a different but similar data structure, see the nlfiedler/extarray repository for an implementation of Space-Efficient Extensible Arrays in Rust.

Examples

A simple example copied from the unit tests.

let inputs = [
    "one", "two", "three", "four", "five", "six", "seven", "eight", "nine",
];
let mut arr: SegmentArray<String> = SegmentArray::new();
for item in inputs {
    arr.push(item.to_owned());
}
for (idx, elem) in arr.iter().enumerate() {
    assert_eq!(inputs[idx], elem);
}

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. The shell script below gives a quick demonstration of running one of the examples with ASAN analysis enabled.

#!/bin/sh
env RUSTDOCFLAGS=-Zsanitizer=address RUSTFLAGS=-Zsanitizer=address \
    cargo run -Zbuild-std --target x86_64-unknown-linux-gnu --release --example leak_test

Other Implementations

Academic Research

Publications related to the dynamic array problem in order of publication: