切换似乎比如果慢

Question

我对速度感到好奇switch,认为它"非常"快,但是我有一个测试用例,似乎显示单个开关大约和4个if测试一样快,当我预期(没有坚实的理由)它和1次测试一样快.这里有两种方法我写的比较switch有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;
}

这是我的测试代码:

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

和另一个相同的循环 useSwitch()

在我的机器上,这些循环大约需要相同的时间才能完成,这是一个惊喜.
我得到ifs的数量为"4",因为这是给定输入范围的平均值(我认为).
如果我减少逻辑选项的数量,if版本明显更快.

我的问题是:

难道switch实际上不是那么快,或者这是在某些方面的"不公平"的考验？

Answer 1

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

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

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

大多数编译器将使用展开的分区树来查找正确的大小写,在长开关上可以提供非常好的平均值和最坏情况下的跳转以达到正确的大小.生成的伪代码将是这样的:

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...
}

对于这里显示的6-8个案例,它并没有多大帮助,但是如果你有一个可能有50多个案例的开关那么它可能真的很有帮助.线性搜索将具有O(n)(最差50个条件,25个平均值),而分区树版本将接近sqrt(n)(8-9条件最差,5-7个平均值,取决于编译器选择).

Answer 2

切换应该更快,它足以查看字节码

   TABLESWITCH
      1: L1
      2: L2
      3: L3
      4: L4
      5: L5
      6: L6

看到这是一项特殊的操作.在现实生活中,由于JVM优化,可能没有区别.但是如果我们使用-Xint(仅限互联网模式)运行你的代码,那么差异应该是显而易见的,在我的PC上它是63到93(ms)支持切换.