哪些实现符合 std::visit 的恒定时间调度？

Question

经常引用 C++ std::variant 的性能比其他语言的变体差。参见例如https://pbackus.github.io/blog/beating-stdvisit-without-really-trying.html

原因之一是 exception 状态，另一个据说是标准的要求 std::visit 复杂性 does not depend on the number of types 这迫使实施者使用调度 table 的函数指针，它抑制了某些优化，如内联。

问题：

将 std::visit 实施为 if-elseif 的链条是否合法，其中每个检查都类似于 if(v.index() == I) return visitor(get<I>(v));？似乎不是，因为调度到更高的索引需要对索引进行更多检查。
用switch(v.index()) case I: return visitor(get<I>(v));这样的开关实现是否合法？这看起来像 "independent of the number of types"，因为控制流直接跳转到案例，例如Microsoft 为少于 64（或左右）种类型实现了它。
如果switch是合法的，那么优化器将小switch转换为if-elseif ladder是否合法？ MSVC 编译器再次执行此操作：https://godbolt.org/z/D2Q5ED。但是 IMO 这违反了标准规定的 "independent of number of types" 复杂性，尽管实际上它会更快。

我的提问是基于 reddit 上有人声称 "Constant time" again refers to the behavior in the limit. 我不太同意的讨论。 IMO "Constant time" 意味着无论输入如何，时间都是恒定的，对于 if-elseif-chain 来说情况并非如此。

但我不确定这在此处如何适用。似乎 1. 是非法的，2. 是合法的，但优化器（可能）将其转换为 1. 这意味着 2. 也是非法的。至少如果严格遵守标准。

Answer 1

您混淆了时间复杂度和运行时间。例如参见 [=26=] .

话虽这么说，但在谈论复杂性时，了解 "constant time" 和 "does not depend on" 等语句的含义很重要：在这种情况下，它们都是 O 的同义词(1)。所以，reddit评论中的说法确实是正确的。

在 visit 的情况下，这意味着存在一些常量 C，使得 visit 永远不会超过 C cpu 周期，即使对于疯狂数量的类型variant。特别是，低于这个数C当然是允许的。

因此，要真正回答您的问题：使用 if-else if 链独占通常具有线性（即 O(n)）复杂度，正如您正确陈述的那样。因此，除非实施者知道编译器会将其优化为常量，否则这是非法的。

A switch 很可能会被编译为跳转 table，这在 O(1) 中有效。如果 case 是后续的整数数量，这种情况尤其可能发生，就像这里的情况一样。因此，使用 switch 的实现应该是合法的。但是请注意，对于 cases 的困难分布，switch 将被编译为 O(log n) 的二进制搜索。参见 here.

最后，鉴于我之前所说的，当然允许应用任何类型的优化，只要这不会使算法变得更复杂 class。即使这意味着 实际运行时间 确实取决于类型的数量，但 时间复杂度 并不。

更新：

根据您的评论，让我给您举一个函数示例，该函数 复杂度 ，独立于 n（又名 "constant"或 O(1)) 而 实际运行时间 当然取决于 n:

int get_max_of_first_50(std::vector<int> const& v)
{
    int max = std::numeric_limits<int>::min();
    for (int i = 0; i < 50; ++i)
        if (v[i] > max)
            max = v[i];

    return max;
}

此函数将始终执行 50 次或更少的迭代，无论 v.size() 可能有多大。因此，在复杂性方面，它被 class 化为常数算法， 独立于 n，或 O(1 );所有三个语句都是等价的。

这可能看起来像作弊，在某种程度上我可以理解这个推理，但重要的是要明白这就是 复杂性 以这种方式引入的原因第一名：

允许在算法分析中进行某些简化。否则很容易变得非常困难
只关心巨大的投入。通常，没有人关心某件事是在 5 毫秒还是 10 毫秒内完成。但是 5 天 vs. 10 天确实很重要。

顺便说一句，"cheating" 这种方式很常见。另一个著名的例子是 std::sort 的实现。基本上，我听说过的大多数库实现都使用 Quicksort（有一些技巧，所以即使在最坏的情况下也是 O(n log(n))）。但是对于小序列，他们通常会切换到插入排序，这在非常小的范围内被证明更快，即使它本身是一种复杂度为 O(n^2) 的算法。但是正如已经解释的那样，从复杂性的角度来看，只要它的用法受常数约束就可以了。而且从实际运行时间来看，当然也好，速度快

哪些实现符合 std::visit 的恒定时间调度？

Which implementations are conformant for constant time dispatch of std::visit?

c++

std

variant

c++-standard-library

visitor-pattern

更新：