Switch and her Brothers in C++ and beyond

There have been recent instances where I have to write programs to pattern-match something and return something else. This is a well-known pattern, and I thought it would be great to write an article just on this, from the perspectives of syntax, semantics, and usability.

Again as hinted, this article demonstrates the concepts in C++.

Pattern matching can be powerful. If used right, a single logical block of code can perform the distribution of logic at scale.

The Great If-Else

Before we dive into switch statements, let's have a look at the basics. Everyone uses them every single day:

#include <string_view>

enum class Country { Japan = 0, France = 1, Brazil = 2, Egypt = 3 };

template<typename T>
__attribute__((noinline)) T runtime_value(T value) {
    asm volatile("" : "+r"(value) : : "memory");
    return value;
}

std::string_view get_language_for(Country country) {
    if (country == Country::Japan) return runtime_value("Japanese");
    else if (country == Country::France) return runtime_value("French");
    else if (country == Country::Brazil) return runtime_value("Portuguese");
    else if (country == Country::Egypt) return runtime_value("Arabic");
}

One can explain more on what a compiler can optimise at compile time, or on what a CPU will do when executing the code; however, in this post I want to focus on the semantic comparison of similar logics.

The Switch

The classic switch statement has been here for a very long time¹. An example could be:

std::string_view get_language_for(Country country) {
    switch (country) {
        case Country::Japan:
            return runtime_value("Japanese");
        case Country::France:
            return runtime_value("French");
        case Country::Brazil:
            return runtime_value("Portuguese");
        case Country::Egypt:
            return runtime_value("Arabic");
    }
    return "Unknown"; // Should never reach here
}

There are already a few caveats. In the above case, guess what, GCC would generate a binary-search-based comparison!

get_language_for(Country):
        sub     rsp, 24
        cmp     edi, 2      ; <--- what...? where's the jump table?
        je      .L4
        jg      .L5
        test    edi, edi
        je      .L6
        cmp     edi, 1
        jne     .L8
        mov     edi, OFFSET FLAT:.LC1
        jmp     .L12

This is due to the internal heuristics and cost model used in modern compilers. In both GCC and LLVM², heuristics are applied to this code when compiling to determine whether a jump table should be generated or not. I would rather not expand on this topic, and interested readers should always inspect their assembly code for their specific use cases.

Thinking about Types

Let's think about types. Of course, we can treat types differently.

1. Inheritance and Virtual Functions

#include <memory>
#include <string>

class Country {
public:
    virtual ~Country() = default;
    virtual std::string language() const = 0;
};

class Japan : public Country {
public:
    Japan() = default;
    std::string language() const override { return "Japanese"; }
};

class France : public Country {
public:
    France() = default;
    std::string language() const override { return "French"; }
};

// and so on...

std::unique_ptr<Country> country = std::make_unique<Japan>();
std::string lang = country->language();

There are runtime overheads from vtable lookups and heap allocation. All the dispatching happens at runtime via vtables.

2. Type Erasure with void* and unions

This is a particularly old way of doing switching:

enum CountryType { JAPAN, FRANCE, BRAZIL, EGYPT };

struct Country {
    CountryType type;
    union {
        struct { char const* language; } japan;
        struct { char const* language; } france;
        struct { char const* language; } brazil;
        struct { char const* language; } egypt;
    };
};

And it is particularly hard to get to the right version of code that is easy to write and maintain (perhaps because of union!). This is a last resort in dealing with switching and dispatching. We should avoid using this unless there is no other better alternative.

std::variant and std::visit

C++17 introduced std::variant, a type-safe union, and std::visit, which enables pattern matching on variants:

#include <variant>
#include <string>

struct Japan { std::string_view language = "Japanese"; };
struct France { std::string_view language = "French"; };
struct Brazil { std::string_view language = "Portuguese"; };
struct Egypt { std::string_view language = "Arabic"; };

using Country = std::variant<Japan, France, Brazil, Egypt>;

std::string_view get_language_for(Country const& country) {
    return std::visit([](auto&& arg) -> std::string_view {
        using T = std::decay_t<decltype(arg)>;
        if constexpr (std::is_same_v<T, Japan>) {
            return "Japanese";
        } else if constexpr (std::is_same_v<T, France>) {
            return "French";
        } else if constexpr (std::is_same_v<T, Brazil>) {
            return "Portuguese";
        } else if constexpr (std::is_same_v<T, Egypt>) {
            return "Arabic";
        }
    }, country);
}

The memory layout of a std::variant is as follows: Size of the largest alternative + (Padding) + Type index³. For the above, GCC generates surprisingly short, optimised code (with -O3):

get_language_for(std::variant<Japan, France, Brazil, Egypt> const&):
        movzx   eax, BYTE PTR [rdi+16] ; <--- Load the type index
        cmp     al, 2                  ; <--- On the type index!
        je      .L3
        ja      .L4
        test    al, al
        je      .L5
        mov     eax, OFFSET FLAT:.LC0
        mov     edx, 6
        xchg    rdx, rax
        ret

With a generic lambda (from C++14), the code becomes extremely concise:

using Country = std::variant<Japan, France, Brazil, Egypt>;

auto get_language_for = [](Country const& country) {
    return std::visit([](auto const& c) { return c.language; }, country);
};

The Overload

The previous generic lambda approach has a slight problem - it actually requires ADL if we choose not to write generic lambda, and it requires same structure across all alternatives. Overload provides another self-contained solution which allows non-uniform structures across the alternatives:

template<class... Ts> struct overload : Ts... { using Ts::operator()...; };
template<class... Ts> overload(Ts...) -> overload<Ts...>;

std::string_view get_language_for(Country const& country) {
    return std::visit(overload{
        [](Japan const& j) { return j.language; },
        [](France const& f) { return f.language; },
        [](Brazil const& b) { return b.language; },
        [](Egypt const& e) { return e.language; }
    }, country);
}

In C++20, this becomes closer to what we think pattern matching should be, with abbreviated function templates:

std::string_view get_language_for(Country const& country) {
    return std::visit(overload{
        [](Japan const&) { return std::string_view{"Japanese"}; },
        [](France const&) { return std::string_view{"French"}; },
        [](auto const& c) { return c.language; }  // Like, "otherwise"
    }, country);
}

What's more with std::variant

1. Zero to Multiple Variants with (std::monostate)

To represent an empty type (note here, std::monostate is the first alternative. This enables default-constructibility of the variant type.):

using Country = std::variant<std::monostate, Japan, France, Brazil, Egypt>; // Can be "empty"

std::string_view get_language_for(Country const& country) {
    return std::visit(overload{
        [](std::monostate const&) { return std::string_view{"Unknown"}; },
        [](Japan const&) { return std::string_view{"Japanese"}; },
        [](France const&) { return std::string_view{"French"}; },
        [](Brazil const&) { return std::string_view{"Portuguese"}; },
        [](Egypt const&) { return std::string_view{"Arabic"}; }
    }, country);
}

Future: C++26 Pattern Matching

The proposal P2688 - Pattern Matching: match Expression is targeting C++26:

// Future C++26 syntax (proposed)
using Country = std::variant<Japan, France, Brazil, Egypt>;

std::string_view get_language_for(Country const& country) {
    return inspect(country) {
        Japan{.language = lang} => lang;
        France{.language = lang} => lang;
        Brazil{.language = lang} => lang;
        Egypt{.language = lang} => lang;
    };
}

We can see it will combine both type-based dispatch and destructuring well, and we should look forward to this going into the standard.

Conclusion

Pattern matching in C++ has evolved significantly:

• C++98: Switch statements, virtual functions
• C++11: Variadic templates, type traits
• C++17: std::variant, std::visit, if constexpr
• C++20: Abbreviated function templates, and Concepts
• C++26: Native pattern matching (proposed)

The key is choosing the right tool for the job. For anything simple enough, we can use switch. For sum types, we can use std::variant. Understanding memory layouts is important, but if your compiler can optimise most of the code out, let's trust it!

References

• P2688: Pattern Matching
• cppreference: std::variant
• cppreference: std::visit
• Bartek's coding blog: Everything You Need to Know About std::variant