performance - 快速生成 "triangle sequence": avoiding mispredictions

Question

我对计算三角形序列1感兴趣，它是对的序列(i, j): (0, 0), (1, 0), (1, 1), (2, 0), (2, 1) ...它遍历所有对 (i, j)限制为 i >= j .相同的序列但具有限制 i > j 也很有趣。

除其他外，这些序列表示从 n 元素集中选择 2 个(可能相同)元素的所有方式(对于直到 (n, n) 2 的序列)，或矩阵的下三角元素的索引。 i 的值序列只有A003056在 OEIS 中，而 j只有A002262 .该序列经常出现在组合算法中，它们的性能可能很关键。

生成序列中下一个值的一种简单但分支的方法是:

if (i == j) {
    j = 0;
    i++;
  } else {
    j++;
  }      
}

但是，在检查条件 (i == j) 时，这会在计算序列的初始元素时出现许多错误预测。 ——
一般每次都会有一个错误预测 i递增。随着序列的增加，错误预测的数量从 i 开始减少。递增
频率降低，所以 j++分支占主导地位并且被很好地预测。尽管如此，某些类型的组合搜索会反复迭代
序列中的小项，所以我正在寻找一种无分支的方法或其他一些较少错误预测的方法。

对于许多用途，序列的顺序并不重要，因此如果它导致以下结果，则以与上述不同的顺序生成值是允许的
更好的解决方案。例如， j可以倒数而不是倒数: (0, 0), (1, 1), (1, 0), (2, 2), (2, 1), ... .

1 我也很想知道这个序列的正确名称是什么(也许所以我为这个问题做了一个更好的标题)。我只是编造了“三角形序列”。

2 在这里， i >= j版本代表子多重集(允许重复)，而 i > j变体代表正常子集(无重复)。

3 在这里， i >= j版本包括主对角线，而 i > j变体排除它。

Answer 1

这里有两种不使用任何昂贵计算的无分支方法。第一个使用比较和逻辑与:

const bool eq = i == j;
i += eq;
j = (j + 1) & (eq - 1);

第二个使用比较和乘法:

const bool eq = i == j;
i += eq;
j = (j + 1) * (1 - eq);

理论上，“乘法”变体应该比“逻辑”变体慢，但测量显示差异很小。

这两种方法都会导致只有允许无分支比较的处理器(例如 x86)的无分支代码。此外，这些方法假设使用一种语言来实现，其中条件表达式的结果可以轻松转换为整数(例如 C/C++，其中“假”比较转换为零整数，而“真”比较转换为等于“的整数” 1”)。

这些方法的唯一问题是性能。理论上，它们可以胜过分支代码，但前提是错误预测非常频繁。一个简单的测试，除了生成“三角形序列”之外没有其他工作(参见 ideone)显示出悲惨的错误预测率，因此两种无分支方法比有分支方法慢约 3 倍。解释很简单:对于更长的序列应该不会有太多的错误预测；至于较短的，现代处理器具有非常好的分支预测器，在短分支模式的情况下几乎永远不会失败；所以我们没有太多的错误预测，分支代码几乎总是只执行 2 条指令(比较、增量)，而无分支代码执行事件和触发“分支”以及一些特定于无分支方法的指令。

如果您想 repeatedly iterate over the small terms in the sequence ，可能其他方法会更可取。您只计算一次序列，然后从内存中重复读取它。