4 ms·

This is one of the best technical articles I've ever read, thanks. It wasn't clear to me what "organize the likely path instead as untaken" means.

BeeOnRope 7y ago
Yes, it is confusing: it should probably say "organize the code so that the likely branch outcome is the fall-through one". Does that make sense? Basically the "jump" should be the unusual case. You can always organize the code like that, but sometimes the compiler needs a little help. Consider the following function, which just sets negative values to zero. void zero_threshold(int *data, size_t len) { for (size_t i = 0; i < len; i++) { int x = data[i]; if (x < 0) data[i] = 0; } } On gcc this compiles to something like: .L4: mov edx, DWORD PTR [rdi] test edx, edx jns .L3 mov DWORD PTR [rdi], 0 .L3: add rdi, 4 cmp rdi, rax jne .L4 The `jns` is the jump that reflects the if (x < 0) statement and it jumps in the case the number is >= 0 (i.e., non-negative). gcc organizes it like this because it involves a only a single jump. However if you expect the non-negative case to be the common one, this is will limit the throughput of the code. It would be better to compile it like this: .L4: mov edx, DWORD PTR [rdi] test edx, edx js .L10 .L3: add rdi, 4 cmp rdi, rax jne .L4 .L1: ret .L10: mov DWORD PTR [rdi], 0 jmp .L3 This now involves two jumps when the number is negative: it has to jump out to the extra bit of code outside the main body of the function at .L10, and then jump back, but the common case is now "fall through" so this could execute at close to 1 per cycle, twice as fast as the other version. You can get gcc to produce the second code by changing the condition to __builtin_expect(x < 0, 0): https://godbolt.org/z/2Qgk7p https://godbolt.org/z/2Qgk7p Of course, this code would be much off vectorized, but it's just an example (and the same principle applies to jumps in vectorized code).
- RivieraKid 7y ago
  It makes complete sense now, appreciate the explanation.
- craz8 7y ago
  I’ve worked in 1 company where we had tools that would re-organize the code to make the common code path be the fall through as much as possible This was done before linking, based on analysis of the common paths from a running program What this also did - which was the important bit at the time - was move all the error code to pages that wouldn’t be loaded for most users So it moved error handling out of common code pages and changed branch instructions to mostly fall through This was many years ago - do similar tools exist in the OSS community?
  - BeeOnRope 7y ago
    All good compilers do this today. They use heuristics to guess what the likely outcome of branches, but you can provide them specific information with profile guided optimization, or with manual branch hits (the __builtin_expect I used in the example above is one such hint). Similarly, you can annotate certain functions or paths "hot" or "cold", and compilers even understand that functions like abort() are cold (they can be called at most once, after all) and hence paths leading up to them are also cold. Similarly, JIT compilers use the runtime observed branching behavior to organize branches so that fall-through is the common case.
  - Twirrim 7y ago
    Grab a look at the FDO and AutoFDO sections from GCC's wiki: https://gcc.gnu.org/wiki/AutoFDO/Tutorial https://gcc.gnu.org/wiki/AutoFDO/Tutorial You'll also find it's referred to as Profile Guided Optimization, there's docs here for clang: https://clang.llvm.org/docs/UsersManual.html#profile-guided-optimization https://clang.llvm.org/docs/UsersManual.html#profile-guided-...

BeeOnRope 7y ago

Yes, it is confusing: it should probably say "organize the code so that the likely branch outcome is the fall-through one". Does that make sense? Basically the "jump" should be the unusual case. You can always organize the code like that, but sometimes the compiler needs a little help. Consider the following function, which just sets negative values to zero. void zero_threshold(int *data, size_t len) { for (size_t i = 0; i < len; i++) { int x = data[i]; if (x < 0) data[i] = 0; } } On gcc this compiles to something like: .L4: mov edx, DWORD PTR [rdi] test edx, edx jns .L3 mov DWORD PTR [rdi], 0 .L3: add rdi, 4 cmp rdi, rax jne .L4 The `jns` is the jump that reflects the if (x < 0) statement and it jumps in the case the number is >= 0 (i.e., non-negative). gcc organizes it like this because it involves a only a single jump. However if you expect the non-negative case to be the common one, this is will limit the throughput of the code. It would be better to compile it like this: .L4: mov edx, DWORD PTR [rdi] test edx, edx js .L10 .L3: add rdi, 4 cmp rdi, rax jne .L4 .L1: ret .L10: mov DWORD PTR [rdi], 0 jmp .L3 This now involves two jumps when the number is negative: it has to jump out to the extra bit of code outside the main body of the function at .L10, and then jump back, but the common case is now "fall through" so this could execute at close to 1 per cycle, twice as fast as the other version. You can get gcc to produce the second code by changing the condition to __builtin_expect(x < 0, 0): https://godbolt.org/z/2Qgk7p https://godbolt.org/z/2Qgk7p Of course, this code would be much off vectorized, but it's just an example (and the same principle applies to jumps in vectorized code).

RivieraKid 7y ago
It makes complete sense now, appreciate the explanation.
craz8 7y ago
I’ve worked in 1 company where we had tools that would re-organize the code to make the common code path be the fall through as much as possible This was done before linking, based on analysis of the common paths from a running program What this also did - which was the important bit at the time - was move all the error code to pages that wouldn’t be loaded for most users So it moved error handling out of common code pages and changed branch instructions to mostly fall through This was many years ago - do similar tools exist in the OSS community?
- BeeOnRope 7y ago
  All good compilers do this today. They use heuristics to guess what the likely outcome of branches, but you can provide them specific information with profile guided optimization, or with manual branch hits (the __builtin_expect I used in the example above is one such hint). Similarly, you can annotate certain functions or paths "hot" or "cold", and compilers even understand that functions like abort() are cold (they can be called at most once, after all) and hence paths leading up to them are also cold. Similarly, JIT compilers use the runtime observed branching behavior to organize branches so that fall-through is the common case.
- Twirrim 7y ago
  Grab a look at the FDO and AutoFDO sections from GCC's wiki: https://gcc.gnu.org/wiki/AutoFDO/Tutorial https://gcc.gnu.org/wiki/AutoFDO/Tutorial You'll also find it's referred to as Profile Guided Optimization, there's docs here for clang: https://clang.llvm.org/docs/UsersManual.html#profile-guided-optimization https://clang.llvm.org/docs/UsersManual.html#profile-guided-...