在C switch语句的开销
https://stackoverflow.com/questions/927403
-
06-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我是一个相当称职的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像素的图片？我试着做一些测试，但我的结果是所有的地方作为系统（移动设备）有可能会扭曲结果后台运行的各种东西。
另一种选择是有一个单独的方法对于每个模式，每个都有其自己的四个环。这显然引入冗余代码，但效率是这里的游戏的名称。
提前感谢！
GAV株系
解决方案
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..
}
其他提示
如果效率比代码大小更重要，然后是你应该创建冗余程序。 case语句的开销更低的东西，你可以在C做一个，但它不是零 - 这将具有基于模式的分支，所以它需要时间。如果你真的想最大的性能，得到的情况下跳出循环，甚至在重复循环的成本。
切换语句是关于高效，因为它们都不可能。他们编译成一个跳转表。事实上，这就是为什么开关是有限的，因为它是：你只能写上您的开关可以的编制基于固定值跳转表
。，交换机的开销可能会是最小的。具有说，可以肯定的唯一方式是为两种不同的方法创建不同版本，和时间他们。
交换机/情况极快与用的if / else等价的：它是作为一个跳转表通常被实现。然而，它仍具有成本。
尽管在优化方面：
1）尝试遍历行，没有结束列（开关x和y“for”循环），一种解决方案可以是难以置信的快于其他，由于高速缓冲存储器管理。
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
...
}
}
它增加了函数调用的开销，但因为你没有传递到PARAMS函数应该不会太大。我觉得这是性能和可读性之间的良好平衡。
编辑：如果您使用GCC，摆脱函数调用，您可以使用goto和的标签的值：找到开关内右侧的标签，然后就跳转到它每一次。我认为应该节省一些更多的周期。
开关不应该产生任何显著开销，它们被编译成一种在低端指针阵列的，那么它的有效的情况下：
的jmp {baseaddress} + switchcasenum
这很可能取决于你的编译器有多好你的CPU的分支预测是，如何生成用于开关的代码。对于这样的少数情况下，它可能会产生一个决策树，在这种情况下，正常CPU的分支预测应该能够去除大部分的开销。如果它产生切换桌上的东西可能是一个有点差...
这是说，要找出最好的办法就是来分析一下，看看。
除了吉姆的建议，尝试更换循环的顺序。无论是循环交换是理想的情况下，1将需要测试，但我怀疑它是。你几乎总是希望你的X你内心的循环内部协调，以改善寻呼性能，因为这会导致你的函数有更好的倾向留在相同的一般存储区中的每个迭代。并用limitted资源的移动设备可能具有足够低RAM，这种差异将被强调。
对不起撞击这个线程，但它似乎对我来说，开关远离问题。
在这种情况下，效率的真正的问题是分裂。在我看来，所有的除法运算的分母是常数（宽度，高度，最大...），这些不会以图像的过程中发生变化。如果我的猜测是正确的，那么这些都是可以改变基于加载，使任何大小的图像可以在运行时使用的图像上的简单变量，现在这允许任何图像尺寸被加载，但是这也意味着，编译器无法对它们进行优化成更简单的乘法运算，其被声明为“常量”是可以做的。我的建议是预先计算这些常数的倒数和繁殖。据我可以记得，该乘法运算大约需要10个时钟周期，其中，作为分割约需70这是每像素60个循环的增加，并且与上述5000x5000，这是1.5秒的估计速度增加上一个1 GHz的CPU。
取决于芯片和编译器和代码的细节，并...但是这往往会被实现为跳转表，这应该是非常快。
BTW--了解这种东西是花了几个星期的学习在某些时候某些装配在你的职业生涯一个很好的说法...
使用的开关可能是两者的速度和时间程序员更好。你让更少的冗余代码，它可能不会需要一个新的堆栈帧。
交换机是如此有效，以至于它们可用于非常奇怪和混乱魔法
但效率是这里的游戏的名称。
循环访问，以便计算新的象素值的图像缓冲区听起来像一个典型的令人尴尬的并行问题，在这个意义上，你可能要考虑推动一些工作纳入工作线程，这应该加快你的操作不是更值得注意的是微的优化，如交换机/壳体的担忧。
另外，而不是做分支指令每次，可以从函数指针阵列，其中该索引用作您的模式标识符调用一个函数指针。
这样就结束了呼叫，例如：
computeWeight[mode](pixel);
使用5000x5000像素，该函数调用开销也可以通过调用函数的范围的像素的，而不是单独的像素减小。
您还可以通过参考/使用指针循环展开和参数传递中，为了该进一步优化。
很多好点的都已经给出。我唯一能想到的加入到这个东西，是在交换机和最不频繁的倒拉升最常见的情况。
因此，如果壳体4发生往往比壳体1，它应该是它上面：
switch (mode) {
case 4:
// ..
break;
case 1:
// ..
break;
}
您没有使用C ++，因为这样的话switch语句可以用多态性进行更换。太糟糕了
干杯！
有不具有写5个独立的功能在该线程的方式很多创造性的建议。
除非你从文件或从键入输入读取“模式”可在编译时被确定的计算方法。作为一般规则，你不希望从编译时移动计算运行时间。
无论哪种方式的代码会更容易阅读，没有人会困惑，你是否打算把在break语句在第一种情况下或没有。
此外，当您在周围的代码得到的错误，你将不必仰望如果枚举被设置为错误的值或没有。
关于内环... 0->变量被做得更好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％，把它放在最后。
