kris-jusiak

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

> 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"

    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"

- 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

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 - 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

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

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>));
    }

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>));
    }

- 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>);

    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...

    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);
    }();

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);