切换似乎比如果慢 [英] Switch seems slower than if

问题描述

我对开关的速度感到好奇，认为它非常快，但我有一个测试用例似乎显示单个开关是关于快到大约4 如果测试，当我预期（没有可靠的理由）时，它就像1次测试一样快。这是我写的两种方法，比较开关与如果：

  public static int useSwitch（int i）{
 switch（i）{
 case 1：return 2; 
案例2：返回3; 
案例3：返回4; 
案例4：返回5; 
案例5：返回6; 
案例6：返回7; 
默认值：返回0; 
} 
} 
 
 public static int useIf（int i）{
 if（i == 1）return 2; 
如果（i == 2）返回3; 
如果（i == 3）返回4; 
如果（i == 4）返回5; 
如果（i == 5）返回6; 
如果（i == 6）返回7; 
返回0; 
} 
  

这是我的测试代码：

  long x = 0; 
 for（int i = 0; i< 999999; i ++）
 x + = useIf（i％7）; //我使用x因此调用不会被优化掉
  

另一个相同的循环 useSwitch（）

在我的机器上，这些循环需要大致相同的时间才能完成，这是一个惊喜。

我把ifs的数量变为4，因为这是给定输入范围的平均值（我认为）。

如果我减少了数量逻辑选项，如果版本明显更快。

我的问题是：

这是切换实际上不是那么快，或者这是一个以某种方式不公平测试？

解决方案

这在某种程度上是不公平的比较。大部分CPU时间将用于处理模运算： i％7 。甚至在最新的最大CPU上模数也非常慢，并且执行时间可能比你试图进行基准测试的if（）或switch（）实现的时间长20倍。

此外，有两种不同的方式可以优化switch语句。一个是查找表，用于顺序情况，就像你提出的那样。另一种方法是在适当的地方使用搜索分区树。在案例稀疏时会发生这种情况，例如以下示例：

  switch（someInt） {
案例0：......休息; 
案例10：......休息; 
案例102：......休息; 
案例6543：......休息; 
案例19303：......休息; 
案例19305：......休息; 
 //等等...... 
} 
  

大多数编译器都会使用一个展开的分区树，以找到正确的情况，在长开关上提供非常好的平均和最坏情况的跳跃，以击中正确的。生成的伪代码将是这样的：

  if（someInt> = 6543）{
 if（ someInt> = 19303）{
 //继续树搜索等等
} 
否则if（someInt == 6543）{} 
} 
 else if（ someInt> = 0）{
 if（someInt> = 10）{
 //继续树搜索等等
} 
 else if（someInt == 0）{ } 
} 
 else {
 //默认案例处理程序... 
} 
  

如图所示，只有6-8个案例并没有多大帮助，但是如果你有一个可能超过50个案例的开关那么它真的很有帮助。线性搜索将具有O（n）（50个条件最差，25个平均值），而分区树版本将接近sqrt（n）（8-9条件最差，5-7个平均值，取决于编译器选择）。 / p>

I was curious as to the speed on switch, believing that it was "very" fast, but I have a test case that seems to show a single switch is about as fast as about 4 if tests, when I expected (no solid reason) it to be as fast as 1 test. Here's the two methods I wrote to compare switch with if:

public static int useSwitch(int i) {
    switch (i) {
        case 1: return 2;
        case 2: return 3;
        case 3: return 4;
        case 4: return 5;
        case 5: return 6;
        case 6: return 7;
        default: return 0;
    }
}

public static int useIf(int i) {
    if (i == 1) return 2;
    if (i == 2) return 3;
    if (i == 3) return 4;
    if (i == 4) return 5;
    if (i == 5) return 6;
    if (i == 6) return 7;
    return 0;
}

Here's my testing code:

long x = 0;
for (int i = 0; i < 999999; i++)
    x += useIf(i % 7); // I use "x" so calls won't get optimized out

And another identical loop for useSwitch()

On my machine these loops take about the same time to complete, which was a surprise.
I arrived at the number of ifs as "4", because that's the average given the input range (I think).
If I reduce the number of logic options, the if version is noticeably faster.

My question is:

Is it that switch actually isn't that fast, or is this an "unfair" test in some way?

解决方案

This is an unfair comparison to some extent. Most of the CPU time will be spent processing the modulo operation: i % 7. Modulo even on latest greatest CPUs is extremely slow and probably takes 20x longer to execute than either the if() or switch() implementations you're trying to benchmark.

Furthermore, there are two different ways that switch statements can be optimized. One is by lookup table, which is used in sequential cases like the one you've put forth. The other way is by using search partition trees, where appropriate. This happens when the cases are sparse, such as in the following example:

switch (someInt) {
    case 0:  ... break;
    case 10:  ... break;
    case 102:  ... break;
    case 6543:  ... break;
    case 19303:  ... break;
    case 19305:  ... break;
    // and so forth...
}

Most compilers will use an unrolled partition tree to find the correct case, which on long switches gives very good avg and worst-case jumps needed to hit the right one. The resulting pseudo-code would be something like this:

if (someInt >= 6543) {
    if (someInt >= 19303) {
        // continue tree search, etc.
    }
    else if (someInt==6543) {}
}
else if (someInt >= 0) {
    if (someInt >= 10) {
        // continue tree search, etc.
    }
    else if (someInt == 0) {} 
}
else {
    // default case handler...
}

It doesn't really help much with just 6-8 cases as shown here, but if you had a switch with perhaps 50+ cases then it can be really helpful. A linear search would have O(n) (50 conditions worst, 25 avg), while the partition tree version would be close to sqrt(n) (8-9 conditions worst, 5-7 avg, depending on compiler choices).

这篇关于切换似乎比如果慢的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！