12

我是一个相当称职的 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 像素的图像，您会期望看到很多开销吗？我试图做一些测试，但我的结果到处都是，因为系统（移动设备）有各种各样的东西在后台运行，可能会扭曲结果。

另一种选择是为每种模式设置一个单独的方法，每个模式都有自己的四个循环。这显然会引入冗余代码，但效率是这里的游戏名称。

提前致谢！

加夫

4

16 回答 16

19

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..
}
于 2009-05-29T18:30:29.547 回答
10

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

于 2009-05-29T18:21:17.163 回答
6

Switch 语句尽可能高效。它们被编译成一个跳转表。事实上，这就是为什么 switch 如此有限的原因：你只能编写一个 switch，你可以为它编译一个基于固定值的跳转表。

于 2009-05-29T18:20:50.703 回答
5

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

于 2009-05-29T18:20:34.683 回答
3

与 if/else 的等效项相比，switch/case 非常快：它通常实现为跳转表。然而，它仍然是有代价的。

在优化事物时：

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

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

于 2009-05-29T19:31:02.420 回答
2

为了效率起见，您最好移到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和标签作为值：在开关中找到正确的标签，然后每次都跳转到它。我认为它应该节省更多的周期。

于 2009-05-29T20:17:32.420 回答
1

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

jmp {基地址}+switchcasenum

于 2009-05-29T18:21:14.760 回答
1

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

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

于 2009-05-29T18:21:47.847 回答
1

除了 Jim 的建议，尝试交换循环的顺序。循环交换是否适合案例 1 需要测试，但我怀疑它是。您几乎总是希望您的 x 坐标在您的内部循环中以提高分页性能，因为这会导致您的函数在每次迭代时更倾向于保持在相同的通用内存区域中。并且资源有限的移动设备可能具有足够低的内存来强调这种差异。

于 2009-05-29T19:24:59.903 回答
1

很抱歉碰到这个线程，但在我看来，这个开关与问题相差甚远。

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

于 2010-09-08T03:31:28.127 回答
0

取决于芯片和编译器以及代码的细节，而且……但这通常会以跳转表的形式实现，应该很快。

顺便说一句——理解这种事情是一个很好的论据，可以在你职业生涯的某个阶段花几个星期学习一些组装......

于 2009-05-29T18:21:58.020 回答
0

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

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

于 2009-05-29T18:22:21.263 回答
0

但效率是这里的游戏名称。

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

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

这样您最终会遇到以下呼叫：

computeWeight[mode](pixel);

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

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

于 2009-05-29T20:10:02.607 回答
0

许多优点已经给出。我能想到的唯一补充就是将最常见的情况移到交换机中，将最不频繁的情况下移。

因此，如果案例 4 比案例 1 更频繁地发生，它应该在它之上：

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

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

干杯！

于 2009-05-29T21:11:50.143 回答
0

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

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

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

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

于 2012-04-23T15:34:01.193 回答
0

关于内部循环... 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 语句非常不友好。对于 < 4 个元素，我会选择 if-then-else 并确保最常见的情况排在最前面。如果第一个条件涵盖了 90% 的情况，那么您基本上已经击中了本垒打。同样，如果其他一些条件 < 1%，则将其放在最后。

于 2019-02-25T02:50:48.513 回答