3 ms·

const branching

2 points by kris-jusiak 2y ago

kris-jusiak 2y ago
Hardware branch prediction is very powerful (https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html 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-cycles/ http://ithare.com/infographics-operation-costs-in-cpu-clock-...). Branchless computing (https://www.youtube.com/watch?v=g-WPhYREFjk 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 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 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 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 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://docs.kernel.org/staging/static-keys.html - https://gcc.gnu.org/onlinedocs/gcc/Extended-Asm.html https://gcc.gnu.org/onlinedocs/gcc/Extended-Asm.html - https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html https://www.intel.com/content/www/us/en/developer/articles/t... - https://www.agner.org/optimize/instruction_tables.pdf https://www.agner.org/optimize/instruction_tables.pdf - https://www.felixcloutier.com/x86 https://www.felixcloutier.com/x86 - https://uops.info/table.html https://uops.info/table.html - https://arxiv.org/abs/2308.14185 https://arxiv.org/abs/2308.14185

2 points by kris-jusiak 2y ago

Hardware branch prediction is very powerful (https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html 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-cycles/ http://ithare.com/infographics-operation-costs-in-cpu-clock-...). Branchless computing (https://www.youtube.com/watch?v=g-WPhYREFjk 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 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 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 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 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://docs.kernel.org/staging/static-keys.html - https://gcc.gnu.org/onlinedocs/gcc/Extended-Asm.html https://gcc.gnu.org/onlinedocs/gcc/Extended-Asm.html - https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html https://www.intel.com/content/www/us/en/developer/articles/t... - https://www.agner.org/optimize/instruction_tables.pdf https://www.agner.org/optimize/instruction_tables.pdf - https://www.felixcloutier.com/x86 https://www.felixcloutier.com/x86 - https://uops.info/table.html https://uops.info/table.html - https://arxiv.org/abs/2308.14185 https://arxiv.org/abs/2308.14185