128臂模式调度问题以及我们如何从 11ns 降至 1.1ns

Source: Dev.to

问题

在大量字面值上进行模式匹配在代码中看起来很简洁，但在运行时会遇到瓶颈。每次调用 on() 都会为每个分支构造 case 对象。

对于 128 条分支来说，每次匹配调用会构造 128 个对象。每次约 11 ns 的开销，对于一次性使用还算可以。但在热点循环中，这简直是灾难。

// Clean syntax, 128 case objects constructed per call
return match(x) | on(
    lit(0) >> handle_0,
    lit(1) >> handle_1,
    // … 126 more arms
    _   >> default_handler
);

这些分支是编译期常量，值 不会 改变。但库必须每次都构造它们，因为 on() 调用把它们作为函数参数传入，而 C++ 在调用点就会求值，任何优化阶段都无法介入。

这并不是库设计的 bug，而是管道语法 match(x) | on(...) 的结构性开销。该语法提供了可读且可组合的匹配方式。代价在于 case 列表成为了运行时对象。

或者说，它曾经是这样，直到我们找到一种方法让它不再如此。

第一次尝试：使用 is_constant_evaluated() 的静态缓存

思路很简单。如果 match 表达式出现在 constexpr 上下文中，编译器已经知道主题值和所有 case 值。我们可以在编译期展开整个 match，完全绕过运行时机制。

C++20 为我们提供了 std::is_constant_evaluated()。当它返回 true 时，说明编译器正在 constexpr 上下文中求值这段代码。我们可以走静态路径：

template <typename Subject, typename CasesTuple>
constexpr auto dispatch(Subject& subject, CasesTuple&& cases) {
    if (std::is_constant_evaluated()) {
        // Compile‑time path: unfold cases statically
        return static_dispatch(subject, std::forward<CasesTuple>(cases));
    }
    // Runtime path: use the normal evaluation engine
    return runtime_dispatch(subject, std::forward<CasesTuple>(cases));
}

理论上很不错。实际上，这只有在 整个 调用点都是 constexpr 时才有帮助。对于运行时匹配但 case 值在编译期已知的情况，case 仍然会被构造，constexpr 分支不会被触发。

我们需要更激进的做法：在编译期检测列表中的每个 case 是否都是静态字面量，然后构建一个稠密的分派表，让运行时求值器能够以 O(1) 的查找方式使用它。

陷阱：[[no_unique_address]] 与 std::is_empty

静态字面模式看起来像空类型：

template <auto V, typename Cmp>
struct static_literal_pattern {
    static constexpr auto value = V;
    [[no_unique_address]] Cmp cmp{};
};

std::equal_to<> 是一个空类型。[[no_unique_address]] 应该允许编译器将 cmp 优化为零大小，从而使整个模式在大小上变得微不足道。

我们使用 std::is_empty 作为静态缓存资格的判断条件：

// Naïve check: if the pattern is empty, we can cache it
if constexpr (std::is_empty_v<T>) {
    // … static cache path
}

这在 GCC 上出现了问题。原因在于：[[no_unique_address]] 是一种许可，而非强制要求。GCC 并不会对非空基类（即使成员本身不是基类）应用该属性。尽管 Cmp 成员是空类型，它仍然导致模式不满足 std::is_empty。

于是静态缓存路径被悄然跳过，稠密分发表从未构建，128‑case 匹配的耗时仍停留在约 11 ns。

修复方案：基于 sizeof<T> 的特性

我们改用了基于大小的特性，无论 [[no_unique_address]] 如何处理都能正常工作：

template <typename T>
constexpr bool is_cacheable_pattern_v = sizeof(T) == 1;

（实际实现细节为简洁起见已省略。）

有了此更改，库能够正确识别静态字面量模式并构建致密表。

数字

在 Intel i7‑13700K、GCC 13.2、-O3 -march=native 环境下进行基准测试。测试对象类型：int，128 条字面量分支，输入为均匀随机。

自动缓存方法与之前的最佳实践（PTN_ON 宏）相匹配，并且与手写 switch 的差距仅为 0.04 ns。这段差距来源于边界检查时的分支预测失误，属于库无法控制的因素。

作为对比：原始实现比手写 switch 慢 9.9×。此次修复后提升至 1.04×。通过在类型特征中更改单个条件，实现了 10× 的性能提升。

关于库设计的启示

• 细小的实现细节很重要。 一个 std::is_empty 检查在某主流编译器上导致了 10 倍的性能下降。
• 依赖编译器扩展（[[no_unique_address]]）可能脆弱。 不同编译器对该属性的处理方式不同；提供可移植的回退方案至关重要。
• 对模式进行静态分析能够收获回报。 识别出所有情况都是编译期字面量后，我们可以用一个稠密的 O(1) 表替代通用的运行时循环。
• 性能关键的库应提供“静态缓存”路径，即使周围代码不是 constexpr 也能工作。

通过将缓存可行性测试改为 sizeof(T)，我们把一个隐藏的性能缺陷转化为可衡量的收益。

模式： 在性能工作中，干净的理论属性往往不是关键，肮脏的经验阈值才是关键。

试一试

实现代码开源于 github.com/sentomk/patternia。

• 调度规划器： include/ptn/core/common/optimize.hpp
• 静态字面量缓存逻辑： include/ptn/core/common/eval.hpp

Header‑only，C++17，仅依赖标准库。