Binary_search is not fast as the auther said - why?

I have compared binary_search before this PR and after, and my own logics.
The PR says that it can process &[usize; 1000] in 15ns and three times faster than old logic. However when i tried same logic, it tooks about 40ns and improvement from the old logic was negligible.
I also cloned the master branch and tried bench, and it tooks 60ns!

Why this happen?
Something is wrong with me? Updates on compiler breaked some criteria?


1 Like

The exact numbers depend on the computer you are running it on, of course.

1 Like

I think four times slower on the high end class CPU at the time is not just a exact number, but some reason exists.

Just to double-check, are you building using --release? Also perhaps the PR author used different optimisation level (or architecture specific ones).

When benchmarking algorithms like sort the input data and starting order is a significant factor. Perhaps instead of comparing your numbers with the PR, compare your numbers using the code before the PR and then after the PR to get something more realistic.

1 Like

This is issue #53823: Upgrading to LLVM 6 caused a regression in code generation that made the fast binary_search implementation much slower. According to the LLVM issue, this is still not fixed in the latest LLVM.


Thank you, I got.
I have to wait it ti be fixed before I think about better logic.
I'm worried to hear it is not fixed two yeas.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.