Towards faster binary search

[LifeIsStrange]

rust/src/libcore/slice/mod.rs

Lines 1565 to 1570 in 05630b0

	pub fn binary_search(&self, x: &T) -> Result<usize, usize>
	where
	T: Ord,
	{
	self.binary_search_by(|p| p.cmp(x))
	}

Could be improved in the same way as rust has switched it's old hashmap to the state of the art hashbrown.

It seems that there is a new state of the art Binary search in town leading up to 25% performance improvement and binary search is a foundational task.
Therefore it would be promising to investigate whether Rust could have a faster binary search implementation, the candidate being
https://news.ycombinator.com/item?id=23893366
(but maybe there are other new state of the art)

[tesuji]

Please edit to use permanent link:

rust/src/libcore/slice/mod.rs

Lines 1565 to 1570 in 05630b0

	pub fn binary_search(&self, x: &T) -> Result<usize, usize>
	where
	T: Ord,
	{
	self.binary_search_by(|p| p.cmp(x))
	}

[leonardo-m]

I've just tried a quaternary search and it's slower than the std one

[jakubadamw]

Binary search ought to be the most overstudied algorithm in computer science. It's important to keep that in mind when one sees a new revelation about it on Hacker News.

If one is interested in experimenting with the different n-ary search algorithms in Rust in a crate, then that sounds like an idea, but it seems out of scope for the standard library. All the more that the quaternary variant, where they report a “25%” speed-up in their tests and data set, is clearly not a “binary search” any more (though for some reason they call it a “quaternary binary search”, which is funny), so it in no way can replace the std's binary search.

[LifeIsStrange]

There is also branchless Binary searches that can benefit from SIMD
https://github.com/ehrmann/branchless-binary-search

[tesuji]

Also see #53823 : the problem is not branchless, but how easy the CPU could predict it.