C 中 switch 语句的开销

Question

我是一位相当有能力的 Java 程序员，但对 C 非常陌生。我正在尝试优化具有四种操作模式的例程。

我循环遍历图像中的所有像素，并根据传递的“模式”计算新的像素值。

我的问题是关于两个嵌套 for 循环中 switch 语句的开销。 我对有关基本 C 语句、数学和逻辑运算的相对效率的任何文档链接感兴趣。

代码如下：

for (x = 0; x < width; x++) {
        for (y = 0; y < height; y++) {
             switch (mode)                  /* select the type of calculation */
             {
                case 0:
                weight = dCentre / maxDistanceEdge;
                case 1: 
                    weight = (float)x/width;             
                    break;
                case 2: 
                    weight = (float)y/height;
                    break;
                case 3: 
                    weight = dBottomLeft / maxDistanceCorner;
                    break;
                case 4: 
                    weight = dTopRight / maxDistanceCorner;
                    break;
                default: 
                weight = 1;
                break;
            }
             // Calculate the new pixel value given the weight
             ...
            }             

    }

如果这是超过 5000 x 5000 像素的图像，您会期望看到很多开销吗？ 我尝试做一些测试，但我的结果到处都是，因为系统（移动设备）在后台运行着各种可能会扭曲结果的东西。

另一种选择是为每种模式提供单独的方法，每种模式都有自己的四个循环。 这显然会引入冗余代码，但效率才是这里的关键。

提前致谢！

加夫

Answer 1

Switch 语句编译为连续值的跳转表和稀疏值的一堆 if-else 语句。 无论如何，如果您关心性能，则不希望在图像处理的内部循环中使用 switch 语句。 您想要如下所示。

另请注意，我将权重计算移出了内部循环（并交换了情况 2 的循环以实现此目的）。 这种将内容移出内循环的思维方式将为您带来您想要的 C 性能。

switch (mode)                  /* select the type of calculation */
{
case 0:
    weight = dCentre / maxDistanceEdge;
    for (x = 0; x < width; x++) {
        for (y = 0; y < height; y++) {
             // Calculate the new pixel value given the weight
             ...
        }
    }
    break;
case 1:
    for (x = 0; x < width; x++) {
        weight = (float)x/width;
        for (y = 0; y < height; y++) {
             // Calculate the new pixel value given the weight
             ...
        }
    }
    break;
case 2:
    // note - the loops have been swapped to get the weight calc out of the inner loop
    for (y = 0; y < height; y++) {
        weight = (float)y/height;
        for (x = 0; x < width; x++) {
             // Calculate the new pixel value given the weight
             ...
        }
    }
    break;
case 3:
    weight = dBottomLeft / maxDistanceCorner;
    for (x = 0; x < width; x++) {
        for (y = 0; y < height; y++) {
             // Calculate the new pixel value given the weight
             ...
        }
    }
    break;
case 4:
    weight = dTopRight / maxDistanceCorner;
    for (x = 0; x < width; x++) {
        for (y = 0; y < height; y++) {
             // Calculate the new pixel value given the weight
             ...
        }
    }
    break;
default:
    weight = 1;
    for (x = 0; x < width; x++) {
        for (y = 0; y < height; y++) {
             // Calculate the new pixel value given the weight
             ...
        }
    }
    break;

// etc..
}

Answer 2

如果效率比代码大小更重要，那么您应该创建冗余例程。 case 语句是您可以在 C 中执行的开销较低的操作之一，但它不是零 - 它必须根据模式进行分支，因此需要时间。 如果您确实想要最大性能，请将案例移出循环，即使以重复循环为代价。

Answer 3

Switch 语句尽可能高效。 它们被编译成跳转表。 事实上，这就是 switch 受到限制的原因：您只能编写一个可以根据固定值编译跳转表的 switch。

Answer 4

与您在循环中进行的数学运算相比，切换的开销可能是最小的。 话虽如此，唯一确定的方法是为两种不同的方法创建不同的版本，并为其计时。

Answer 5

与 if/else 的等效项相比，switch/case 速度极快：它通常作为跳转表实现。 然而它仍然有成本。

当您优化事物时：

1）尝试在行上循环，而不是在列上循环（切换x和y“for”循环），由于缓存内存管理，一种解决方案可能比另一种解决方案快得多。

2）用（预先计算的）逆的乘法替换所有除法将为您带来显着的增益，并且可能会带来可接受的精度损失。

Answer 6

为了提高效率，您最好将 switch 移到循环之外。

我会使用这样的函数指针：

double fun0(void) { return dCentre/maxDistanceEdge; }
double fun1(void) { return (float)x/width; }
/* and so on ... */

double (*fun)(void);

switch (mode)                  /* select the type of calculation */
{
    case 0: fun = fun0;
            break;
    case 1: fun = fun1;
            break;
    case 2: fun = fun2;
            break;
    case 3: fun = fun3;
            break;
    case 4: fun = fun3;
            break;
    default : fun = fun_default;
            break;
}

for (x = 0; x < width; x++) {
        for (y = 0; y < height; y++) {
             weight = fun();
             // Calculate the new pixel value given the weight
             ...
        }
}

它增加了函数调用开销，但它不应该太大，因为您不向函数传递任何参数。 我认为这是性能和可读性之间的良好权衡。

编辑：如果您使用GCC，要摆脱函数调用，您可以使用goto和标签作为值： 在开关中找到正确的标签，然后每次都跳转到它。 我认为它应该可以节省更多的周期。

Answer 7

开关不应该产生任何显着的开销，它们被编译成低端的一种指针数组，那么这是有效的情况：

jmp {baseaddress}+switchcasenum

Answer 8

这可能取决于 CPU 的分支预测器有多好，以及编译器如何生成切换代码。 对于如此少量的情况，它可能会生成决策树，在这种情况下，正常的 CPU 分支预测应该能够消除大部分开销。 如果它生成一个切换表，情况可能会更糟……

也就是说，找出答案的最佳方法是分析它并查看。

Answer 9

除了吉姆的建议之外，还可以尝试交换循环的顺序。 循环交换是否适合情况 1 需要测试，但我怀疑确实如此。 您几乎总是希望您的 x 坐标位于内部循环中，以提高分页性能，因为这会导致您的函数在每次迭代时更倾向于保留在相同的通用内存区域中。 资源有限的移动设备可能具有足够低的内存，因此这种差异将被强调。

Answer 10

很抱歉打扰这个帖子，但在我看来，这个开关离问题还很远。

在这种情况下，效率的真正问题是部门。 在我看来，除法运算的所有分母都是常数（宽度、高度、最大值...），并且这些在整个图像过程中不会改变。 如果我的猜测是正确的，那么这些都是简单的变量，可以根据加载的图像进行更改，以便在运行时可以使用任何大小的图像，现在这允许加载任何图像大小，但这也意味着编译器无法优化它们如果它们被声明为“const”，它就可以进行更简单的乘法运算。 我的建议是预先计算这些常数的倒数并相乘。 据我记得，乘法运算大约需要 10 个时钟周期，而除法大约需要 70 个时钟周期。这意味着每个像素增加了 60 个周期，对于上述 5000x5000，预计速度会增加 1.5 秒。 1 GHz CPU。

Answer 11

取决于芯片和编译器以及代码的细节，并且......但这通常会作为跳转表实现，这应该非常快。

顺便说一句——理解这种事情是在你职业生涯的某个阶段花几周时间学习一些汇编的一个很好的论据......

Answer 12

使用开关对于速度和编程时间来说可能更好。 您正在编写更少的冗余代码，并且可能不需要新的堆栈框架。

开关非常高效，以至于它们可以用于非常奇怪和令人困惑的黑魔法。

Answer 13

但效率才是这里的关键。

迭代图像缓冲区以计算新的像素值听起来像是一个典型的令人尴尬的并行问题，从这个意义上说，您可能需要考虑将一些工作推入工作线程，这应该比微优化更显着地加快您的操作速度例如 switch/case 问题。

此外，您可以从函数指针数组中调用函数指针，而不是每次都执行分支指令，其中索引用作模式标识符。

因此，您最终会得到如下调用：

computeWeight[mode](pixel);

对于 5000x5000 像素，还可以通过针对一系列像素（而不是单个像素）调用函数来减少函数调用开销。

您还可以使用循环展开和通过引用/指针传递参数，以便进一步优化。

Answer 14

已经给出了许多优点。 我唯一能想到的就是将开关中最常见的情况向上移动，将最不常见的情况向下移动。

因此，如果情况 4 比情况 1 发生得更频繁，则它应该位于其之上：

switch (mode) {
    case 4:
        // ..
        break;
    case 1:
        // ..
        break;
}

太糟糕了，您没有使用 c++，因为这样可以用多态性来替换 switch 语句。

干杯！

Answer 15

在这个线程中有很多创造性的建议，不需要编写 5 个单独的函数。

除非您从文件或键入的输入中读取“模式”，否则可以在编译时确定计算方法。 作为一般规则，您不希望将计算从编译时移动到运行时。

无论哪种方式，代码都会更容易阅读，并且不会有人对您是否打算在第一种情况下放入break语句感到困惑。

此外，当您在周围代码中遇到错误时，您不必查找枚举是否设置为错误的值。

Answer 16

关于内部循环... 0->var 最好是 var->0，因为 var-- 会触发零标志（6502 天）。 这种方法还意味着“宽度”被加载到 x 中并且可以被忘记，“高度”也是如此。 另外，内存中的像素通常是左->右、上->下，所以肯定有 x 作为你的内循环。

for (y = height; y--;) {
    for (x = width; x--;) {
         weight = fun();
         // Calculate the new pixel value given the weight
         ...
    }
}

另外...非常重要的是你的 switch 语句只有 2 个使用 x 或 y 的情况。 其余的都是常数。

 switch (mode)                  /* select the type of calculation */
 {
     case 0:
        weight = dCentre / maxDistanceEdge;
        break;
     //case 1: 
     //  weight = (float)x/width;             
     // break;
     //case 2: 
     //     weight = (float)y/height;
     //     break;
     case 3: 
          weight = dBottomLeft / maxDistanceCorner;
          break;
      case 4: 
           weight = dTopRight / maxDistanceCorner;
           break;
      default: 
           weight = 1;
           break;
 }

所以基本上除非模式 1 或 2 权重是在循环之前计算的。

... Y loop code here

    if (mode == 2) { weight = (float)y/height; } // calc only once per Y loop

    ... X loop here

        if (mode == 1) { weight = (float)x/width; } // after this all cases have filled weight
        calc_pixel_using_weight(weight);

我发现如果数据稀疏， switch 语句非常不友善。 对于< 我会选择 if-then-else 的 4 个元素，并确保最常见的情况位于顶部。 如果第一个条件适用于 90% 的情况，那么您基本上就打出了全垒打。 同样，如果某个其他条件< 1% 把它放在最后。