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

  • Tutorial
Да, это целая статья по самому обычному 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. А если в этом цикле куча строковых ключей с одинаковыми хэшами, то подумайте о других способах реализации».
Поделиться публикацией

Похожие публикации

Комментарии 19
    +10
    >>Думаю, теперь понятно, почему после найденного соответствия, выполнение продолжается до первого встретившегося break

    А это не было понятно изначально? вроде бы мы видим работу алгоритма по стандарту и только.
    Интересна только оптимизация на 3-ке, которую вы разбираете ниже.
      0
      Это комментарий не к стандарту, а к реализации. Понятно уж, что чтобы узнать поведение, не нужно копаться так глубоко.
        +5
        Это комментарий не к стандарту, а к реализации. Понятно уж, что чтобы узнать поведение, не нужно копаться так глубоко.
        А в какой реализации switch работает не по стандарту? Тут не только стандарт, а вообще ожидаемое поведение от свича по его определению. Чтобы «узнать поведение» надо знать не больше чем что такое вообще switch во всех таких (скажем, C-подобных) его реализациях. Что именно могло вызвать вопрос то? Вот этот вывод из статьи:
        выполнение продолжается до первого встретившегося break.
        ведь заведомо известное ожидаемое поведение, не?
          +1
          Полагаю, имелось в виду: «Понятно, каким именно способом стандарт реализован в байткоде».
            0
            Именно. Но, как я написал ниже, это всего лишь небольшое замечание по реализации, а не подведение итогов.
            0
            Возможно, вам показалось, что это полученный вывод? Нет, это очевидная информация, написанная мимоходом. Раздел не об этом.
              0
              Ну ок. Я в общем-то догадался, что не очевидные вещи вы пытались через анализ байт-кода пояснить. Просто вопрос в начале статьи
              Каков результат работы этого кода?
              подразумевает как минимум какую-то неоднозначность поведения или подвох или загадку.
                0
                Да, понял вас. Согласен. Первый пример привел для разминки, чтобы его потом поковырять.
        0
        в JLS написано как switch for string работает, декомпилятор не обязателен :) но всё равно интересно и убедительно
          0
          JLS разве описывает способ реализации switch? JVM да.
          –1
          Если второй случай и так обрабатывается JIT-ом, то зачем мне сакральное, но бесполезное знание?
            0
            Это философский вопрос… Например в олимпиадном программировании на JIT полагаться не всегда можно.
              0
              Вы не думайте, что благодаря JIT, tableswitch и lookupswitch одинаковы по производительности. JIT, очень старается оптимизировать, (в большинстве случаев лучше человека, и нам нет нужды вникать в эти тонкости) но только там, где это возможно. Например, разница будет явно видна с последовательными и сильно разбросанными ключами. Поэтому да, эти знания представляют только научный интерес.
                0
                Научный это когда есть наука. А здесь просто деталь реализации конкретного продукта конкретной компанией. При том деталь бесполезная на практике, потому что чтобы она стала полезной:

                1) Весь остальной код должен быть идеальным, т.к. нет смысла оптимизировать lookupswitch-и, если у вас алгоритм кривой
                2) Он все еще работает медленно и нуждается в оптимизации
                3) Оптимизация lookupswitch-ей даст хоть какой-то прирост

                Не вижу себе реальной практической ситуации, когда эти 3 условия могут встретиться в одной точке.
                  +2
                  Кто-то довольствуется информацией как это работает, кто-то разбирает и проверяет, несмотря на то, что это вряд ли пригодится, ему просто интересно.
              –1
              Оператор switch в Java? Не, не слышал…
                0
                Ребята, если у вас в цикле, который должен выполняться сто миллионов раз в секунду, 1000 case-ов с последовательными ключами кроме нескольких, то обрабатывайте эти несколько ключей вне switch.

                Хороший совет. Но вот если после обработки какого-нибудь из этих нескольких ключей нет break… что же, goto внутрь второго switch писать? :)
                  0
                  У вас вряд ли возникнет такая ситуация на практике. Это очень плохой код :) Но если возникнет, то тут уж по усмотрению, я просто оценил скорость нахождения совпадения.
                    0
                    Думаю, что обработку далёких ключей можно внести в default — тогда структурность почти не нарушится.

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                Самое читаемое