Да, это целая статья по самому обычному switch в JDK 7. Бывает так, что накопленный материал кажется интересным и малоизвестным, а потом оказывается, что любая бабка у подъезда уже 50 лет знает об особенностях реализации switch. Но я попробую. Для затравки, предлагаю 3 вопроса:
- (Простой) Каков результат работы этого кода?
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 варианта практически одинаковы. Немного отличаются литералами.
//Вариант 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 таким кодом не проведешь, но если немного пошаманить, то небольшая разница будет заметна.
- Какова вычислительная сложность алгоритма нахождения совпадающего значения среди n case-ов (по крайней мере, в JDK 7)?
Ответы:
- 01
- Метод hashCode() возвращает одинаковое значение для всех строк первого switch. Подробности ниже.
- В зависимости от случая может быть 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. А если в этом цикле куча строковых ключей с одинаковыми хэшами, то подумайте о других способах реализации».
Автор: Fil
