性能 – 快速生成“三角形序列”：避免错误预测

我有兴趣计算三角形sequence1,它是对(i,j)的序列：(0,0),(1,0),(1,1),(2,0),(2,1) )…
它以i> = j的限制迭代所有对(i,j).具有但不限于i的相同序列> j也很有趣.

这些序列代表了从n元素集中选择2个(可能相同)元素的所有方法(对于序列到(n,n)2),或者矩阵3的下部三角元素的索引3 .单独i的值序列在OEIS中是A003056,而j单独的值是A002262.序列经常出现在组合算法中,其中它们的性能可能是关键的.

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

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

然而,在检查条件(i == j)时,在计算序列的初始元素时会遇到许多错误预测 –
通常每次我增加一个误预测.随着序列的增加,由于i递增,误预测的数量变得更低
频率降低,因此j分支占主导地位并得到很好的预测.仍然,某些类型的组合搜索反复迭代
序列中的小术语,所以我正在寻找一种无分支的方法或其他方法,这些方法可以减少错误预测.

对于许多用途,序列的顺序并不重要,因此如果它导致的话,生成不同于上面的顺序的值是允许的.
更好的解决方案.例如,j可以向下计数而不是向上计数：(0,0),(1,1),(1,0),(2,2),(2,1),….

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

这里,i> = j版本表示子多重(允许重复),而i> 1. j变体表示正常子集(无重复).

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

以下是两种不使用任何昂贵计算的无分支方法.第一个使用比较和逻辑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条指令(比较,增量),而无分支代码执行主动和非执行“分支”以及一些特定于无分支方法的指令.

如果您想重复迭代序列中的小项,可能其他方法更可取.您只计算一次序列,然后重复从内存中读取它.