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

Gregory 发表于 Dev

格雷戈里

我有一个算法的核心，我想将本质上一系列大约20深度的if / else if / else if / else i /链转换为可以线性进行的循环。条件条件很简单，具有以下四种可能性之一（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个中的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));
}

cmaster-恢复莫妮卡

没有向量化，您的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;

现在，您可以自由地进行循环。

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。