wt-slice

High-performance extensions for ordered slices.

This is a fork of superslice. It preserves superslice's lower-bound, upper-bound, equal-range, and permutation APIs while adding exact-search experiments for WorkTablesIndex.

Licensed under APACHE-2.

Installation

Until the fork is published, use its Git repository:

[dependencies]
wt-slice = { git = "https://github.com/pathscale/wt-slice" }

and augment slices by using its Ext trait:

use wt_slice::*;

Now you can enjoy high performance of common algorithms on slices:

• exact_search
• exact_search_by
• exact_search_by_key
• lower_bound
• upper_bound
• equal_range

The exact-search methods return Result<matching_index, insertion_index>. Their search loop exits early on equality while using unpredictable conditional selection for the left/right decision, avoiding the most expensive branch in a conventional binary search.

Why isn't this part of the standard library?

Worry not, work is on the way:

• Make binary_search as fast as fast_binary_search: https://github.com/rust-lang/rust/pull/45333
• Add lower_bound, upper_bound, equal_range to std: https://github.com/rust-lang/rfcs/issues/2184