Время выполнения switch в Java

Со времен господства языка C я пребывал в уверенности, что операция switch при благоприятных обстоятельствах выполняется за время, не зависящее от количества ветвей (cases). Оказалось, что бывают и неприятные исключения.



Благоприятные обстоятельства — это подряд идущие значения, соответствующие ветвям:

    public void switching( int l )
    {
      switch( l )
      {
        case 0: m0(); break;
        case 1: m1(); break;
        case 2: m2(); break;
        case 3: m3(); break;
        case 4: m4(); break;
        case 5: m5(); break;
      }
    }

В этом случае их можно сделать индексами массива переходов, вот выборка элемента массива и дает постоянное время при любом количестве ветвей.

Каково же было моё удивление, когда тесты показали, что в Java время выполнения switch пропорционально количеству ветвей! Такое может происходить, если switch реализован как последовательность условий:

        if( l == 0 ) m0(); else
        if( l == 1 ) m1(); else
        if( l == 2 ) m2(); else
        if( l == 3 ) m3(); else
        if( l == 4 ) m4(); else
        if( l == 5 ) m5();

Но в JVM есть специальная инструкция tableswitch, то есть возможность генерации эффективного байт-кода есть. Значит, проблема глубже — в реализации самой JVM.

Подтвердил гипотезу ответ на форуме Sun.

Эффективная реализация вроде бы есть только в серверной JVM для Java 5 на Solaris.

Можете проверить свою JVM: switchtest.zip

Если во втором столбце значения растут примерно как в третьем — время выполнения switсh зависит от количества меток:

E:>java -cp . SwitchTest
num switch if empty
1 125 171 63
2 125 141 46
3 125 110 47
4 140 110 31
5 125 125 31
6 140 141 31
7 157 156 47
8 172 156 31
9 188 203 47
10 250 187 47
11 219 203 31
12 187 203 32
13 218 235 47
14 234 218 47
15 235 250 31
16 265 235 47
17 250 265 47
18 266 250 47
19 297 281 31
20 297 281 31
21 297 282 31
22 282 297 31
23 328 297 31
24 297 312 32
25 328 297 47
26 312 344 31
27 344 344 31
28 328 328 31
29 344 343 32
30 359 359 32
31 328 375 31
32 375 359 32
33 375 359 31
34 391 391 46
35 375 407 31
36 391 421 32
37 422 421 32
38 406 406 31
39 406 422 31
40 438 406 47
41 453 438 31
42 437 438 31
43 453 438 31
44 469 469 31
45 500 453 31
46 469 484 32
47 453 469 31
48 547 500 31
49 516 640 32

10.06.2007  Метки:   Рубрики: Разработка, Языки

2 комментария

  1. Nikos - 31.08.2007

    Ужоснах.

    У меня всегда было чувство, что Java сделана сильно через жопу. Теперь я это точно знаю

  2. allex - 11.09.2007

    Это ж не проблема дизайна языка, а особенность конкретной реализации компилятора и виртуальной машины. Если бы эта особенность доставляла заметные неудобства — давно бы уж исправили.

    А мне просто на глаза попалось, это побочный результат другого исследования.

Написать комментарий