Zero/Minimal overhead static/const branching

Hardware branch prediction is very powerful (https://www.intel.com/content/www/us/en/developer/articles/t...) but it's also not perfect and costly misdirections may happen (http://ithare.com/infographics-operation-costs-in-cpu-clock-...).

Branchless computing (https://www.youtube.com/watch?v=g-WPhYREFjk) is a technique which may help a lot with mitigating the overhead of branching.

Alternative way, coming from linux kernel (https://docs.kernel.org/staging/static-keys.html) is to leverage knowledge about branches direction and literally change the instructions via run-time code patching to avoid the potential branching overhead all together.

When to go for such extreme solution? When performance really matters:

  - `and` branches are known at compile-time
  - `or` branches are not changing often at run-time
      - `and/or` branches are expensive to compute/require memory access
      - `and/or` branches are hard to learn by the hardware branch predictor due to their random nature

Some examples include logging, tracing, configuration, hot-path, algo, etc.

> https://github.com/boost-ext/sb - x86-64/linux/gcc/clang moves the solution to user space (for run-time) as well as to compile-time with C++20.

> static_branch - Minimal overhead run-time branch (https://godbolt.org/z/797WeYYGK) / (nop=not taken / jmp=taken)

    void fun() { // can be inlined/constexpr or not
      if (sb::static_branch<"semi run-time branch">::get()) {
        std::puts("taken");
      } else {
        std::puts("not taken");
      }
    }

    int main() {
      fun(); // not taken
    
      sb::static_branch<"semi run-time branch">::set(true);
      fun(); // taken
    
      sb::static_branch<"semi run-time branch">::set(false);
      fun(); // not taken
    }

    main: // $CXX -O3
      lea rdi, [rip + .L.str.1]
      nop # code patching (nop->nop)
      lea rdi, [rip + .L.str.2]
     .Ltmp1:
      call puts@PLT # not taken
    
      call static_branch<"semi run-time branch">::set(true) # relatively slow
    
      lea rdi, [rip + .L.str.1]
      jmp .Ltmp2 # code patching (nop->jmp)
      lea rdi, [rip + .L.str.2]
     .Ltmp2:
      call puts@PLT # taken
    
      call static_branch<"semi run-time branch">::set(false) # relatively slow
    
      lea rdi, [rip + .L.str.1]
      nop # code patching (nop->nop)
      lea rdi, [rip + .L.str.2]
     .Ltmp3:
      call puts@PLT # not taken
    
    .L.str.1: .asciz "taken"
    .L.str.2: .asciz "not taken"

> const_branch - Zero overhead compile-time branch (https://godbolt.org/z/xEboP8WYe)

    template<auto tag = []{}> // Note: `tag` is required to delay `fun`
                              // instantiation as get has to be dependent
    auto fun() {
      if constexpr (sb::const_branch<"compile-time branch">::get<tag>()) {
        std::puts("taken");
      } else {
        std::puts("not taken");
      }
    }

    int main() {
      fun(); // not taken
    
      static_assert(sb::const_branch<"compile-time branch">::set<true>());
      fun(); // taken
    
      static_assert(sb::const_branch<"compile-time branch">::set<false>());
      fun(); // not taken
    }

    main: // $CXX -O3
      lea  rbx, [rip + .L.str.1]
      mov  rdi, rbx
      call puts@PLT # not taken
    
      lea  rdi, [rip + .L.str.2]
      call puts@PLT # taken
    
      mov  rdi, rbx
      call puts@PLT # not taken
    
      xor  eax, eax # return 0
      ret
    
    .L.str.1: .asciz "not taken"
    .L.str.2: .asciz "taken"

Acknowledgments

- https://docs.kernel.org/staging/static-keys.html - https://gcc.gnu.org/onlinedocs/gcc/Extended-Asm.html - https://www.intel.com/content/www/us/en/developer/articles/t... - https://www.agner.org/optimize/instruction_tables.pdf - https://www.felixcloutier.com/x86 - https://uops.info/table.html - https://arxiv.org/abs/2308.14185