Skip to main content

Crate radix_spline

Crate radix_spline 

Source
Expand description

§radix_spline

Implementation of RadixSpline (paper) in Rust. This is mainly a learning experiment for me but it is functional, as such I believe it’s fine for people to use if they so desire. The code is small though so anyone depending on it should consider just vendoring the implementation.

A C API is provided via the radix_spline_c subproject.

This crate supports no_std but requires alloc as it uses Vec internally.

§Performance

The synthetic 200M and Wikipedia 200M datasets on SOSD (Search On Sorted Data) are used to benchmark. As the C API currently takes a contiguous array of keys I modified the benchmark to do the same for the C++ version. I then disabled -ffast-math and enabled -Ctarget-cpu=native on the Rust version so their two compiler flags were equivalent.

Checking on the synthetic 200M entry dataset the results are:

graph

The Rust implementation needs to go via a shared object and the C bindings have to construct the object and box it added a layer of indirection. In comparison the original implementation can benefit from inlining and lesser indirection from the harness code.

Contrastingly, I’m happy the index size is a consistent 24 bytes smaller due to using Box<[T]> instead of a Vec<T> in the constructed spline removing the unnecessary capacity.

Running on the 200M wikipedia dataset we can see the lookup latency isn’t as clear:

graph

As I continue working on this I’ll be looking into more of what causes changes in performance. I may need to create a comparative harness in Rust for running the Rust benchmark or add some benchmark-useful C API methods.

§References

As well as the paper RadixSpline: a single-pass learned index, the reference C++ implementation was consulted. This project as a result is also licensed under the MIT license although the code will likely diverge to be more Rusty.

Structs§

RadixSpline
A RadixSpline is a read-only learned data structure built over a list of sorted data. This is the learned spline and can be used to estimate a range in a sorted list where an element can appear. It does this by fitting a spline over the data and using a radix table for quick lookups of spline segments that span a points value.
RadixSplineBuilder
Fluent builder API for the RadixSpline.

Traits§

Key
Convenience trait for the spline key.