如何将一系列if/else if/else if/ chain转换为线性循环代码

Question

我有一个算法的核心，我想把它从一系列的if/else i/ chain (大约20深)转换成一个可以以线性方式完成的循环。条件句简单，有四种可能性之一(Ai < Bj)，(Ai <= Bj)，(Ai > Bj)，(Ai >= Bj)。如何将所有这些条件转换为单个条件。例如，这条链可以是这样的。

if (A[i+0] <  B[j+0]) break
if (A[i+1] <= B[j+1]) break
if (A[i+2] >  B[j+2]) break
if (A[i+3] >= B[j+3]) break
if (A[i+4] >= B[j+4]) break
....

每个条件可以是4种可能中的1种，但我想将它们转换成一组没有情况的步骤，这样就可以在一个循环中完成(或者可能与向量本质并行)。

// Given a list R[n] of 4 possible relations loop over all the data
int result = 1;
for (i = 0; i < num_relations && result; ++i) {           
       // How do I convert this to linear code which does the equivalent of
       // (the value of R[n] and what relation it maps is flexible, this is an example)
       case (R[n]) {
          0 : result = A[i] <  B[i]; break;
          1 : result = A[i] <= B[i]; break;
          2 : result = A[i] >  B[i]; break;
          3 : result = A[i] >= B[i]; break;
       }
}

可以使用的(无符号数字)的一些属性包括

(A > B) ^ 1 === (A <= B) ^ 0

能不能把上面的东西优化成比

result = 1;
for (i = 0; i < num_relations && result; ++i) {           
   result = ((A[i] <  B[i]) && (R[i] == 0)) ||
            ((A[i] <= B[i]) && (R[i] == 1)) ||
            ((A[i] >  B[i]) && (R[i] == 2)) ||
            ((A[i] >= B[i]) && (R[i] == 3));
}

Answer 1

没有矢量化，您的if()序列将尽可能快。在这种情况下，每个条件都必须有一个比较指令，您无法绕过它(即使一些机器可以优化除了一个之外的分支)。

通过矢量化，您可以并行地执行多个比较，条件是它们都在同一个方向上。但这可以通过转换输入值来实现：

int signs[] = {1, 1, -1, -1, -1, ...};
int equals[] = {0, 1, 0, 1, 1, ...};
if (A[i+0] <  signs[0]*B[j+0] + equals[0]) break;
if (A[i+1] <  signs[1]*B[j+1] + equals[1]) break;
if (A[i+2] <  signs[2]*B[j+2] + equals[2]) break;
if (A[i+3] <  signs[3]*B[j+3] + equals[3]) break;
if (A[i+4] <  signs[4]*B[j+4] + equals[4]) break;
...

但是，这段代码的矢量化应该会失败，因为在计算第一个条件之前，编译器不需要从内存中加载A[i+1]，并且显示没有实现。因此，您需要使条件评估不依赖于彼此：

int signs[] = {1, 1, -1, -1, -1, ...};
int equals[] = {0, 1, 0, 1, 1, ...};
int doBreak = 0;
doBreak |= (A[i+0] <  signs[0]*B[j+0] + equals[0]);
doBreak |= (A[i+1] <  signs[1]*B[j+1] + equals[1]);
doBreak |= (A[i+2] <  signs[2]*B[j+2] + equals[2]);
doBreak |= (A[i+3] <  signs[3]*B[j+3] + equals[3]);
doBreak |= (A[i+4] <  signs[4]*B[j+4] + equals[4]);
...
if(doBreak) break;

现在你可以自由地利用它做一个循环了。

Answer 2

1. 创建满足签名的四个助手函数： bool (*)(int A，int B)；bool isLess(int A，int B) {返回A< B；} bool isLessOrEqual(int A，int B) {返回A <= B；} bool isGreater(int A，int B) {返回A> B；} bool isGreaterOrEqual(int A，int B) {返回A >= B；}
2. 把它们放在一个数组里。 CompareFunction functions[] = {isLess，isLessOrEqual，isGreater，isGreaterOrEqual}；
3. 使用循环中的函数数组。 对于(i = 0；i< num_relations &&计算所；++i) { result = functionsi；}

Answer 3

您可以使用按位的AND

result = 1;
for (i = 0; i < num_relations && result; ++i) {           
    delta = A[i] - B[i];

    //  R[i] & 1 is true for 1 and 3
    //  R[i] & 2 is true for 2 and 3   
    if (delta == 0) {
        result = (R[i] & 1);
    }
    else  {
        //  exclusive or
        result = (delta < 0) ^ (R[i] & 2);
    }
}

诀窍是合并用例，从而减少关系操作的数量。