如何在不损失性能的情况下从大循环中提取预定义的巨大开关？

Question

我有一个瓶颈，看起来是这样的：

void function(int type) {
    for (int i = 0; i < m; i++) {
        // do some stuff A
        switch (type) {
        case 0:
            // do some stuff 0
            break;
        [...]
        case n:
            // do some stuff n
            break;
        }
        // do some stuff B
    }
}

N和m足够大。

百万，有时是数亿。

N是2^7-2^ 10 (128-1024)

代码块A和B足够大。

我重写了代码(通过宏)如下：

void function(int type) {
    switch (type) {
    case 0:
        for (int i = 0; i < m; i++) {
            // do some stuff A
            // do some stuff 0
            // do some stuff B
        }
        break;
    [...]
    case n:
        for (int i = 0; i < m; i++) {
            // do some stuff A
            // do some stuff n
            // do some stuff B
        }
        break;
    }   
}

因此，在IDA中，这个函数如下所示：

​

有没有办法将开关从循环中移除：

1. 而不创建循环的一堆副本。
2. 不使用宏创建巨大的函数
3. 而不失去表现？

在我看来，一个可能的解决方案是goto变量的存在。就像这样：

void function(int type) {
    label* typeLabel;
    switch (type) {
    case 0:
        typeLabel = &label_1;
        break;
    [...]
    case n:
        typeLabel = &label_n;
        break;
    }

    for (int i = 0; i < m; i++) {
        // do some stuff A
        goto *typeLabel;
        back:
        // do some stuff B
    }

    goto end;

    label_1:
    // do some stuff 0
    goto back;
    [...]
    label_n:
    // do some stuff n
    goto back;

    end:
}

所有这一切都将在不同的Android设备上以不同的速度进行，这也使事情变得更加复杂。

作为ARM的架构，和x86。

也许这可以做汇编程序插入而不是纯C？

编辑：

我做了一些测试。N= 45,734,912

循环内开关: 891,713μs

循环内开关: 976,085μs

环内开关比循环内开关快9.5%

例如:没有开关的简单实现需要1,746,947μs

Answer 1

目前，我能看到的最好的解决办法是：

使用宏n函数生成，如下所示：

void func_n() {
    for (int i = 0; i < m; i++) {
        // do some stuff A
        // do some stuff n
        // do some stuff B
    }
}

然后创建一个指向它们的指针数组，并从主函数调用：

void main(int type) {
    func* table[n];
    // fill table array with pointers to func_0 .. func_n

    table[type](); // call appropriate func
}

这允许优化器优化编译器函数func_0。func_n。而且，它们不会有那么大。

Answer 2

实际上，静态标签数组可能是最快的正确选项(指针数组是最明智的快速选项)。但是，让我们发挥创造力。

(请注意，这应该是一个评论，但我需要空间)。

选项1:利用分支预测器

让我们建立在这样一个事实之上:如果某个分支的某个结果发生了，那么预测器很可能在将来预测相同的结果。尤其是如果不止一次发生的话。代码看起来类似于：

for (int i = 0; i < m; i++) 
{
    // do some stuff A
    if (type < n/2) 
    {
        if (type < n/4) 
        {
            if (type < n/8) 
            {
                if (type == 0) // do some stuff 0
                else           // do some stuff 1
            } 
            else 
            {
                ...
            }
        } 
        else 
        {
             ...
        }
    } 
    else 
    {
        ...
        // do some stuff n
    }

    // do some stuff B
}

基本上，在log(n)步骤中，二进制搜索应该做什么。这是一个日志(N)可能的跳转，但经过一次或两次迭代，分支预测器将正确地预测它们，并将无问题地推测执行正确的指令。根据CPU的不同，这可能比goto *labelType; back:更快，因为在动态计算跳转地址时，有些人无法预取指令。

选项2: JIT加载正确的“东西”

因此，理想情况下，您的代码如下所示：

void function(int type) {
    for (int i = 0; i < m; i++) {
        // do some stuff A
        // do some stuff [type]
        // do some stuff B
    }
}

在当前函数调用中，所有其他的0.n“东西”都是垃圾。好吧，让我们这样做：

void function(int type) {
    prepare(type);
    for (int i = 0; i < m; i++) {
        // do some stuff A
        reserved:
        doNothing(); doNothing(); doNothing(); doNothing(); doNothing();
        // do some stuff B
    }
}

doNothing()调用的存在只是为了保留函数中的空间。最好的实现是goto B。prepare(type)函数将查找所有0..n实现的查找表，获取type实现，并将其复制到所有的goto B上。然后，当您实际执行您的循环时，您将得到最优的代码，在那里没有不必要的跳转。

只需确保在goto B实现中有一些最终的stuff指令--复制一个较小的而不是更大的一个可能会导致问题。或者，在退出function之前，您可以还原所有占位符goto B;指令。这是一个很小的成本，因为每次调用只执行一次，而不是每次迭代。

在程序集中实现prepare()要比在C中容易得多，但它是可行的。您只需要所有stuff_i实现的开始/结束地址(在您的文章中，这些是label_[i]和label_[i+1])，并将其转化为reserved。

也许编译器甚至会允许您这样做：

memcpy((uint8_t*)reserved, (uint8_t*)label_1, (uint8_t*)label_2 - (uint8_t*)label_1);

但很可能不会。但是，您可以使用setjmp或函数调用中的__builtin_return_address / _ReturnAddress之类的东西获得适当的位置。

请注意，这将需要对指令内存进行写访问。获取它是特定于OS的，并且可能需要su/admin特权。

Answer 3

编译器通常擅长选择switch的最优形式。对于ARM设备，您可以有几个窗体用于密集的代码段。或者是一个分支表(像一堆函数指针)，或者如果开关中的代码接近相同，您可以做一个数组索引。从语义上说，

 dest = &first_switch_pc;
 dest += n*switch_code_size;
 current_pc = dest;

ARM CPU可以在一条指令中做到这一点。在您的情况下，这可能是无利可图的，因为type似乎是每个循环迭代的常数。

但是，我肯定会探索像这样对代码进行重组，

void function(int type) {
    i = 0;
    if (m==0) return;
    // initialize type_label;
    goto entry;
    while(1) {
        // do some stuff B
        i++;
        if(i < m) break;
    entry:
        // do some stuff A
        goto *type_label;

        label_1:
       // do some stuff 0
       continue;
       [...]
       label_n:
       // do some stuff n
       continue;
    }
}

这将合并'A‘和'B’，这样它就能很好地适应代码缓存。然后，从“goto标签”到循环顶部的“控制流”。您可能可以简化控制流逻辑，具体取决于在未知代码段中如何使用i。编译器可能会根据优化级别等自动为您做这件事。没有更多的信息和分析，没有人能给出真正的答案。“A”、“B”的成本和开关片段的大小都很重要。检查汇编程序输出总是有帮助的。