C++ Weekly #2: constexpr Map

constexpr Specifier

The constexpr specifier declares that it is possible to evaluate the value of the function or variable at compile time.

constexpr is such a stunning idea first introduced in c++11, which lets the programmer tell the compiler which part of code could be and would like to be evaluated at the compile-time specifically. This, not only clean up the code once more, just like when you using a const specifier, but the compiler also could understand your intended more clearly, hence it could try to optimize the code even better.

Later on, C++14 and C++17 fix some of the language issues, which make it more flexible to use. You can now define the constexpr function with loop, branch predictions, and so on. This is something you should be using in your projects, especially when you start a new project compile with the later C++ standard.

If you are new to constexpr, I highly recommend you checkout constexpr, and const expression for more details.

Compile Time vs Runtime

Here is a simple sum function showing the difference between compile time and runtime.

constexpr int sum_constexpr(int a, int b) {
    return a + b;
}

int sum(int a, int b) {
    return a + b;
}

int main() {
    auto res = sum_constexpr(1, 3);
    auto res2 = sum(1, 3);
    return 0;
}

intel asm syntax, gcc 10.2, compiler explore

sum(int, int):                              // int sum(int a, int b)
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-4], edi
        mov     DWORD PTR [rbp-8], esi
        mov     edx, DWORD PTR [rbp-4]
        mov     eax, DWORD PTR [rbp-8]
        add     eax, edx
        pop     rbp
        ret
main:
        push    rbp
        mov     rbp, rsp
        sub     rsp, 16

        mov     DWORD PTR [rbp-4], 4        // auto res = sum_constexpr(1, 3);

        mov     esi, 3                      // auto res2 = sum(1, 3);
        mov     edi, 1                      // ...
        call    sum(int, int)               // ...
        mov     DWORD PTR [rbp-8], eax      // ...

        mov     eax, 0
        leave
        ret

Not only the entire function of constexpr is not present in the assembly, but it also generates an even shorter code for those function calls. Because the compiler knows the result from auto res = sum_constexpr(1, 3); could be generated at compile-time, it only computes the value from your function and directly assigns it to the register, therefore, all the function stack could also be eliminated.

The compiler could do all kind of crazy things to optimize your code, and with constexpr declared, your release the full potential to let the compiler do that computation at the compile time. It usually takes a longer compile-time, but for the C++ programmer, I assume you would like to trade the runtime performance with the compile speed.

constexpr Map vs std::map

Back to the topic we made in the subtitle, you may get some clue why we could benefit from the constexpr Map.

Until this blog last modified date, there is still no constexpr constructor support for std::map. The good news is, you might be able to use constexpr constructor for the most common container std::vector in C++20 standard.

IMPORTANT: constexpr Map is intended to use for small size lookup, if you do need a very large size dynamic map, please use std::map instead!

Code credit from Jason Turner, C++ Weekly Ep 223 on Youtube, my C++ Weekly blog series is also inspired by his great work! You should definitely checkout his work.

template <typename Key, typename Value, std::size_t Size>
struct Map {
  std::array<std::pair<Key, Value>, Size> data;

  [[nodiscard]] constexpr Value at(const Key &key) const {
    const auto itr =
        std::find_if(begin(data), end(data),
                     [&key](const auto &v) { return v.first == key; });
    if (itr != end(data)) {
      return itr->second;
    } else {
      throw std::range_error("Not Found");
    }
  }

};

using namespace std::literals::string_view_literals;
static constexpr std::array<std::pair<std::string_view, int>, 8> color_values{
    {{"black"sv, 7},
     {"blue"sv, 3},
     {"cyan"sv, 5},
     {"green"sv, 2},
     {"magenta"sv, 6},
     {"red"sv, 1},
     {"white"sv, 8},
     {"yellow"sv, 4}}};

int lookup_value(const std::string_view sv) {
  //static const auto map = std::map<std::string_view, int>{color_values.begin(), color_values.end()};
  static constexpr auto map =
      Map<std::string_view, int, color_values.size()>{{color_values}};

  return map.at(sv);
}

The results turn out to be 9.6 times speedup from this constexpr Map versus the std::map!

gcc 10.1, quickbench

For the small fixed-size constexpr Map, the compiler normally has more flexibility to optimize your code. If you interested why was it, strongly recommend you have a look the video on Jason goes through the assembly GCC generated! I was astonished by how GCC optimizing this piece of code.

I want to emphasize again if you have a very large map size, std::map binary search is the way to go. But for the small size map lookup purpose, which you already have all the data ready at the compile time, you should definitely start using this from now on!