kris-jusiak

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

# Meta-Programming is one of the C++ super-powers

Traditional meta-programming model in C++ is very powerful but not the easiest to grasp. Mainly because it has different syntax than 'normal' C++ with a lot of angle brackets, it's functional, immutable, etc.

There are some great template meta-programming libraries available such as boost.mp11 - https://www.boost.org/doc/libs/1_85_0/libs/mp11/doc/html/mp1... which make template meta-programming much simpler. The question is - Can we do better? And if so, what are the trade-offs? All in all, wouldn't be great to be able to write the same code for run-time and compile-time and/or debug compile-time code at run-time?

Reflection for C++ - https://wg21.link/P2996 - introduced a new meta-programming model which is value/consteval based and can greatly improve the experience. Together with reflection is a very powerful combination but it also has its own set of trade-offs such as slower compilation-times.

This post is about `mp` - https://github.com/boost-ext/mp - meta-programming library which supports - similar to P2996 - meta-programming model for easier transition as it supports C++20 (msvc, gcc, clang), has a bit faster compilation times than P2996, but mostly, it makes meta-programming a 'normal' C++. In the mp world no difference between run-time and compile-time, whole standard library can be leveraged and it has reflection integration with C++20 using https://github.com/boost-ext/reflect. Of course it has it own set of trade-offs but, IMHO, it has a lot of potential and it's super fan.

> Example (API)

    // mp::meta
    static_assert(mp::meta<int> == mp::meta<int>);
    static_assert(mp::meta<int> != mp::meta<void>);
    static_assert(typeid(mp::meta<int>) == typeid(mp::meta<void>));
    
    // mp::type_of
    constexpr mp::info meta = mp::meta<int>;
    mp::type_of<meta> i{}; // same as int i{};
    mp::type_of<mp::meta<bool>> b = true; // same as bool b = true;
    
    // mp::apply
    template<class...> struct type_list{ };
    static_assert(std::is_same_v<type_list<int, int>, mp::apply_t<type_list, mp::array{meta, meta}>>);
    
    // mp::invoke
    static_assert(not mp::invoke<std::is_const>(meta));
    static_assert(std::is_same_v<const int, mp::type_of<mp::invoke<std::add_const>(meta)>>);

    // hello world
    template<size_t N, class... Ts>
    using at_c = mp::type_of<std::array{mp::meta<Ts>...}[N]>;

    static_assert(std::is_same_v<int, at_c<0, int, bool, float>>);
    static_assert(std::is_same_v<bool, at_c<1, int, bool, float>>);
    static_assert(std::is_same_v<float, at_c<2, int, bool, float>>);
    
    // ranges
    template<class... Ts>
    constexpr mp::vector ranges =
        std::array{mp::meta<Ts>...}
      | std::views::drop(1)
      | std::views::reverse
      | std::views::filter([](auto m) { return mp::invoke<std::is_integral>(m); })
      | std::views::transform([](auto m) { return mp::invoke<std::add_const>(m); })
      | std::views::take(2)
      ;
    
    static_assert(std::is_same_v<
      std::variant<const int, const short>, 
      mp::apply_t<std::variant, ranges<double, void, const short, int>>
    >);

    // reflection (requires https://github.com/boost-ext/reflect)
    struct foo {
      int a;
      bool b;
      float c;
    };

    foo f{.a = 42, .b = true, .c = 3.2f};

    constexpr mp::vector v = reflexpr(f)
      | std::views::filter([&](auto meta) { return member_name(meta, f) != "b"; })
      ;

    static_assert(std::tuple{42, 3.2f} == unreflexpr<std::tuple, v>(f));

> Full example - standalone - https://godbolt.org/z/Mjcxedzzj

> Full example - reflection - https://godbolt.org/z/ds3KMGhqP

> Library - https://github.com/boost-ext/mp

> Supported compilers - https://godbolt.org/z/qarWdbK79

> Compilation times benchmark - https://boost-ext.github.io/mp

Compile-time first unit-testing is a super power of modern C++.

It catches errors earlier and helps (to a certain degree) avoiding memory leaks and undefined behaviors. However, the main problem facing compile-time tests are bad error messages. With C++20 and, especially, with clang that can be improved a lot to a degree sometimes even better than at run-time. Running tests at compile-time is useful and more and more powerful with each new standard, but there is also a strong case for run-time execution as well. Firstly, not all tests can be executed at compile-time due to constexpr limitations (for example goto/exceptions/reinterpret_cast/... in C++20). Additionally there is case for the code coverage, debugging and CI reporting. Therefore, the combination of both seems the most powerful: compile-time tests with nicer error messages and run-time execution on top (with ability to choose the execution model globally and/or for specific tests).

https://github.com/boost-ext/ut2 is trying to accomplish just that.

https://wg21.link/P2996 allows form of stateful meta-programming without using friend injection.

Meta-counter is pretty easy - https://godbolt.org/z/91M56a5dd as we just iterate over complete instantiations of the counter class (tricky part is to force the instantiation).

The following is a bit more complex example of stateful meta-programming - compile-time type list.

Firstly, C++20 version (based on friend injection) - works on gcc,clang,msvc

    template<class...> struct type_list {};

    namespace detail {
    template<auto> struct nth { auto friend get(nth); auto friend get(nth); };         
    template<auto N, class T> struct set { auto friend get(nth<N>) { return T{}; } }; 
    template<class T, template<class...> class TList, class... Ts> auto append(TList<Ts...>) -> TList<Ts..., T>;
    } // namespace detail

    template<class T, auto N = 0, auto unique = []{}>
    consteval auto append() {
        if constexpr (requires { get(detail::nth<N>{}); }) {
            append<T, N+1, unique>();
        } else if constexpr (N == 0) {
            void(detail::set<N, type_list<T>>{});
        } else {
            void(detail::set<N, decltype(detail::append<T>(get(detail::nth<N-1>{})))>{});
        }
    }

    template<auto unique = []{}, auto N = 0>
    consteval auto get_list() {
        if constexpr (requires { get(detail::nth<N>{}); }) {
            return get_list<unique, N+1>();
        } else if constexpr (N == 0) {
            return type_list{};
        } else {
            return get(detail::nth<N-1>{});
        }
    }

    int main() {
      static_assert(typeid(get_list()) == typeid(type_list<>));

      append<int>();
      static_assert(typeid(get_list()) == typeid(type_list<int>));

      append<float>();
      static_assert(typeid(get_list()) == typeid(type_list<int, float>));
    }

Full example -> https://godbolt.org/z/axPT88e3c

Now, C++26 version with the reflection proposal (based on injecting classes with members) - works on EDG

    template<class...> struct type_list{};

    namespace detail {
    template<auto> struct type_list;
    consteval auto append(auto new_member) {
      std::vector<std::meta::info> members{};
      for (auto i = 0;; ++i) {
        if (auto mi = substitute(^type_list, { std::meta::reflect_value(i) }); std::meta::is_incomplete_type(mi)) {
          std::vector<std::meta::nsdm_description> new_members{};
          for (auto member: members) {
            new_members.push_back({std::meta::type_of(member), {.name = std::meta::name_of(member)}});
          }
          const char name[]{'_', char(i+'0'), 0}; // there are defo better ways to do that
          new_members.push_back({{new_member}, {.name = std::string_view(name, 2)}});
          return define_class(mi, new_members);
        } else {
          members = std::meta::nonstatic_data_members_of(mi);
        }
      }
    }

    consteval auto get_list() {
      std::vector<std::meta::info> members{};
      for (auto i = 0;; ++i) {
        if (auto mi = substitute(^type_list, { std::meta::reflect_value(i) }); std::meta::is_incomplete_type(mi)) {
          break;
        } else {
          members = std::meta::nonstatic_data_members_of(mi);
        }
      }
      std::vector<std::meta::info> new_members{};
      for (auto member : members) { new_members.push_back(std::meta::type_of(member)); }
      return substitute(^::type_list, new_members);
    }
    } // namespace detail

    template<class T> using append = [:detail::append(^T):];
    template<auto = []{}> using get_list = [:detail::get_list():];

    int main() {
      static_assert(typeid(get_list<>) == typeid(type_list<>));

      append<int>();
      static_assert(typeid(get_list<>) == typeid(type_list<int>));

      append<float>();
      static_assert(typeid(get_list<>) == typeid(type_list<int, float>));
    }

Full example -> https://godbolt.org/z/5s8YvYqqr

Resources:

- https://reddit.com/r/cpp/comments/1890jr9/reflectcpp_automat... - https://www.reddit.com/r/cpp/comments/18b8iv9/c20_to_tuple_w...

Auto-tuning version of constexpr get_name for members

    struct foo {
        int bar;
        int baz;
    };

    static_assert("bar"sv == get_name<0, foo>);
    static_assert("baz"sv == get_name<1, foo>);

Basic idea:

    template <auto Ptr> [[nodiscard]] consteval auto get_name() -> std::string_view { 
        return std::source_location::current().function_name();
    }
    template <class T> extern const T external; // magic happens here
    constexpr auto ptr(auto&& t) { auto&& [p1] = t; return &p1; }

    struct foo { int field; };

    std::cout << get_name<ptr(external<foo>)>(); // prints ...field...

Auto-tuning the name (to avoid ifdefs for compilers): // define a $struct$.$filed$ to find the parsing requirements for given compiler

    struct $struct$ {
        int $field$; // pick some name / $ is valid identifier now
    };
    constexpr auto $name = get_name_impl<0, struct$>;
    constexpr auto $end = $name.substr($name.find("$field$") + sizeof("$field$") - 1);
    constexpr auto $begin = $name[$name.find("$field$") - 1];

    template <auto N, class T>
    constexpr auto get_name = [] {
        const auto name = get_name_impl<N, T>;
        const auto begin = name.find(end);
        const auto tmp = name.substr(0, begin);
        return tmp.substr(tmp.find_last_of(begin) + 1);
    }();

Full example - https://godbolt.org/z/MWhf6voTs

Following on https://reddit.com/r/cpp/comments/1890jr9/reflectcpp_automat... the following is simple implementation of to_tuple with names (compile-time names) which seems to work on gcc,clang,msvc*

It uses extern combined with source_location to get the field name.

Example

    struct foo {
        int first_field;
        int second_field;
    };

    constexpr auto t = to_tuple(foo{.first_field = 42, .second_field = 87});
    static_assert("first_field"sv == std::get<0>(t).name and 42 == std::get<0>(t).value);
    static_assert("second_field"sv == std::get<1>(t).name and 87 == std::get<1>(t).value);

100 LOC example - https://godbolt.org/z/sEMPxjGfP

Experimental approach towards releasing C++ (small) libraries with tests being executed upon include/import at compile-time. Traditional way of testing libraries includes continuous integration systems with huge matrix of possible combinations of supported compilers/systems etc. Although, that's very powerful there is no way to verify all possible combinations and users often assume that the library just works as it's already tested without verifying on their environment. With C++20 ability to test the library upon use additional guarantees can be put in place (accordingly to the quality of tests). Tests are executed at compile-time during include/import so there is no run-time overhead and compile-time overhead is minimal. With this approach, it can be basically guaranteed that the tested features are working as expected without any leaks and/or UB if the library compiles upon include/import. The feedback is immediate and constantly verified making the solution reliable and without run-time surprises on the client side.

C++20 allows to `almost` natively use std.ranges for template meta-programming. Idea explored at - https://github.com/boost-ext/mp.

IMHO the best approach is to avoid the problem by applying TDD. Then there is very little need to debug anything. But otherwise, there is https://github.com/mikael-s-persson/templight for compile-time debugging which is pretty cool and having something like `expect(auto... args) static_asert(args...); assert(args...);` may help with being able to debug at run-time and get the coverage (though, the code has has to compile aka pass first).

Thanks! Most likely not yet applicable at Google's scale but smaller project can defo leverage the approach. Personally, I'm writing most of my tests this way and with TDD the red phase is always a compilation fail which is quicker than buiding and running in my experience. But that's for a medium size project. But as always it depends there are trade offs.

I guess so, can't think of an example now but I'm pretty sure there are subtle corner cases (as always) and it depends on the testing, coverage and potential limitations of checking things at compile-time, though, IMHO, the technique is promissing and can help with a lot of use cases but defo not everything.

Hmm, there are obvisouly trade offs (it depends on the compiler how many tests, how are they written, etc.) but for apples to apples comparision the gtest binary would have to be either compiled with sanitizers (that would be probably slower to compile than static_assert tests without sanitizers) or run with valgrind or similar (execution would be much slower, static_asserts tets don't have to be executed, compiles=green).

constexpr has to checked for leaks and UB so as long as there is coverage at compile-time (static_assert + constexpr) I would assume there shouldn't be neither leaks nor UB. But the context is limitted where that can be applied and actually compiles. For example, there is no way to do it with global variables but with limited scope that's possible.

With C++20 almost anything can be used in constexpr context (vector, unique_ptr, virtual, function, etc.) and as long as it's in the scope it can be tested at compile time which guarantees memory safatey, no UB, etc. Additionally, since constexpr can be executed at run-time and code has been tested at compile-time already therefore 'static_assert' is (almost) all you need - https://godbolt.org/z/P4cqboGx6.