判断整数序列是否可以在不使用分支的情况下生成的技术？

Question

如果你正在为一个分支开销很大的架构进行优化（比如PS3的cell处理器），那么确定是否可以在不使用分支或者至少使用更少的分支的情况下表达给定算法就变得非常重要。我经常在未经优化的代码中看到一种模式，即使用一堆if来调整某个数组的索引（如果数组大小为奇数，则将索引增加1，在某些其他情况下，乘以2等）。因此，如果有一种方法，可以通过两个数字列表来确定是否可能编写一个无分支函数，将一个列表转换为另一个列表，那就太好了。

例如，最近我想知道是否有可能编写一个无分支函数，将以下内容转换为：0、1、2、3、4、5、6、7、8、9 到 0、2、4、6、8、9、7、5、3、1（升序偶数后跟降序奇数）。从技术上讲，我可以编写一个大的switch/case函数，但显然我感兴趣的是一个能够遵循任意大小模式的函数。使用分支编写执行此转换的函数很简单，但如果有一种非分支方式来实现它，这并不是立即显而易见的。

那么，有没有一般的方法来解决这类问题，或者有什么快速的试金石？还是必须逐案证明？如果它们实际上是不可能的，那么在这些问题上努力工作就没有意义了。我似乎记得曾经读过一篇文章，介绍了仅使用算术而不使用分支的函数的正式数学术语，但我想不起来了。

- Joseph Garvin

---

没有分支？这是否意味着该函数对任何参数执行完全相同的原始操作序列？或者您可以做类似“读取值n，然后移动到第n个元素...”的事情吗？在前一种情况下，显然是不可能的，在后一种情况下，只是繁琐而已。还是您指的是其他什么？ - Beta

我的意思是条件语句和相应的跳转指令。根据您的意思，“移动到值n”可能属于该类别。如果您的意思是调用由数组中索引为n的函数指针，则算作分支。如果您的意思是从某个地方读取n，然后使用它来索引一个数组，则不需要任何分支。基本上没有“如果这是真的就走这条路，否则走那条路”的情况（请注意，循环条件按此定义计数）。 - Joseph Garvin

我可能没有理解问题，因为直接数组索引看起来可以工作。J = A[I] 如果你想对整个数组进行操作而不仅仅是单个数字，你可以展开循环或使用达夫设备来减少分支成本。 - Mike Dunlavey

从技术上讲，我可以编写一个大的switch/case函数，但显然我对一个可以遵循任意大小模式的函数感兴趣。 - Joseph Garvin

Answer 1

将0、1、2、3、4、5、6、7、8、9转换为0、2、4、6、8、9、7、5、3、1（先按升序排列偶数，然后按降序排列奇数）。

简单来说，给定从0到N-1的X的N个值的序列，我们可以看到序列的前一半是2X。序列的后一半是（2N-1）-2X。序列在X=(N+1)/2处分割，“整数”运算。在上面的例子中，N == 10。

所以假设使用带有算术右移的32位有符号整数：

int Transform(int x)
{
    const int seq1=x+x;
    const int mask=(x-((N+1)>>1))>>31;
    const int seq2=(N+N-1)-seq1;
    return (mask&seq1)|((~mask)&seq2);
}

请注意，这里使用的掩码模式非常快，因为PowerPC有一个ANDC（与补码）操作，使得（~mask）成为一种免费操作。

- Adisak

---

你能解释一下你是怎么想出那个解决方案的吗？我更希望了解处理这些问题的一般方法，而不仅仅是为一个实例提供现成的解决方案，虽然我同样感激它 :) - Joseph Garvin

我注意到有两个序列...奇数和偶数。我为每个序列推导了整数公式，然后想出了一个掩码条件。每当你需要在两个条件之间选择，并且有一个明确定义的边界时，很容易制作一个无分支表示。 - Adisak

当您开始有超过两个条件可供选择时，确定边界条件和掩码变量变得困难。 - Adisak

Answer 2

如果您将所需的索引绘制成三角形函数，就可以得到与输入索引相对应的图形。结果表明，在您的n=10情况下，它是这样的。

9.5 - abs(2 (x - 4.75))

因此，对于一般的n，它将是

n-0.5 - abs(2*(x - n/2-0.25))

或者以整数形式表示，

(2*n-1 - abs(4*x - 2*n + 1)) / 2

这是完全基于分支的思想，在输出索引方面，只需使用单个数学函数即可生成。我认为一般的方法是绘制所需的索引图，并寻找一种表示它的模式和数学函数的方式。

显然，如果你所需的最终索引形成一条直线，则变换很简单。如果你的映射中有一个折点，那么你想要使用绝对值函数来引入弯曲，并且你可以调节缩放来改变弯曲的角度。你可以通过偏置来倾斜这个拐点（例如abs(x)+x/2）。如果你需要在最终索引函数中出现跳跃间断点，则使用符号函数（希望内置或使用abs(x)/x）。你需要创造性地利用常见函数的图形来发挥优势。

---

附录

如果您的索引函数是分段线性的，则有一种简单的算法。假设所需的索引函数表示为一系列线段。

{(sx1,sy1)-(ex1,ey1), (sx2,sy2)-(ex2,ey2), ... , (sxN,syN)-(exN,eyN)}
 segment 1            segment 2                   segment N

对于所有的K，exK > sxK，并且对于所有的K，sxK > sx(K-1)（从左到右排列）。

k = 1
f(x) = Make affine model of segment k
g(x) = f(x)
Do:
   k = k + 1
   h(x) = Makeaffine model of segment k
   If g(x) and h(x) intersect between ex(k-1) and ex(k)
       f(x) = f(x) + [slope difference of g(x) and h(x)] * ramp(x)
   Else
       f(x) = f(x) + (h(ex(k-1)) - f(ex(k-1))) * step(x)
       f(x) = f(x) + [slope difference of g(x) and h(x)] * ramp(x)

ramp(x) = (abs(x)+x)/2，step(x) = (sign(x)+1)/2。f(x)代表所需函数，g(x)是上一个段落的仿射模型，h(x)是当前段落的仿射模型。仿射模型只是斜率偏移形式的一条线：a*x+b，而斜率差就是斜率的差异。该算法从左到右简单地进行，随着其前进，添加适当的函数片段。它添加的函数对于x <= 0总是为零，因此不会影响到目前已经建立起来的f(x)。

当然，以上内容可能存在一些错误/打字错误。我真的要去开会了，所以不能再写了。

- Victor Liu

---

你能在没有分支的情况下计算abs()吗？ - Drew Hall

Abs并不总是针对整数硬件实现的，但fabs是常见的FPU操作。对于整数，您可以使用无分支的方式进行绝对值计算：int Abs(int A) { int Sign = A >> 31; return ( A ^ Sign ) - Sign; }。 - Adisak

转换INT到FLOAT再返回会因LHS（Load Hit Store）惩罚在PS3上非常缓慢，就这个问题而言，在目标平台上使用分支版本会慢得多。 - Adisak

分段线性附加物绝对不能在循环中解决无分支要求的问题。要实现无分支，必须同时计算所有值，然后进行无分支选择。在进行无分支优化时，还应该尽可能地折叠计算值的常见表达式。 - Adisak

算法的目的是生成代码，而不是直接将其作为代码使用。 - Victor Liu

Answer 3

如果你特别是在优化PS3，Power PC Compiler Writers Guide的第3.1.5节中有关于无分支代码的技巧，附录D中有GNU Superoptimizer序列的无分支代码。

你可能也会对Mike Acton's Cell Performance博客感兴趣。

- Adisak

---

顺便提一下，如果你去找的话，X86也应该有许多常见情况的GNU Superoptimizer序列。 - Adisak

Answer 4

例如，您始终可以使用拉格朗日插值编写多项式公式。虽然不太美观（或特别快），但它不会有任何分支。

- lhf

Answer 5

如果速度确实很重要，那么你不能把列表的指令写出来，直到某个特定长度为止吗？（当然可以预先生成这段代码）。

 void algorithm1_Length6(int *srcList, int *destList)
 {
      *destList++ = *srcList;
      *destList++ = srcList[2];
      *destList++ = srcList[4];
      *destList++ = srcList[5];
      *destList++ = srcList[3];
      *destList++ = srcList[1];
 }

以及所有其他长度不超过一定长度的变体。

- Toad

---

从技术上讲，我可以编写一个大的switch/case函数，但显然我对一个能够遵循任意大小模式的函数感兴趣。 - Joseph Garvin

Answer 6

从技术上讲，任何一系列操作都可以使用利用布尔运算的状态机执行而无需“分支”。分支的概念是因为大多数程序是通过可以向左或向右走的程序计数器执行的一系列指令。

即使你谈论的是纯函数式方法——它是无状态的，对于有限的离散值集合，你总是可以（以大量内存为代价）使用查找表。

- Jason S

Answer 7

对于给定的数组，您可以使用以下方法：

 void tranform(int[] src, int[] dest) {
        //0, 2, 4, 6, 8, 9, 7, 5, 3, 1
        dest[0] = src[0];
        dest[1] = src[2];
        dest[2] = src[4];
        dest[3] = src[6];
        dest[4] = src[8];
        dest[5] = src[9];
        dest[6] = src[7];
        dest[7] = src[5];
        dest[8] = src[3];
        dest[9] = src[1];
    }

但是对于大数组来说，编写这样的方法往往很困难，因此编写生成器方法会很有用：

static void createFunction(int[] src, int[] dest) {
        System.out.println("void tranform(int[] src, int[] dest) {");
        for (int i = 0; i < dest.length; i++) {
            for (int j = 0; j < src.length; j++) {
                if (dest[i] == src[j]) {
                    System.out.println("dest[" + i + "]=src[" + j + "];");
                    break;
                }
            }
        }
        System.out.println("}");
    }

使用以下代码调用您的数组：

createFunction(new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, new int[]{0, 2, 4, 6, 8, 9, 7, 5, 3, 1});

并将该方法的输出粘贴到您的程序中。

- rachvela

---

我特别提到我正在寻找能够处理不同大小输入的函数。制作一个可以处理不同大小并生成不能处理不同大小的函数的函数是一种创造性的解决方法，但这不是我要找的。即使忽略它的hackishness，如果优化是一个目标，这绝对不是一个好的解决方案。 - Joseph Garvin