Ответ 1
Разница заключается в том, что lookupswitch использует таблицу с ключами и метками, но таблицаwitch использует таблицу только с метками.
При выполнении tablewitch значение int поверх стека непосредственно используется в качестве индекса в таблице, чтобы захватить пункт перехода и немедленно выполнить скачок. Весь процесс поиска + перехода - это операция O (1), что означает, что он быстро вспыхивает.
При выполнении lookupswitch значение int поверх стека сравнивается с клавишами в таблице до тех пор, пока не будет найдено совпадение, а затем пункт назначения перехода рядом с этим ключом используется для выполнения Прыгать. Поскольку таблица lookupswitch всегда должна сортироваться, так что keyX < keyY для каждого X < Y, весь процесс поиска + перехода является операцией O (log n), поскольку поиск ключа выполняется с использованием алгоритма бинарного поиска (нет необходимости сравнивать значение int со всеми возможными ключами, чтобы найти совпадение или определить, что ни один из ключей не соответствует). O (log n) несколько медленнее, чем O (1), но все же все в порядке, так как многие известные алгоритмы O (log n), и они обычно считаются быстрыми; даже O (n) или O (n * log n) по-прежнему считается довольно хорошим алгоритмом (медленные/плохие алгоритмы имеют O (n ^ 2), O (n ^ 3) или даже хуже).
Решение о том, какую инструкцию использовать компилятор, основывается на том, насколько компактен оператор switch, например
switch (inputValue) {
case 1: // ...
case 2: // ...
case 3: // ...
default: // ...
}
Переключатель выше идеально компактен, он не имеет числовых "отверстий". Компилятор создаст такой стиль таблицы:
tableswitch 1 3
OneLabel
TwoLabel
ThreeLabel
default: DefaultLabel
Псевдокод со страницы Jasmin объясняет это довольно хорошо:
int val = pop(); // pop an int from the stack
if (val < low || val > high) { // if its less than <low> or greater than <high>,
pc += default; // branch to default
} else { // otherwise
pc += table[val - low]; // branch to entry in table
}
Этот код довольно четко описывает, как работает такой табличный интерфейс. val inputValue, low будет 1 (самое низкое значение в коммутаторе) и high будет 3 (самое высокое значение в коммутаторе).
Даже с некоторыми отверстиями переключатель может быть компактным, например
switch (inputValue) {
case 1: // ...
case 3: // ...
case 4: // ...
case 5: // ...
default: // ...
}
Переключатель выше "почти компактный", он имеет только одно отверстие. Компилятор может сгенерировать следующую команду:
tableswitch 1 6
OneLabel
FakeTwoLabel
ThreeLabel
FourLabel
FiveLabel
default: DefaultLabel
; <...code left out...>
FakeTwoLabel:
DefaultLabel:
; default code
Как вы можете видеть, компилятор должен добавить фальшивый футляр для 2, FakeTwoLabel. Поскольку 2 не является реальным значением коммутатора, FakeTwoLabel на самом деле является меткой, которая изменяет поток кода точно там, где находится случай по умолчанию, так как значение 2 должно фактически выполнять случай по умолчанию.
Таким образом, коммутатор не должен быть совершенно компактным для компилятора для создания столов-столов, но он должен быть, по крайней мере, достаточно близок к компактности. Теперь рассмотрим следующий переключатель:
switch (inputValue) {
case 1: // ...
case 10: // ...
case 100: // ...
case 1000: // ...
default: // ...
}
Этот переключатель нигде не близок к компактности, он имеет более чем сто раз больше отверстий, чем значений. Можно было бы назвать это запасным переключателем. Компилятор должен был бы генерировать почти тысячи фальшивых случаев, чтобы выразить этот переключатель в виде таблицы. Результатом будет огромная таблица, резко увеличивающая размер файла класса. Это непрактично. Вместо этого он будет генерировать lookupswitch:
lookupswitch
1 : Label1
10 : Label10
100 : Label100
1000 : Label1000
default : DefaultLabel
В этой таблице содержится всего 5 записей, а не более тысячи. Таблица имеет 4 действительных значения, O (log 4) равно 2 (log здесь находится на базе 2 BTW, а не на базе 10, поскольку компьютер работает с двоичными числами). Это означает, что VM не более двух сравнений, чтобы найти метку для inputValue или прийти к выводу, что значение не находится в таблице, и поэтому значение по умолчанию должно быть выполнено. Даже если в таблице было 100 записей, для получения правильной метки или принятия перехода на метку по умолчанию потребуется не более 7 сравнений VM (а 7 сравнений намного меньше 100 сравнений, не так ли?).
Итак, это глупость, что эти две инструкции взаимозаменяемы или что причина для двух инструкций имеет исторические причины. Существует две инструкции для двух разных ситуаций: одна для коммутаторов с компактными значениями (для максимальной скорости) и одна для переключателей с запасными значениями (не максимальная скорость, но все же хорошая скорость и очень компактное представление таблицы, независимо от всех числовых отверстий).