The code assumes the comparison is cheap, and if you happen to find the match on the first line, you still do N comparisons until the result is returned. Also, in my experience, the times I used a binary search, the size of the array wasn’t a fixed size.
I don’t think that not optimizing for the “quick” case is an issue: using a “regular” binary search, half the elements require exactly log N comparisons, and 7/8 of the elements require at least log N - 2 comparisons, so by always doing log N comparisons we aren’t losing much.
That said, the D code gets optimized to use conditional moves, eliminating all branching. I haven’t been able to convince the compiler to do the same with the Zig version, you can try yourself here.
Passing the correct flag to zig (-OReleaseFast instead of -Drelease-fast) makes the code near identical.
-Drelease-fast was the old flag used by the zig build system while -OReleaseFast is the flag used when invoking the compiler directly. The build system now uses -Doptimize=ReleaseFast. Not sure why godbolt didn’t show you an error…
Edit: looks like zig build-exe has a -D option to define c macros… that’s definitely a footgun :/
-D[macro]=[value] Define C [macro] to [value] (1 if [value] omitted)
The code assumes the comparison is cheap, and if you happen to find the match on the first line, you still do N comparisons until the result is returned. Also, in my experience, the times I used a binary search, the size of the array wasn’t a fixed size.
*log N comparisons
I don’t think that not optimizing for the “quick” case is an issue: using a “regular” binary search, half the elements require exactly log N comparisons, and 7/8 of the elements require at least log N - 2 comparisons, so by always doing log N comparisons we aren’t losing much.
That said, the D code gets optimized to use conditional moves, eliminating all branching. I haven’t been able to convince the compiler to do the same with the Zig version, you can try yourself here.
Passing the correct flag to zig (
-OReleaseFastinstead of-Drelease-fast) makes the code near identical.-Drelease-fastwas the old flag used by the zig build system while-OReleaseFastis the flag used when invoking the compiler directly. The build system now uses-Doptimize=ReleaseFast. Not sure why godbolt didn’t show you an error…Edit: looks like zig build-exe has a -D option to define c macros… that’s definitely a footgun :/
Ah, that’s a dumb mistake to make, thanks for correcting it!
That’s neat. I was curious what the Zig code would look like. Pretty similar to the my version in D.
Performance wise, the D compiler (ldc in this case) generatea pretty tight code, three instructions per comparison, using conditional moves.
But I haven’t done any serious performance benchmarks. That would be an interesting exercise.