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

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 中看起来像这样：

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

无需创建一堆循环副本
不使用宏创建庞大的函数
不损失性能？

在我看来可能的解决方案是存在 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

loop-within-switch 比 switch-within-loop 快 9.5%

例如：不带switch的简单实现耗时1,746,947 μs

Answer 1

实际上，静态标签数组可能是最快的理智选项（指针数组是最理智的快速选项）。但是，让我们发挥创意吧。

（请注意，这应该是评论，但我需要 space）。

选项 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) 步中二分搜索要做什么。这是 log(n) 次可能的跳跃，但仅经过一两次迭代后，分支预测器将正确预测它们，并将毫无问题地推测性地执行正确的指令。根据 CPU，这可能比 goto *labelType; back: 更快，因为有些指令在动态计算跳转地址时无法预取指令。

选项 2：JIT 加载正确的 'stuff'

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

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 "stuffs" 在当前函数调用中都是垃圾。好吧，就这样吧：

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() 调用只是为了保留函数中的 space。最佳实施是 goto B。 prepare(type) 函数将在查找 table 中查找所有 0..n 实现，获取 type 一个，并将其复制到所有这些 goto B 中。然后，当您实际执行循环时，您将获得没有不必要跳转的最佳代码。

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

prepare() 在汇编中比在 C 中更容易实现，但它是可行的。您只需要所有 stuff_i 实现的 start/end 地址（在您的 post 中，这些是 label_[i] 和 label_[i+1]），以及 memcpy 到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 2

编译器通常擅长选择 switch 的最佳形式。对于 ARM 设备，您可以为密集的代码片段提供几种形式。一个分支 table （就像一堆函数指针）或者如果开关中的代码几乎相同，你可以做一个数组索引。语义上是这样的，

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

ARM CPU 可以在一条指令中完成此操作。在您的情况下，这可能不是 profitable，因为 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 label' 中的 'control flow' 将到达循环的顶部。您也许可以根据 i 在未知片段中的使用方式来简化控制流逻辑。编译器可能会根据优化级别等自动为您执行此操作。没有更多信息和分析，没有人能真正给出答案。 'stuff A'、'stuff B' 的成本和开关片段的大小都很重要。检查汇编器输出总是有帮助的。

Answer 3

目前，我能看到的最佳解决方案是：

使用宏 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 4

This pdf of slides from a presentation 关于让 gcc 进行线程跳转很有趣。这是 gcc 需要做的精确优化，以类似于 loop-inside-switch 版本编译 switch-inside-loop 版本。

顺便说一句，loop-inside-switch 版本在性能上应该等同于 loop-inside-separate-functions 版本。缓存根据缓存行而不是整个功能进行操作。如果一个函数中的大部分代码从来没有运行s，那么它在那里并不重要。只有执行运行的代码才会在缓存中使用 space。

如果 Android 设备中的所有 ARM 内核都具有间接跳转的分支目标预测，那么您的第二个执行编译器的工作并在循环内执行间接 goto 的实现可能是最好的权衡代码大小和性能之间。正确预测的无条件间接分支的成本与 x86 上的一对 add 指令的成本大致相同。如果 ARM 类似，代码大小的节省应该是值得的。这些幻灯片讨论了一些具有间接分支预测的 ARM 内核，但并没有说所有内核都可以。

This Anandtech article about A53 cores (the little cores in big.LITTLE) says that A53 vastly increased the indirect-branch prediction resources compared to A7. A7 cores have an 8-entry indirect branch target buffer. That should be enough to make the goto *label in your loop efficient, even on very weak LITTLE cores, unless the rest of your loop has some indirect branches inside the loop. One mispredict on the occasional iteration should only cost maybe 8 cycles. (A7 has a short 8-stage pipeline, and is "partial dual issue, in-order"，因此分支预测错误比在更强大的 CPU 上更便宜。

更小的代码大小意味着从闪存加载的代码更少，如果使用 type 而 do stuff for A 和 [=14= 的不同参数调用函数，则 I-cache 压力也更小] 代码仍然存在于 I$ 中，并且其分支预测历史仍然可用。

如果 do stuff for [type] 代码改变了 stuff for A 和 B 代码中分支的行为方式，最好复制整个循环体，因此分支的不同副本有自己的预测条目。

如果您想找出真正缓慢的地方，您将不得不分析您的代码。如果 ARM 像 x86 一样拥有硬件性能计数器，您应该能够看到哪些指令占用了很多周期。还实际计算分支预测错误、I$ 未命中和许多其他内容。

要提出任何进一步的建议，我们需要查看您的代码片段有多大，以及它们在做什么。很明显，您认为循环和切换开销使这个热门功能成为瓶颈，而不是它需要的，但您实际上并没有说 loop-inside-switch 提供了更好的性能。

除非所有 do stuff A、do stuff B 和许多 do stuff [type] 块都非常小，否则 switch 可能不是问题所在。如果它们很小，那么是的，可能值得将循环复制 N 次。

Answer 5

另一个解决方案是使用 labels as values:

void function(int type) {
    void *type_switch = &&type_break;

    switch (type) {
    case 0:
        type_switch = &&type_0;
        break;
    [...]
    case n:
        type_switch = &&type_n;
        break;
    }

    for (int i = 0; i < m; i++) {
        // do some stuff A

        goto *type_switch;

        type_0: {
            // do some stuff 0
            goto type_break;
        }
        [...]
        type_n: {
            // do some stuff n
            goto type_break;
        }
        type_break: ;

        // do some stuff B
    }
}

这个解决方案比差。

如果不启用代码优化，变量将在代码0..n.的部分每次从堆栈加载
也可以每次从栈中加载地址goto
两个额外的转到。

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

C How extract predefined huge switch from huge loop without loss performance?

c

x86

arm

c89

选项 1：利用分支预测器

选项 2：JIT 加载正确的 'stuff'