How does std::visit handle multiple variants?

Related to, but not the same question as How does std::visit work with std::variant?

Implementing std::visit for a single variant conceptually looks like this (in C++ pseudocode):

template<class F, class... Ts>
void visit(F&& f, variant<Ts...>&& var) {
  using caller_type = void(*)(void*);
  caller_type dispatch[] = {dispatch_visitor(f, (INDEX_SEQUENCE))...};
  dispatch[var.index()](var);
};

Basically, we set up a jump table that calls the correct dispatcher for our visitor.

For multiple variants, it seems to be more complicated, as for this approach you'd need to compute the Cartesian product of all the variants' alternatives and possibly template thousands of functions. Is this how it's done or is there a better way that standard libraries implement it?

Solution

For multiple variants, it seems to be more complicated, as for this approach you'd need to compute the Cartesian product of all the variants' alternatives and possibly template thousands of functions.

There are currently two implementations of multi-variant visitation.

GCC constructs a multi-dimensional function table at compile time according to the number of alternative types of variants, and access the corresponding visit function through multiple indexes at runtime.

// Use a jump table for the general case.
constexpr auto& __vtable = __detail::__variant::__gen_vtable< 
                             _Result_type, _Visitor&&, _Variants&&...>::_S_vtable;
auto __func_ptr = __vtable._M_access(__variants.index()...);
return (*__func_ptr)(std::forward<_Visitor>(__visitor),
                     std::forward<_Variants>(__variants)...);

MSVC uses recursive switch-case to perform multi-variant visitation:

#define _STL_VISIT_STAMP(stamper, n)                                               \
    constexpr size_t _Size = _Variant_total_states<_Remove_cvref_t<_Variants>...>; \
    static_assert(_Size > (n) / 4 && _Size <= (n));                                \
    switch (_Idx) {                                                                \
        stamper(0, _STL_CASE);                                                     \
    default:                                                                       \
        _STL_UNREACHABLE;                                                          \
    }

This switch-case base implementation has better performance when the number of variants is small or the number of alternatives is small, which also makes GCC use this approach for simple cases in its recent patch to reduce the instantiation of function tables.

switch (__v0.index())
{
  _GLIBCXX_VISIT_CASE(0)
  _GLIBCXX_VISIT_CASE(1)
  _GLIBCXX_VISIT_CASE(2)
  _GLIBCXX_VISIT_CASE(3)
  _GLIBCXX_VISIT_CASE(4)
  case variant_npos:
          // ...
}

You can refer to the following two blogs by Michael Park for more implementation details: