4 ms·

Curiously, most variations of the C++ version run only half as fast as they should on Intel Haswell chips, probably because of branch prediction failures I hav

by nkurz 11y ago

Curiously, most variations of the C++ version run only half as fast as they should on Intel Haswell chips, probably because of branch prediction failures I haven't looked at the code yet (time for bed) but this note from Agner seems like it might be relevant: 3.8 Branch prediction in Intel Haswell, Broadwell and Skylake The branch predictor appears to have been redesigned in the Haswell, but very little is known about its construction. The measured throughput for jumps and branches varies between one branch per clock cycle and one branch per two clock cycles for jumps and predicted taken branches. Predicted not taken branches have an even higher throughput of up to two branches per clock cycle. The high throughput for taken branches of one per clock was observed for up to 128 branches with no more than one branch per 16 bytes of code. If there is more than one branch per 16 bytes of code then the throughput is reduced to one jump per two clock cycles. If there are more than 128 branches in the critical part of the code, and if they are spaced by at least 16 bytes, then apparently the first 128 branches have the high throughput and the remaining have the low throughput. These observations may indicate that there are two branch prediction methods: a fast method tied to the μop cache and the instruction cache, and a slower method using a branch target buffer. http://www.agner.org/optimize/microarchitecture.pdf http://www.agner.org/optimize/microarchitecture.pdf At a glance, the symptoms seem like this might match. Separately, I think there is still a limit of 3 branches per 16B before the branch prediction starts to fail. It's rare to hit this in normal code, but something this optimized might.

wscott 11y ago
I found the branch prediction claim to be a bit weak without perfmon data to support it. The references point out that the Intel 'popcnt %r1, %r2' instruction has a false input dependency on the output variable and neither gcc nor clang seem to know about that and adjust register scheduling. This is usually caused because the chip uses the same scheduling bucket used for instructions like 'add'. So putting 'popcnt %rax, %rax' inside a tight loop will prevent that loop from being unrolled in the processor. As a result the code is highly sensitive to random changes because the compiler occasionally gets lucky and breaks the chain.
nly 11y ago
I've recently experienced what I believe was likely branch predictor failure. I rewrote essentially the same algorithm, with the same complexity, in a completely new way, to reduce constant factors. The new code was beautiful, and I was expecting perhaps 15-20% performance improvement. (40% of the runtime in the old version was in one function, the new version should, and did, call that function with less data to grind on average). Memory access patterns should be identical. Grand. So what happened with my standard benchmark on Haswell (GCC 5.3, -march=native -O2)? Old version, without PGO: ~8 minutes (baseline) Old version, with PGO on: ~9 minutes (yes, PGO made it slower) New version, without PGO: 11 minutes (60% slower) New version, with PGO on: 7 minutes (~15% faster) All of these benchmarks were replicated with a common set of functions tagged noinline, and I inspected the assembly to see if there was a difference with regard to loop unrolling. Nope, no unrolling. Afaict it appeared to be entirely to do with the way GCC had laid out code with respect to branches. The differences were minor in key areas and seemed like arbitrary compiler choices. I eventually narrowed this down with callgrinds branch-predictor simulator to a few hot spots. I added a redundant if-statement to check for and short-circuit a common case, even though it shouldn't have mattered, and a few __builtin_expects, and suddenly I was getting the 15% speedup without PGO.
melted 11y ago
Don't know about Clang/LLVM, but in GCC you can give the compiler a hint if a branch is likely to be taken. As far as I can tell from disassembly, most of the time it just puts that branch first in the instruction stream, but I have measured significant benefit in very hot code paths.
nkurz 11y ago
I've now looked at it more closely, and tested on Skylake and Haswell. I don't think the case described in https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67153 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67153 is actually a bug in either the compiler or the processor. Rather, it's the behavior you would expect if the compiler (at compile time) guesses wrong about whether a branch is likely to be taken or not. Which choice is fastest on the depends on the runtime word list, and thus there is no reason to fault the compiler for either choice. For the processor, the difference is simply that a "branch not taken" is faster than a branch taken. The fast version involves a loop that executes in a single cycle: 77.21 │210:┌─→add $0x4,%rcx 0.66 │ │ cmp %rcx,%r8 │ │↓ je 260 4.20 │219:│ mov (%rcx),%edi 0.88 │ │ test %r9d,%edi │ └──jne 210 The cmp/je and test/jne instructions fuse into on µop each, so that (incredibly) the processor can execute the remaining 4 fused µops at an iteration per cycle. If the loop is rearranged so that the middle branch is taken, each iteration takes a minimum of 2 cycles instead. The solution (as the author mentions in a parenthetical) is to give more information to the compiler with "__builtin_expect". I wasn't able to test on Sandy Bridge or earlier, but my strong guess would be that Haswell and Skylake have a potential speedup, rather than a regression. I'll try to add a comment to the bug later tonight.

by nkurz 11y ago

wscott 11y ago

I found the branch prediction claim to be a bit weak without perfmon data to support it. The references point out that the Intel 'popcnt %r1, %r2' instruction has a false input dependency on the output variable and neither gcc nor clang seem to know about that and adjust register scheduling. This is usually caused because the chip uses the same scheduling bucket used for instructions like 'add'. So putting 'popcnt %rax, %rax' inside a tight loop will prevent that loop from being unrolled in the processor. As a result the code is highly sensitive to random changes because the compiler occasionally gets lucky and breaks the chain.

nly 11y ago

I've recently experienced what I believe was likely branch predictor failure. I rewrote essentially the same algorithm, with the same complexity, in a completely new way, to reduce constant factors. The new code was beautiful, and I was expecting perhaps 15-20% performance improvement. (40% of the runtime in the old version was in one function, the new version should, and did, call that function with less data to grind on average). Memory access patterns should be identical. Grand. So what happened with my standard benchmark on Haswell (GCC 5.3, -march=native -O2)? Old version, without PGO: ~8 minutes (baseline) Old version, with PGO on: ~9 minutes (yes, PGO made it slower) New version, without PGO: 11 minutes (60% slower) New version, with PGO on: 7 minutes (~15% faster) All of these benchmarks were replicated with a common set of functions tagged noinline, and I inspected the assembly to see if there was a difference with regard to loop unrolling. Nope, no unrolling. Afaict it appeared to be entirely to do with the way GCC had laid out code with respect to branches. The differences were minor in key areas and seemed like arbitrary compiler choices. I eventually narrowed this down with callgrinds branch-predictor simulator to a few hot spots. I added a redundant if-statement to check for and short-circuit a common case, even though it shouldn't have mattered, and a few __builtin_expects, and suddenly I was getting the 15% speedup without PGO.

melted 11y ago

Don't know about Clang/LLVM, but in GCC you can give the compiler a hint if a branch is likely to be taken. As far as I can tell from disassembly, most of the time it just puts that branch first in the instruction stream, but I have measured significant benefit in very hot code paths.

nkurz 11y ago

I've now looked at it more closely, and tested on Skylake and Haswell. I don't think the case described in https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67153 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67153 is actually a bug in either the compiler or the processor. Rather, it's the behavior you would expect if the compiler (at compile time) guesses wrong about whether a branch is likely to be taken or not. Which choice is fastest on the depends on the runtime word list, and thus there is no reason to fault the compiler for either choice. For the processor, the difference is simply that a "branch not taken" is faster than a branch taken. The fast version involves a loop that executes in a single cycle: 77.21 │210:┌─→add $0x4,%rcx 0.66 │ │ cmp %rcx,%r8 │ │↓ je 260 4.20 │219:│ mov (%rcx),%edi 0.88 │ │ test %r9d,%edi │ └──jne 210 The cmp/je and test/jne instructions fuse into on µop each, so that (incredibly) the processor can execute the remaining 4 fused µops at an iteration per cycle. If the loop is rearranged so that the middle branch is taken, each iteration takes a minimum of 2 cycles instead. The solution (as the author mentions in a parenthetical) is to give more information to the compiler with "__builtin_expect". I wasn't able to test on Sandy Bridge or earlier, but my strong guess would be that Haswell and Skylake have a potential speedup, rather than a regression. I'll try to add a comment to the bug later tonight.