Faster ►► C++

Meta-Programming

C++UG Dresden 2020

Meta Programming

What is it?

Generic Types

using IntVec = std::vector<int>;

using IntAndFloat = std::tuple<int, float>;

using IntOrFloat = std::variant<int, float>;

Generic Algorithms

template<class It, class Value>
auto find(It b, It e, const Value&) -> It;

auto vec = IntVec{1, 2, 3};
auto it = find(vec.begin(), vec.end(), 2);

Motivations

Fast to write
Fast to understand
Fast to run
Fast to compile

Fast to compile

Measure!

Time-Trace

clang -ftime-trace

Clang >=9
Visualized in Chrome

AST-Print

clang -Xclang -ast-print -fsyntax-only

Code seen by Compiler
All template instantiations

Metashell

http://metashell.org/

Clang based interactive shell

Metabench

http://metaben.ch

started by Louis Dionne for Hana
GCC, Clang, MSVC
requires CMake + Ruby

Tools

Time-Trace
AST-Print
Metashell
Metabench

Dig Deeper

Compare two types

STL usage

static_assert(std::is_same<int, int>::value);
static_assert(!std::is_same_v<int, float>);

template<class, class>
struct is_same : false_type {};

template<class T>
struct is_same<T, T> : true_type {};

template<class A, class B> constexpr
  auto is_same_v = is_same<A, B>::value;

Issues

Template struct instantiations
For all pairs of types

1. Idea

templated constexpr variable
with template specialisation

template<class, class> constexpr
  auto is_same = false;

template<class T> constexpr
  auto is_same<T, T> = true;

Jorg Brown (CppCon 2019)

“Reducing Template Compilation Overhead, Using C++11, 14, 17, and 20.”

https://www.youtube.com/watch?v=TyiiNVA1syk

Wrapper (Slide 44/61)

template<class T>
struct Wrapper {
  static constexpr
    bool IsSame(Wrapper<T>*) { return true; }
  static constexpr
    bool IsSame(void*) { return false; }
};
static_assert(
  Wrapper<int>::IsSame((Wrapper<int>*)(nullptr)));

Wrapper with Base (Slide 46/61)

struct WrapperBase {
  static constexpr bool IsSame(void*) { return false; }
};
template<class T>
struct Wrapper : WrapperBase {
  static constexpr
    bool IsSame(Wrapper<T>*) { return true; }
  using WrapperBase::IsSame;
};

template<class A, class B>
using is_same = std::integral_constant<bool,
    Wrapper<A>::IsSame((Wrapper<B>*)(nullptr))>;

More Ideas?

Just Pointer

template<class T> using PtrTo = T*;

template<class T> constexpr
  auto is_same(T*, T*) { return true; }
constexpr
  auto is_same(...) { return false; }

static_assert(is_same(PtrTo<int>{}, PtrTo<int>{}));

Pointer to Type Pointers

template<class T> struct Type;
template<class T> constexpr
  auto type = (Type<T>*)(nullptr);

constexpr bool same(const void* a, const void* b) {
  return a == b;
}

static_assert(same(&type<int>, &type<int>));

Which strategy is best?

STL: struct is_same<T, T>
Variable: auto is_same_v<T, T>
Wrapper: Wrapper<T>::IsSame(Wrapper<T>*)
WrapperBase
Pointer: is_same(T*, T*)
Type Pointer: same(&type<T>, &type<T>)

Benchmarks

Efforts for Metabench

Write cpp.erb
CMake metabench_add_dataset()
CMake metabench_add_chart()
Run with CMake

Qbs module cpp_bench

New

Depends { name: "cpp_bench" }
configure cpp_bench.inputNumber: []
add cpp-file
build only changed files

Results

Same Clang-9 Compile Time

Same Clang-9 Ram Usage

Same Clang-9 AST line count

Same VS2019 Compile Time

Conclusion

Never underestimate STL
crazy ideas might help

Conditional Type

using X = conditional_t<true, int, float>;
static_assert(std::is_same_v<X, int>);

using Y = conditional_t<false, int, float>;
static_assert(std::is_same_v<Y, float>);

template<bool Cond, class Then, class Else>
using conditional_t =
    typename Conditional<Cond, Then, Else>::type;

template<bool Cond, class Then, class Else>
struct Conditional {
    using type = Then;
};
template<class Then, class Else>
struct Conditional<false, Then, Else> {
    using type = Else;
};

template<bool Cond> struct Conditional;

template<> struct Conditional<true> {
    template<class Then, class>
    using type = Then;
};

template<> struct Conditional<false> {
    template<class, class Else>
    using type = Else;
};

Conditional Benchmark Results

Conditional Clang-9 Compile Time

Conditional VS2019 Compile Time

Conclusion

benchmark all the things!
compilers change over time

Containers

Vector Contenders

STL: std::vector<T, Allocator>
ETL: etl::vector<T, Size>
Folly: folly::fbvector<T, Allocator>
EASTL: eastl::vector<T, Allocator>
Co-Cpp19: array19::DynamicArrayOf<T>

Vector Benchmark Results

Vector Clang-9 Compile Time

Vector VS2019 Compile Time

Map Contenders

STL: std::map<K, V, Compare, Allocator>
ETL: etl::flat_map<K, V, Size, Compare>
Folly: folly::sorted_vector_map<K, V, C, A, G, Cont>
EASTL: eastl::vector_map<K, V, Comp, Alloc, Cont>

Map Clang-9 Compile Time

Map VS2019 Compile Time

Conclusion

complex containers take time
simplified containers compile faster

Tuple

Tuple Contenders

STL: std::tuple<T…>
EASTL: eastl::tuple<T…>
Hana: boost::hana::tuple<T…>
Basicpp: tuple17::Tuple<T…>
Co-Cpp19: tuple19::Tuple<T…>

Tuple Clang-9 Compile Time

Tuple VS2019 Compile Time

Tuple Visit Clang-9 Compile Time

Tuple Visit VS2019 Compile Time

Conclusion

std::tuple kinda slow
Features might be expensive!
Opinionated implementation much faster

Variant

Variant Contenders

STL: std::variant<T…>
EASTL: eastl::variant<T…>
Mapbox: mapbox::util::variant<T…>
MPark: mpark::variant<T…>
Basicpp: variant17::Variant<T…>
Co-Cpp19: variant19::Variant<T…>

Variant Clang-9 Compile Time

Variant VS2019 Compile Time

Variant Visit Clang-9 Compile Time

Variant Visit VS2019 Compile Time

Summary

benchmark meta programming
compile time is not doomed
look for the simplest, sufficient implementation

Andreas Reischuck
@arBmind

Work with us…

Give a Talk
⇒ get a Dresden tour

Rebuild language project

Collaborate

Compile Benchmark your library!

co_await question_ready()