快速生成"三角形序列":避免错误预测

Question

我有兴趣计算三角形序列¹,这是一对对的序列,(i, j): (0, 0), (1, 0), (1, 1), (2, 0), (2, 1) ... 它们迭代所有(i, j)具有限制的对i >= j.具有限制i> j的相同序列也是有趣的.

除了其他之外,这些序列表示从n元素集(对于序列直到(n, n)²)或矩阵³的下部三角元素的索引选择2(可能相同)元素的所有方式.i单独的值序列是OEIS中的A003056,而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), ....

---

¹我也很想知道这个序列的正确名称是什么(或许我为这个问题做了更好的标题).我只是编造了"三角形序列".

²此处,i >= j版本表示子多重集(允许重复),而i > j变体表示正常子集(不重复).

³这里,i >= j版本包括主对角线,而i > j变体排除它.

Answer 1

以下是两种不使用任何昂贵计算的无分支方法.第一个使用比较和逻辑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);

理论上,"乘法"变量应该比"逻辑"变量慢,但测量显示差异很小.

这两种方法都会导致无分支代码仅适用于允许无分支比较的处理器(例如x86).这些方法也假设使用一种语言来实现,其中条件表达式的结果可以很容易地转换为整数(例如C/C++,其中"false"比较被转换为零整数,而"true"则转换为等于"整数"的整数) 1" ).

这些方法的唯一问题是性能.它们理论上可以胜过分支代码,但只有当错误预测真的很频繁时才会出现.除了生成"三角形序列"(在ideone上看到它)之外没有其他工作的简单测试显示了可怜的错误预测率,因此两种无分支方法比分支方法慢3倍.解释很简单:对于较长的序列应该没有太多的错误预测; 对于较短的分支,现代处理器具有非常好的分支预测器,在短分支模式的情况下几乎不会失败; 所以我们没有多少错误预测,分支代码几乎总是只执行2条指令(比较,增量),而无分支代码执行主动和非执行"分支"以及一些特定于无分支方法的指令.

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