Pydong

pydongery and other shenanigans

• HOME
• STANDARDS
• BETTER C++
• CATEGORIES
• TAGS
• ARCHIVES
• ABOUT

Home Variadic Switch Post Cancel

Variadic Switch

Posted May 13, 2025 Updated May 13, 2025 By _Che _ 21 min read

几年前，我在 Reddit 上发现了一个有趣的问题。 基本上，作者想知道为什么没有办法将参数包扩展为一系列 case 标签，然后跟一个语句。 它用以下虚构的语法来说明：

1
2
3
4
5
6
7
8
9
10
11

```
| ```
template <class Visitor, class Variant, std::size_t ... Is>
auto visit_impl(Visitor visitor, Variant && variant, std::index_sequence<Is...>) {
  auto i = variant.index();
  switch (i) { (case Is: return visitor(get<Is>(variant));)... }
}
template <class Visitor, class Variant>
auto visit(Visitor visitor, Variant&& variant) {
  return visit_impl(visitor, variant, 
           std::make_index_sequence<std::variant_size_v<Variant>>{});
}

```
  
---|---  
`
这提出了一个有趣的挑战——我们如何才能尽可能接近地通用地生成一些东西，这些东西可以优化到与手写 `switch` 一样好的汇编代码？
也许更有趣的是：C++26 的特性能对此有所帮助吗？

## 跳转表

一些编程语言提供了一种直接或间接的方式来生成所谓的跳转表或 [branch table](https://pydong.org/posts/variadic-switch/<https:/en.wikipedia.org/wiki/Branch_table>)。 虽然 C++ 的 `switch` 语句并不要求编译器将其转换为跳转表，但如果 `case` 的数量足够多且启用了优化，大多数编译器都会这样做。

> 为了简单起见，我们暂时不关心通用的 visitor，而是始终调用一个未定义的模板函数 `h`：
> ````
1
2

```
| ```
template <int>
int h();

```
  
> ---|---  
> `
> 由于它没有被定义，编译器不可能内联对它的调用。 这在我们查看生成的汇编代码（和优化过程）以查看编译器是否能够理解我们的代码时，应该会派上用场。

考虑一个简单的 switch，例如：

1 2 3 4 5 6 7 8 9 10

| ```
int mersenne(unsigned index){
 switch (index) {
  case 0: return h<2>();
  case 1: return h<3>();
  case 2: return h<5>();
  case 3: return h<7>();
  case 4: return h<13>();
  default: return -1;
 }
}

---|---
` 启用优化后，GCC 将其转换为以下 x86 汇编代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

```
| ```
mersenne(unsigned int):
    cmp   edi, 4
    ja   .L2
    mov   edi, edi
    jmp   [QWORD PTR .L4[0+rdi*8]]
.L4:
    .quad  .L8
    .quad  .L7
    .quad  .L6
    .quad  .L5
    .quad  .L3
.L5:
    jmp   int h<7>()
.L3:
    jmp   int h<13>()
.L8:
    jmp   int h<2>()
.L7:
    jmp   int h<3>()
.L6:
    jmp   int h<5>()
.L2:
    mov   eax, -1
    ret

```
  
---|---  
`
虽然它无助于解决所提出的问题，但我们可以使用 GCC 的 [computed goto](https://pydong.org/posts/variadic-switch/<https:/gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html>) 扩展来近似地反向推导生成的汇编代码。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

| ```
template <auto> int h();
int mersenne(unsigned index){
 constexpr static void* jtable[] = 
 {          //.L4:
  &&CASE_0,     //  .quad .L8
  &&CASE_1,     //  .quad .L7
  &&CASE_2,     //  .quad .L6
  &&CASE_3,     //  .quad .L5
  &&CASE_4,     //  .quad .L3
 };
 if (index > 4)    // cmp edi, 4
  goto DEFAULT;   // ja  .L2
 
 goto* jtable[index]; // jmp [QWORD PTR .L4[0+rdi*8]]
CASE_0:        //.L8:
 return h<2>();    //  jmp int h<2>()
CASE_1:        //.L7:
 return h<3>();    //  jmp int h<3>()
CASE_2:        //.L6:
 return h<5>();    //  jmp int h<5>()
CASE_3:        //.L5:
 return h<7>();    //  jmp int h<7>()
CASE_4:        //.L3:
 return h<13>();   //  jmp int h<13>()
DEFAULT:        //.L2:
 return -1;      //  mov eax, -1
            //  ret
}

---|---
` 在 Compiler Explorer 上运行

这使我们得出了第一个朴素的实现策略。

分发表

为了将其转换为有效的 C++ 代码，我们需要创建一个函数指针数组，而不是标签地址。 方便的是，获取我们希望处理的每个 h 特化版本的指针非常简单。 这让我们得到了所谓的 dispatch table。 我们可以将之前的示例重写如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

```
| ```
int mersenne(unsigned index){
 using F = int();
 constexpr static F* table[] = { 
  &h<2>,
  &h<3>,
  &h<5>,
  &h<7>,
  &h<13>,
  &h<17>
 }; 
 if (index > 4) {
  // boundary check
  return -1;
 }
 return table[index]();
}

```
  
---|---  
`
更通用地，我们可以展开参数包来生成表。

1 2 3 4 5 6 7 8 9 10 11

| ```
template <int... Is>
int visit(unsigned index) {
 using F = int();
 constexpr static F* table[] = {&h<Is>...}; 
 if (index >= (sizeof table / sizeof* table)) {
  // boundary check
  return -1;
 }
 return table[index]();
}

---|---
` 在 Compiler Explorer 上运行

请注意，虽然这仍然为此简单的示例生成良好的汇编代码，但它会迅速退化并发出一个 call 而不是 jump。

通用的 visit

但是，这已经可以用于实现单变体的 visit。 由于 visit 是一个很好的使用示例，我们将查看每个策略的简化实现。

在所有策略的 visit 示例实现中，为了清楚起见，使用了 get。 但是，在链接的 CE 示例中，您将看到 __unchecked_get，它（对于 libc++）本质上与 get 相同，只是没有边界检查。 这主要是为了使发出的汇编代码更易于阅读。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

```
| ```
template <typename F, typename V>
decltype(auto) visit(F&& visitor, V&& variant) {
 constexpr static auto max_index = std::variant_size_v<std::remove_cvref_t<V>>;
 constexpr static auto table = []<std::size_t... Idx>(std::index_sequence<Idx...>) {
  return std::array{+[](F&& visitor, V&& variant) {
   return std::invoke(std::forward<F>(visitor), 
             get<Idx>(std::forward<V>(variant)));
  }...};
 }(std::make_index_sequence<max_index>());
 const auto index = variant.index();
 if (index >= table.size()) {
  // boundary check
  std::unreachable();
 }
 return table[index](std::forward<F>(visitor), std::forward<V>(variant));
}

```
  
---|---  
`
[在 Compiler Explorer 上运行](https://pydong.org/posts/variadic-switch/<https:/godbolt.org/z/77TWhc6ce>)

## 宏

当然，最接近 `switch` 的东西是…… `switch`。 可靠的旧宏可能不会激发快乐，但通过巧妙地将它们与 C++ 特性结合起来，我们可以尝试其他方法：生成大量 `case`，然后丢弃所有索引超过我们要处理的 `case` 数量的那些。
为此，我们首先需要某种方法来发出索引递增的 `case`。 像下面这样的一组宏可以提供帮助：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

| ```
#define STAMP4(Offset, Fnc) \
  Fnc(Offset)       \
  Fnc((Offset) + 1)    \
  Fnc((Offset) + 2)    \
  Fnc((Offset) + 3)

#define STAMP16(Offset, Fnc) \
  STAMP4(Offset, Fnc)    \
  STAMP4((Offset) + 4, Fnc) \
  STAMP4((Offset) + 8, Fnc) \
  STAMP4((Offset) + 12, Fnc)

#define STAMP64(Offset, Fnc)  \
  STAMP16(Offset, Fnc)    \
  STAMP16((Offset) + 16, Fnc) \
  STAMP16((Offset) + 32, Fnc) \
  STAMP16((Offset) + 48, Fnc)

#define STAMP256(Offset, Fnc)  \
  STAMP64(Offset, Fnc)     \
  STAMP64((Offset) + 64, Fnc) \
  STAMP64((Offset) + 128, Fnc) \
  STAMP64((Offset) + 192, Fnc)

#define STAMP(Count) STAMP##Count

---|---
有了STAMP宏，我们现在可以定义一个宏来生成一个case`。

1
2
3
4
5
6
7

```
| ```
#define GENERATE_CASE(Idx)                       \
 case (Idx):                             \
  if constexpr ((Idx) < max_index) {                 \
   return std::invoke(std::forward<F>(visitor),           \
             get<Idx>(std::forward<Vs>(variant)));     \
  }                                 \
  std::unreachable();

```
  
---|---  
`
为了尽可能减少需要丢弃的分支数量，我们可以生成多个类模板的显式特化版本，每个版本处理最多特定大小限制的 variant。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

| ```
#define GENERATE_STRATEGY(Idx, Stamper)                 \
 template <>                              \
 struct VisitStrategy<Idx> {                      \
  template <typename F, typename V>                  \
  static constexpr decltype(auto) visit(F&& visitor, V&& variant) {  \
   switch (variant.index()) {                    \
    Stamper(0, GENERATE_CASE);                   \
    default:                            \
     std::unreachable();                      \
   }                                 \
  }                                  \
 }

GENERATE_STRATEGY(1, STAMP(4));  // 4^1 potential states
GENERATE_STRATEGY(2, STAMP(16));  // 4^2 potential states
GENERATE_STRATEGY(3, STAMP(64));  // 4^3 potential states
GENERATE_STRATEGY(4, STAMP(256)); // 4^4 potential states

---|---
此时，我们只需要选择VisitStrategy` 的适当特化版本。 请注意，这只能处理最多 256 个备选项的 variant——如果需要支持更多，则必须回退到另一种策略（即，分发表）。

1
2
3
4
5
6
7
8
9
10
11

```
| ```
template <typename F, typename V>
constexpr decltype(auto) visit(F&& visitor, V&& variant) {
 constexpr static auto max_index = std::variant_size_v<std::remove_cvref_t<V>>;
 using visit_helper       = VisitStrategy<max_index <= 4   ? 1
                         : max_index <= 16 ? 2
                         : max_index <= 64 ? 3
                                   : 4;
 return visit_helper::template visit(std::forward<F>(visitor),
                   std::forward<Vs>(variant));
}

```
  
---|---  
`

## 递归 switch

这很好，但是您已经被承诺了 C++ 元编程魔法，而不是无聊的旧宏。 让我们探索另一种方法。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

| ```
template <int Offset, int Limit>
[[clang::always_inline]] inline int visit(unsigned index) {
 switch (index - Offset) {
  case 0:
   if constexpr (Offset < Limit) {
    return h<Offset>();
   }
  default:
   if constexpr (Offset + 1 < Limit) {
    return visit<Offset + 1, Limit>(index);
   }
 }
 std::unreachable();
}

---|---
虽然inline关键字更有趣的用途是将不同翻译单元中的函数或变量的多个定义折叠成具有一个地址的单个实体 ([dcl.inline/6](https://pydong.org/posts/variadic-switch/<https:/standards.pydong.org/c++/dcl.inline#6>))，从而绕过原本会违反 ODR 的情况，但某些编译器实际上将inline` 视为可忽略的优化提示 (dcl.inline/2)。 例如，Clang 会稍微提高内联阈值。

不幸的是，无法以可移植的方式强制内联。 但是，大多数编译器都有专门用于此目的的特殊属性。

编译器| 属性 ---|--- GCC| [[gnu::always_inline]] Clang| [[clang::always_inline]] 或 [[gnu::always_inline]] MSVC| [[msvc::forceinline]]

我们可以使用 Compiler Explorer’s clang Opt Pipeline Viewer 功能来验证对 visit 的所有调用是否都被内联。 在 SimplifyCFG 优化过程之后，链接的比较现在被组合成一个 switch。 如果我们不强制内联，则可能已经在较早的 InlinerPass 过程中生成了 switch，并使计算出的内联成本超过阈值，从而导致多个跳转表。

1
2
3
4
5
6
7
8
9
10

```
| ```
; int visit<0ul, 3ul>(unsigned long)
define weak_odr dso_local noundef i32 @_Z5visitILm0ELm3EEim(i64 noundef %index) local_unnamed_addr #0 comdat {
entry:
 switch i64 %index, label %sw.epilog.i [
  i64 0, label %sw.bb
  i64 1, label %sw.bb.i
  i64 2, label %_Z5visitILm2ELm3EEim.exit
 ]
 ; ...
}

```
  
---|---  
`
但是，如果我们查看生成的汇编代码，我们会注意到缺少跳转表：

1 2 3 4 5 6

| ```
int visit<0ul, 3ul>(unsigned long):
    cmp   rdi, 2
    je   int h<2ul>()
    cmp   rdi, 1
    jne   int h<0ul>()
    jmp   int h<1ul>()

---|---
事实证明，clang 认为对于 x86 作为目标汇编器来说，为如此少的分支生成跳转表更便宜。 这可能会发生，但至少对于 x86，我们会得到一个具有 4 个或更多case` 的跳转表。 可以通过查看 X86 DAG->DAG 指令选择过程来验证这一点。

和以前一样，在 SimplifyCFG 过程之后，它会将所有内联比较组合成一个 switch。

1
2
3
4
5
6
7
8
9
10
11

```
| ```
; int visit<0ul, 4ul>(unsigned long)
define weak_odr dso_local noundef i32 @_Z5visitILm0ELm4EEim(i64 noundef %index) local_unnamed_addr #0 comdat {
 entry:
  switch i64 %index, label %sw.epilog.i [
   i64 0, label %sw.bb
   i64 1, label %sw.bb.i
   i64 2, label %sw.bb.i7
   i64 3, label %_Z5visitILm0ELm4EEim.exit
  ]
 ; ...
}

```
  
---|---  
`
这次我们可以在 X86 DAG->DAG 指令选择过程的结果中看到这个可爱的注释：

1 2 3 4

| ```
# Machine code for function 
# int visit<0ul, 4ul>(unsigned long): IsSSA, TracksLiveness
Jump Tables:
%jump-table.0: %bb.1 %bb.2 %bb.3 %bb.5

---|---
` 太好了，一个跳转表！ 让我们验证生成的汇编代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

```
| ```
int visit<0ul, 4ul>(unsigned long): 
    lea   rax, [rip + .LJTI0_0]
    movsxd rcx, dword ptr [rax + 4*rdi]
    add   rcx, rax
    jmp   rcx
.LBB0_1:              // label %sw.bb
    jmp   int handler<0ul>() // TAILCALL
.LBB0_3:              // label %sw.bb.i7
    jmp   int handler<2ul>() // TAILCALL
.LBB0_4:              // label %_Z5visitILm0ELm4EEim.exit
    jmp   int handler<3ul>() // TAILCALL
.LBB0_2:              // label %sw.bb.i
    jmp   int handler<1ul>() // TAILCALL
.LJTI0_0:
    .long  .LBB0_1-.LJTI0_0
    .long  .LBB0_2-.LJTI0_0
    .long  .LBB0_3-.LJTI0_0
    .long  .LBB0_4-.LJTI0_0

```
  
---|---  
`
`.LJTI0_0` 它就在那里。 真棒。

好的，那么这种方法是否足够？ 遗憾的是，并非如此。 目前，只有 clang 能够看穿这一点并生成一个大的跳转表。

## 折叠技巧

我在本博客文章的引言中提到的 [Reddit](https://www.reddit.com/) 线程中的一位评论者提出了以下相当神秘的代码：

1 2 3 4 5 6

| ```
template <int... Is>
int visit(unsigned index) {
 int retval;
 std::initializer_list<int>({(index == Is ? (retval = h<Is>()), 0 : 0)...});
 return retval;
}

---|---
` Clang 能够看穿这一点，但遗憾的是 GCC 和 MSVC 不能 (在 Compiler Explorer 上运行)。 为了解释为什么会这样，我们需要深入了解 GCC 在底层做了什么。

首先，让我们将初始化列表部分重写为对 , 的折叠。 Clang 仍然可以看穿这一点，而 GCC 仍然不能。

1
2
3
4
5
6

```
| ```
template <int... Is>
int visit(unsigned index) {
 int retval;
 ((index == Is ? (retval = h<Is>()),0 : 0), ...);
 return retval;
}

```
  
---|---  
`
假设 `Is` 是索引序列 [0, 5]，这会扩展为以下代码 ([cppinsights](https://pydong.org/posts/variadic-switch/<https:/cppinsights.io/s/4207098f>)):

1 2 3 4 5 6 7 8 9 10 11

| ```
template<>
int visit<0, 1, 2, 3, 4, 5>(unsigned index) {
 int retval;
 (index == 0 ? (retval = h<0>()) , 0 : 0),
  ((index == 1 ? (retval = h<1>()) , 0 : 0), 
   ((index == 2 ? (retval = h<2>()) , 0 : 0) , 
    ((index == 3 ? (retval = h<3>()) , 0 : 0) , 
     ((index == 4 ? (retval = h<4>()) , 0 : 0) , 
      (index == 5 ? (retval = h<5>()) , 0 : 0)))));
 return static_cast<int &&>(retval);
}

---|---
` 我们可以将其重写为更易于阅读的形式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

```
| ```
int visit(unsigned index) {
 int retval;
 if (index == 0) { // case 0
  retval = h<0>();
 }
 if (index == 1) { // case 1
  retval = h<1>();
 }
 if (index == 2) { // case 2
  retval = h<2>();
 }
 if (index == 3) { // case 3
  retval = h<3>();
 }
 if (index == 4) { // case 4
  retval = h<4>();
 }
 if (index == 5) { // case 5
  retval = h<5>();
 }
 return retval;
}

```
  
---|---  
`
让我们看看在 GCC 的 `iftoswitch` 优化过程之前的两个“case”。 为了简洁起见，以下代码片段已删除了一些过程详细信息，并且标识符已更改为与代码片段匹配。 此外，这里隐藏着一个小小的谎言——它实际上还没有直接写入 `retval`，现在它将使用一个临时的变量。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

| ```
//  basic block 2, loop depth 0, maybe hot
//  pred:    ENTRY (FALLTHRU,EXECUTABLE)
 if (index == 0)
  goto <bb 3>;
 else
  goto <bb 4>;
//  succ:    3 (TRUE_VALUE,EXECUTABLE)
//        4 (FALSE_VALUE,EXECUTABLE)
//  basic block 3, loop depth 0, maybe hot
//  pred:    2 (TRUE_VALUE,EXECUTABLE)
 retval = h<0>();
//  succ:    4 (FALLTHRU,EXECUTABLE)
//  basic block 4, loop depth 0, maybe hot
//  pred:    2 (FALSE_VALUE,EXECUTABLE)
//        3 (FALLTHRU,EXECUTABLE)
 if (index == 1)
  goto <bb 5>;
 else
  goto <bb 6>;
//  succ:    5 (TRUE_VALUE,EXECUTABLE)
//        6 (FALSE_VALUE,EXECUTABLE)
//  basic block 5, loop depth 0, maybe hot
//  pred:    4 (TRUE_VALUE,EXECUTABLE)
 retval = h<1>();

---|---
因此，不幸的是，GCC 没有推断出此时只会采用“case”分支中的一个，因此决定不将其转换为switch`。 让我们帮助 GCC，将其转换为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

```
| ```
int visit(unsigned index) {
 int retval;
 if (index == 0) {   // case 0
  retval = h<0>();
 }
 else if (index == 1) { // case 1
  retval = h<1>();
 }
 else if (index == 2) { // case 2
  retval = h<2>();
 }
 else if (index == 3) { // case 3
  retval = h<3>();
 }
 else if (index == 4) { // case 4
  retval = h<4>();
 }
 else if (index == 5) { // case 5
  retval = h<5>();
 }
 return retval;
}

```
  
---|---  
`
相反。 我们可以 [手动确认](https://pydong.org/posts/variadic-switch/<https:/gcc.godbolt.org/z/G3YhP4Pq8>) 这可行。 太好了——那么我们如何以通用的方式做到这一点呢？

### 短路折叠

我们之前已经有了一个索引包，所以让我们再次使用折叠表达式。 我们正在寻找的是一种能够 [short circuiting](https://pydong.org/posts/variadic-switch/<https:/en.wikipedia.org/wiki/Short-circuit_evaluation>) 的运算符。
C++ 有两个这样的运算符——逻辑 `and` ([expr.log.and/1](https://pydong.org/posts/variadic-switch/<https:/standards.pydong.org/c++/expr.log.and#1>)) 和逻辑 `or` ([expr.log.or/1](https://pydong.org/posts/variadic-switch/<https:/standards.pydong.org/c++/expr.log.or#1>))。 因此，让我们改为折叠 `or`。

1 2 3 4 5 6

| ```
template <int... Is>
int visit(unsigned index) {
 int value;
 (void)((index == Is ? value = h<Is>(), true : false) || ...);
 return value;
}

---|---
` 根据 cppinsights，这将转换为：

1
2
3
4
5
6
7
8
9
10
11
12
13

```
| ```
template<>
int visit<0, 1, 2, 3, 4, 5>(unsigned index)
{
 int value;
 static_cast<void>(
  (index == 0 ? (value = h<0>()) , true : false) || 
   ((index == 1 ? (value = h<1>()) , true : false) || 
    ((index == 2 ? (value = h<2>()) , true : false) || 
     ((index == 3 ? (value = h<3>()) , true : false) || 
      ((index == 4 ? (value = h<4>()) , true : false) || 
       (index == 5 ? (value = h<5>()) , true : false))))));
 return static_cast<int &&>(value);
}

```
  
---|---  
`
正如 [Compiler Explorer](https://pydong.org/posts/variadic-switch/<https:/gcc.godbolt.org/z/981vYoE9b>) 可以为我们确认的那样：这将说服 GCC 生成一个跳转表。 太棒了。

### 通用的 visit

不幸的是，使此过程通用化变得有点困难。
由于我们需要准备一个 visitor 返回类型的变量，因此我们需要找到 visitor 的返回类型。 幸运的是，所有备选项的 visitor 都需要具有相同的返回类型，因此我们可以简单地检查第一个备选项。

1 2 3

| ```
template <typename F, typename V>
using visit_result_t = std::invoke_result_t<F, std::variant_alternative_t<0, 
                         std::remove_reference_t<V>>>;

---|---
有了这个，我们就可以设置visit`。

1
2
3
4
5
6
7
8

```
| ```
template<typename F, typename V>
constexpr auto visit(F&& visitor, V&& variant){
 using return_type = visit_result_t<F, V>;
 constexpr auto size = std::variant_size_v<std::remove_cvref_t<V>>;
 return visit_impl<return_type>(std::make_index_sequence<size>(), 
                 std::forward<F>(visitor), 
                 std::forward<V>(variant));
}

```
  
---|---  
`

#### 返回 `void` 的 Visitor

由于我们不能有 `void` 类型的变量，因此我们需要为返回 `void` 的 visitor 进行特殊处理。 这很容易。

1 2 3 4 5 6 7 8 9 10 11 12 13

| ```
template <typename R, typename F, typename V, std::size_t... Idx>
 requires (std::same_as<R, void>)
constexpr void visit_impl(std::