c++ - 如何将一系列if/else if/else if/关系链转换成线性循环代码

Question

我有一个算法的核心，我想将其从本质上从一系列 if/else if/else if/else i/链大约 20 深转换为可以以线性方式完成的循环。条件很简单，有 4 种可能性之一 (A[i] < B[j]), (A[i] <= B[j]), (A[i] > B[j]), (A[ i] >= B[j]).我怎样才能将它们全部转换为一个条件。例如，链可能是这样的。

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 种可能中的一种，但我想将它们全部转换为一组没有大小写的步骤，以便它可以在循环中完成(或者可能与 vector 内在函数并行)

// 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;

现在您可以随意制作一个循环了。