Binary_search is not fast as the auther said - why?

help
#1

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 x.py bench, and it tooks 60ns!

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

Environment:
i7-7700K/nightly-x86_64-pc-windows-msvc
or
i7-3770/nightly-x86_64-unknown-linux-gnu

1 Like
#2

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

1 Like
#3

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

#4

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
#5

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.

7 Likes
#6

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.

#7

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.