Тонкости оператора switch

Да, это целая статья по самому обычному switch в JDK 7. Бывает так, что накопленный материал кажется интересным и малоизвестным, а потом оказывается, что любая бабка у подъезда уже 50 лет знает об особенностях реализации switch. Но я попробую. Для затравки, предлагаю 3 вопроса:

1. (Простой) Каков результат работы этого кода?
   

   switch(5){
   default: System.out.print(0);
   case 1: System.out.print(1); break;
   case 4: System.out.print(4);
   case 2: System.out.print(2);
   }

   
   
2. Следующие 2 варианта практически одинаковы. Немного отличаются литералами.
   

   //Вариант 1 switch("BBBBBB"){ case "AaAaAa": break; case "AaAaBB": break; case "AaBBAa": break; case "AaBBBB": break; case "BBAaAa": break; case "BBAaBB": break; case "BBBBAa": break; case "BBBBBB": break; }

   //Вариант 2 switch("BBBBBB_8"){ case "AaAaAa_1": break; case "AaAaBB_2": break; case "AaBBAa_3": break; case "AaBBBB_4": break; case "BBAaAa_5": break; case "BBAaBB_6": break; case "BBBBAa_7": break; case "BBBBBB_8": break; }

   Почему первый switch выполняется в несколько раз медленнее, по крайней мере, с отключенным JIT (-Djava.compiler=NONE)? Сами проверьте в цикле! JIT таким кодом не проведешь, но если немного пошаманить, то небольшая разница будет заметна.
3. Какова вычислительная сложность алгоритма нахождения совпадающего значения среди n case-ов (по крайней мере, в JDK 7)?
   

Ответы:

1. 01
2. Метод hashCode() возвращает одинаковое значение для всех строк первого switch. Подробности ниже.
3. В зависимости от случая может быть O(1), O(log n) и даже достигать O(n).

Давайте разбираться. Case-значения, для краткости, я буду называть ключами.

TableSwitch

Возьмем пример из первой задачи. Скомпилируем его и дизассемблируем полученный байт-код.

javap -c Main.class

         0: iconst_5                          // Засовываем 5 в стек
         1: tableswitch   { // 1 to 4         // Забираем 3 из стека и ищем в таблице
                       1: 39                  // 39, 56, 32, 49 – адресные метки переходов
                       2: 56
                       3: 32
                       4: 49
                 default: 32
            }

        32: getstatic     #27                 // Field java/lang/System.out:Ljava/io/PrintStream;
        35: iconst_0
        36: invokevirtual #33                 // Method java/io/PrintStream.print:(I)V

        39: getstatic     #27                 // Field java/lang/System.out:Ljava/io/PrintStream;
        42: iconst_1
        43: invokevirtual #33                 // Method java/io/PrintStream.print:(I)V
        46: goto          63                  // break

        49: getstatic     #27                 // Field java/lang/System.out:Ljava/io/PrintStream;
        52: iconst_4
        53: invokevirtual #33                 // Method java/io/PrintStream.print:(I)V

        56: getstatic     #27                 // Field java/lang/System.out:Ljava/io/PrintStream;
        59: iconst_2
        60: invokevirtual #33                 // Method java/io/PrintStream.print:(I)V

        63: return

Нас особенно интересует инструкция с меткой 1. Она означает, что компилятор создал таблицу (массив), содержащий адреса переходов для всех значений ключей от наименьшего до наибольшего, без исключений. Алгоритм выполнения switch примерно такой (псевдокод):

if (val<low || val>high){
     jump default;
}else{
     jump table[val - low];
}

В нашем случае: low==1, high==4, table=={39, 56, 32, 49}. Так как в таблице должны быть последовательно все ключи от low до high, то компилятору пришлось добавить ключ 3 и задать для него то же поведение, что и для default.

Начиная с инструкции 32, код всех case и default в порядке их расположения в исходном коде. Грубо говоря, здесь компилятор генерирует сплошной код обработчиков ключей. Думаю, теперь понятно, почему после найденного соответствия, выполнение продолжается до первого встретившегося break.

LookupSwitch

Появляется резонный вопрос: а что если значения ключей сильно разрежены? Если у нас их всего два: 1 и 1000000, то крайне неразумно создавать массив с миллионом элементов. Заменим в нашем примере ключ 4 на 10, этого будет достаточно (если вдруг нет – увеличьте). Смотрим байт-код (байт-код обработчиков остался практически тем же, поэтому не приведен):

         1: lookupswitch  { // 3
                       1: 43
                       2: 60
                      10: 53
                 default: 36
            }

Здесь тоже задается таблица, но уже для пар: ключ — метка перехода. В спецификации JVM сказано, что хотя поиск может быть и линейным, ключи обязательно должны быть отсортированы для возможности более быстрого поиска, хотя сам способ поиска не оговаривается. Возможно, в каких-нибудь реализациях используется линейный поиск. Это первый известный мне случай (хотя и теоретический) со сложностью switch O(n). Далее мы увидим другой, более осязаемый.

Реальные пацаны и девчата спрашивают: как компилятор решает что выбрать – tableswitch или lookupswitch? А самые реальные скачивают исходники OpenJDK (учтите, в других реализациях JDK способ выбора может отличаться) и изучают метод visitSwitch класса com.sun.tools.javac.jvm.Gen.java в openjdk/langtools/src/share/classes.

            // Determine whether to issue a tableswitch or a lookupswitch
            // instruction.
            long table_space_cost = 4 + ((long) hi - lo + 1); // words
            long table_time_cost = 3; // comparisons
            long lookup_space_cost = 3 + 2 * (long) nlabels;
            long lookup_time_cost = nlabels;
            int opcode =
                nlabels > 0 &&
                table_space_cost + 3 * table_time_cost <=
                lookup_space_cost + 3 * lookup_time_cost
                ?
                tableswitch : lookupswitch;

table_space_cost – в этот размер входит количество всех значений диапазона, плюс по одному значению для lo, hi, default_address и маркер выбранного switch-метода (tableswitch).
table_time_cost – 3 операции: проверка вхождения в диапазон (на минимум и максимум) и извлечение адресной метки из таблицы.
lookup_space_cost – 2 значения на каждую пару ключ-адрес, плюс по значению для размера таблицы, default_address, и маркер выбранного switch-метода (lookupswitch).
lookup_time_cost – предполагается худший случай – линейный поиск.

А сам алгоритм, как видите, нехитрый. Магическое число 3 («И эти люди запрещают нам ковыряться в носу» (с)), скорее всего, эмпирическое.

Сравнение строк

«String.hashCode может запросто иметь коллизии, String.equals слишком медленен, может быть, строки интернируются?» – так думал я, пока не изучил байт-код.

switch(""){
case "AA": break;
case "BB": break;
}

       0: ldc           #27                 // String
       2: dup
       3: astore_0
       4: invokevirtual #29                 // Method java/lang/String.hashCode:()I
       7: lookupswitch  { // 2
                  2080: 32
                  2112: 44
               default: 73
          }

      32: aload_0
      33: ldc           #35                 // String AA
      35: invokevirtual #37                 // Method java/lang/String.equals:(Ljava/lang/Object;)Z
      38: ifne          56
      41: goto          73

      44: aload_0
      45: ldc           #41                 // String BB
      47: invokevirtual #37                 // Method java/lang/String.equals:(Ljava/lang/Object;)Z
      50: ifne          66
      53: goto          73

      56: getstatic     #43                 // Field java/lang/System.out:Ljava/io/PrintStream;
      59: iconst_1
      60: invokevirtual #49                 // Method java/io/PrintStream.println:(I)V
      63: goto          73

      66: getstatic     #43                 // Field java/lang/System.out:Ljava/io/PrintStream;
      69: iconst_2
      70: invokevirtual #49                 // Method java/io/PrintStream.println:(I)V

      73: return

То есть, на этапе компиляции вычисляется хэш-код всех ключей. Для строк всегда выполняется lookupSwitch, даже если хэши последовательны. При выполнении вычисляется хэш-код условного выражения и именно он сравнивается с хэшами-ключами. При совпадении строки еще и сравниваются (адреса 32–53) методом String.equals() для предотвращения возможной коллизии. И, в случае успеха, переход к выполнению соответствующего выражения (56–70).

А если у нас несколько ключей с одинаковыми хэшами?

switch(""){
case "Aa": break;
case "BB": break;
}

        7: lookupswitch  { // 1
                   2112: 24
                default: 62
           }
       
       24: aload_0
       25: ldc           #35                 // String Aa
       27: invokevirtual #37                 // Method java/lang/String.equals:(Ljava/lang/Object;)Z
       30: ifne          45
       33: aload_0
       34: ldc           #41                 // String BB
       36: invokevirtual #37                 // Method java/lang/String.equals:(Ljava/lang/Object;)Z
       39: ifne          55
       42: goto          62

       45: getstatic     #43                 // Field java/lang/System.out:Ljava/io/PrintStream;
       48: iconst_1
       49: invokevirtual #49                 // Method java/io/PrintStream.println:(I)V
       52: goto          62
       55: getstatic     #43                 // Field java/lang/System.out:Ljava/io/PrintStream;
       58: iconst_2
       59: invokevirtual #49                 // Method java/io/PrintStream.println:(I)V

       62: return

Тогда эти ключи объединяются под одним хэш-ключом в lookupswitch, и, при совпадении ключа, происходит перебор всех строк с этим хэшем и их сравнение с помощью String.equals(). Пример из 2-го вопроса выполняет аж 8 сравнений. Вот вам и второй случай со сложностью O(n).

Выводы

Если бы не JIT, то можно было бы порассуждать об оптимизации switch. Но мне не удалось подобрать хорошего примера, в котором tableswitch был бы заметно быстрее lookupswitch (с включенным JIT). Ну, разве что такой:
1. Допустим, у нас N ключей со значениями от 1 до N. В этом случае, будет использоваться tableswitch.
2. Те же самые ключи, но плюс еще один, со значением много большим N. В этом случае, будет использоваться lookupswitch.
(С отключенным JIT все понятно, разница ощутима.)
С JIT никакой разницы. Возможно, он разбивает все ключи на несколько диапазонов и поступает с ними аналогично tableswitch. Однако, начиная с N=721, у меня произошло резкое падение производительности второго примера.

В завершение, напрашиваются только совсем дикие советы, считайте их шуткой: «Ребята, если у вас в цикле, который должен выполняться сто миллионов раз в секунду, 1000 case-ов с последовательными ключами кроме нескольких, то обрабатывайте эти несколько ключей вне switch. А если в этом цикле куча строковых ключей с одинаковыми хэшами, то подумайте о других способах реализации».