3 ms·
On my Cascade Lake processor "-mllvm -x86-cmov-converter=false" almost halves the performance of the binary search: | Benchmark | gcc | clang | clang -cmo
by bjourne 3y ago
On my Cascade Lake processor "-mllvm -x86-cmov-converter=false" almost halves the performance of the binary search:
| Benchmark | gcc | clang | clang -cmov |
|-----------|------|-------|-------------|
| slow u32 | 23.4 | 46.7 | 45.8 |
| fast u32 | 18.1 | 19.8 | 31.4 |
The numbers are nanoseconds/bsearch on a 100mb uint32 array. Seem to me that clang (15.0.7) is just much worse at optimizing this particular piece of code than gcc (13.2.1). You can see the assembly here https://godbolt.org/z/cbx5Kdjs6 https://godbolt.org/z/cbx5Kdjs6. The gcc assembly looks way cleaner to me.
- mhdm 3y agoThen you'll want to look at https://mhdm.dev/posts/sb_lower_bound/#prefetching https://mhdm.dev/posts/sb_lower_bound/#prefetching 100mb is large enough that the branchy version turns out to have a slight advantage, more due to quirks of x86 (speculative execution) rather than being better.
- bjourne 3y agoSo I spent too much time benchmarking: | Entries | gcc | gcc+pref. | clang | clang+pref. | clang -cmov | clang -cmov+pref. | |---------|-----|-----------|-------|-------------|-------------|-------------------| | 0.5 | 210 | 88 | 213 | 191 | 109 | 93 | | 1.0 | 231 | 107 | 235 | 211 | 134 | 112 | | 2.0 | 289 | 168 | 306 | 275 | 231 | 179 | | 5.0 | 369 | 231 | 389 | 343 | 338 | 239 | | 10 | 413 | 268 | 437 | 384 | 410 | 276 | | 25 | 469 | 311 | 490 | 435 | 506 | 318 | | 50 | 515 | 346 | 537 | 478 | 586 | 356 | | 100 | 564 | 387 | 588 | 522 | 670 | 399 | Entries are in millions and times in ns per bsearch call. Prefetching does all the difference, but perhaps not for the right reason. On my machine (broadwell) the two prefetches that you suggested makes gcc emit the cmovb that clang with -cmov uses. The second one is enough to make it prefer cmovb but not the first one. Maybe a hand-hacked assembly loop based on the code gcc emits but without the prefetches would run even faster.