mualphaomegaepsilon / branchhinting

C++ Macro definitions for easy branch hinting.

C++ Macro definitions for easy Static Branch Prediction.

BranchHinting is a minimalistic macro library used to perform Static Branch Prediction, a technique used to hint the compiler about the likeliness of one or more branching conditions, so that the code can be streamlined into being more I-cache friendly.
The desired behaviour is obtained through the use of the __builtin_expect keyword which is a GCC Built-in function.

Be aware that using this technique might give better or worse performance based on the quality of the hinting, so use this tool wisely.

Platform	Build Status
Linux

Table of contents

• Download
• Dependencies
• Source code integration
• Disabling macros
• Testing
• CMake support
• Doxygen support
• Compilers supported
• PGO vs SBP
• Generated x86 assembly
• Future upgrades
• Font credits

Download

The command below will download the content of this repository:

$ git clone https://github.com/MuAlphaOmegaEpsilon/BranchHinting

Dependencies

This project consists of a header-only file with no include dependencies.

Source code integration

Give a look at how to change the source code changes when you want to integrate the macros of this library:

+ #include <BranchHinting.hpp> // C++ Macro definitions for easy Static Branch Prediction.

bool mostlyTrue (); // A bool function that most of the time returns "true"
bool mostlyFalse (); // A bool function that most of the time returns "false"

void foo_one ();
void foo_two ();
void foo_three ();
void foo_four ();

int main ()
{
    bool almostAlwaysTrue = mostlyTrue ();
    bool almostAlwaysFalse = mostlyFalse ();
    bool otherCondition = ... ;

-   if (almostAlwaysTrue || otherCondition == false)
+   if (LIKELY (almostAlwaysTrue) || otherCondition == false)
        foo_one ();
    else
        foo_two ();

-   if (almostAlwaysFalse)
+   unlikely_if (almostAlwaysFalse)
        foo_three ();
-   else if (almostAlwaysTrue)
+   else likely_if (almostAlwaysTrue)
        foo_four ();

    return 0;
}

Disabling macros

The hints to the compiler can be disabled just by defining a single macro.

#define DISABLE_BRANCH_HINTING

Testing

Just run the script contained in the repository. After testing has ended the script will automatically clean all the files created.

./runTests.sh

CMake support

You only need to add the two commands below to your CMakeLists.txt file in order to use this macro library:

ADD_SUBDIRECTORY (${PROJECT_SOURCE_DIR}/path_to_BranchHinting/)	
TARGET_LINK_LIBRARIES (your_executable PUBLIC BranchHinting)	

Doxygen support

Doxygen is supported out of the box: just run it and check inside the docs folder:

doxygen

Compilers supported

GCC, Clang and ICC correctly support the macros used to hint about likely taken branches; MSVC on the other hand doesn't support at all such features, and encourages the use of PGO instead.

In case you are using this library as part of a cross-platform project that will also run on Windows through MSVC:
BranchHinting is automatically disabled when using the MSVC compiler, and you simply won't get the bonuses/maluses that comes from using it; apart from this everything will work fine.

PGO vs SBP

Profile Guided Optimization is a great tool, there's no doubt about it, but it has its pros and cons as well as Static Branch Prediction.

Remember: BranchHinting falls under SBP

If the test workload does not match the way the program is actually used, the performed optimizations might actually do more harm than good. For this reason, is it often hard to use PGO for libraries. Libraries can be used in many–sometimes widely different–scenarios. Unless the use cases are indeed similar, it is usually better to rely exclusively on Static Branch Prediction using __builtin_expect.

<What Every Programmer Should Know About Memory, page 85 - Akkadia>

Generated x86 assembly

Look at how these two snippets of code differ in the generated assembly using GCC 8.2 with the -O3 flag on the GodBolt.org compiler explorer website.
You can notice how the compiler optimizes the path for the likely-tagged branches on the right side:

• Lines 5-6: the result of mostlyTrue () is saved in the %EBP register.
• Lines 7-8: the result of mostlyFalse () is saved in the %EBX register.
• Lines 9-10: the CPU jumps to execute foo_two () only when mostlyTrue () returned false, which is known to be unlikely.
• Line 11: the CPU calls foo_one ().
• Lines 12-13: the CPU jumps to execute foo_three () only when mostlyFalse () returned true, which is known to be unlikely.
• Line 14: the CPU calls foo_four () regardless, since it is already on the path that checked that mostlyTrue () actually returned true.

Future upgrades

C++20 is probably going to integrate natively the [[likely]] and [[unlikely]] attributes for static branch prediction.
I will take into account the possibility of upgrading BranchHinting once the new standard will be officially supported by most compilers.

Here you can find the latest revision of the attribute proposal, while here you can find the original 2016 proposal which also presents some insights based on statistical data regarding the effectiveness of static branch prediction.

Font credits

The font used for the logo is free for non-lucrative purposes: Pretty Trees, created by CloutierFontes.