Totally agree with other comments that a sorted array will be hard to beat. I don't see how binary search could help with the "look for the next availability" query, but even a linear search could be fast on a strong CPU with cache prefetching, out-of-order execution, etc.
A few thousand elements is still small for a computer. I would be curious to see a benchmark comparing sorted arrays of intervals against the fancier structures.
I did some simple benchmarks of a `Vec<(u32, u32)>` to a `BTreeMap<u32, u32>` for the test case and found them to be roughly comparable. The intervals are relatively dense so I was hoping for the vector to perform better than it did.
The binary search was useful to find the start position if there are more than a few hundred elements or so (whatever the breakeven point for linear search vs. binary search is on your CPU).
Comments
Totally agree with other comments that a sorted array will be hard to beat. I don't see how binary search could help with the "look for the next availability" query, but even a linear search could be fast on a strong CPU with cache prefetching, out-of-order execution, etc.
A few thousand elements is still small for a computer. I would be curious to see a benchmark comparing sorted arrays of intervals against the fancier structures.
I did some simple benchmarks of a `Vec<(u32, u32)>` to a `BTreeMap<u32, u32>` for the test case and found them to be roughly comparable. The intervals are relatively dense so I was hoping for the vector to perform better than it did.
The binary search was useful to find the start position if there are more than a few hundred elements or so (whatever the breakeven point for linear search vs. binary search is on your CPU).