快速生成 "triangle sequence"：避免错误预测

Question

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

这些序列代表了从 n-element 集合中选择 2 个（可能相同）元素的所有方法（对于 (n, n)^{2[ 的序列=53=]), 或矩阵的下三角元素的索引³。单独 i 的值序列是 A003056 in OEIS, while j alone is A002262。该序列经常出现在组合算法中，它们的性能可能很关键。}

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

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

但是，在检查条件 (i == j) - 通常每次 i 增加一个错误预测。随着序列的增加，错误预测的数量变得更少，因为 i 增加了频率降低，因此 j++ 分支占主导地位并且可以很好地预测。尽管如此，某些类型的组合搜索会反复迭代序列中的小项，所以我正在寻找 branch-free 方法或其他一些预测错误较少的方法。

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

¹ 我也很想知道这个序列的正确名称是什么（也许我为这个问题取了一个更好的标题）。我只是编造了 "triangle sequence".

²这里，i >= j版本代表sub-multisets（允许重复），而i > j变体代表正常子集（不重复） ).

³ 这里，i >= j 版本包括主对角线，而 i > j 版本不包括它。

Answer 1

你可以从 i 导出 j:

...set val...
old_j = j;
j = (j + 1) % (i + 1);
if (i == old_j) {
    i++;
}
...loop if more...

并进一步从j和当前i推导出i增量：

...set val...
old_j = j;
j = (j + 1) % (i + 1);
i = i + (i / old_j);
...loop if more...

(暂时无法测试...请复习)

Answer 2

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

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

第二个使用比较和乘法：

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

理论上 "multiplication" 变体应该比 "logical" 变体慢，但测量显示差异很小。

这两种方法只会为允许无分支比较的处理器（例如 x86）生成无分支代码。此外，这些方法假设使用一种语言来实现，其中条件表达式的结果可以很容易地转换为整数（例如 C/C++，其中 "false" 比较被转换为零整数，并且 "true" 个 - 等于“1”的整数）。

这些方法的唯一问题是性能。理论上它们可以胜过分支代码，但前提是错误预测非常频繁。一个简单的测试，除了生成 "triangle sequence"（参见 ideone）之外没有其他工作，显示了悲惨的错误预测率，因此两种无分支方法都比分支方法慢 3 倍。解释很简单：对于更长的序列应该不会有太多的错误预测；至于较短的分支，现代处理器具有非常好的分支预测器，在短分支模式的情况下几乎不会失败；所以我们没有太多的错误预测，分支代码几乎总是只执行 2 条指令（比较，递增），而无分支代码执行主动和指示 "branches" 加上一些特定于无分支方法的指令。

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

Answer 3

在Python中我们可以表示为：

i, j = i + (i == j), (j + 1) * (i != j)

但事实证明，在大约一百万次迭代后，在我的机器上，以下更冗长的惰性评估代码快了大约 20%：

from itertools import count, repeat

def gen_i():
    """ A003056 """
    for x in count(0):  # infinitely counts up
        yield from repeat(x, x + 1)  # replication

def gen_j():
    """ A002262 """
    for x in count(0):  # infinitely counts up
        yield from range(x + 1)  # count up to (including) x

sequence = zip(gen_i(), gen_j())

for _ in range(1000000):
    i, j = next(sequence)

上述代码中，gen_i()、gen_j()、count()、repeat()、zip()都是生成器（而range()是一个迭代器）所以 sequence 继续按需调用代码，因为需要新的 (i, j) 对。我假设 range() 和 repeat() 的实现都因预测错误而终止。

简单不一定也很快（即考虑所有不必要的零加法和紧凑形式的乘法。）

那么，快速生成序列和避免错误预测哪个更重要？

快速生成 "triangle sequence"：避免错误预测

Quickly generating the "triangle sequence": avoiding mispredictions

language-agnostic

performance

sequences

bit-manipulation

oeis