Разница между LookupSwitch JVM и TableSwitch?

У меня есть некоторые трудности, чтобы понять LookUpSwitch и TableSwitch в байт-коде Java.

Если я правильно понимаю, LookUpSwitch и TableSwitch соответствуютswitch утверждение источника Java? Почему один оператор JAVA генерирует 2 разных байт-кода?

Жасмин документация каждого:

LookupSwitch tableswitch

Ответы на вопрос(4)

When exactly does javac 1.8.0_45 compile switch to either one?

Чтобы решить, когда использовать какой, вы могли бы использоватьjavac алгоритм выбора в качестве основы.

Мы знаем, что источникjavac находится вlangtools Сделки РЕПО.

Тогда мы grep:

hg grep -i tableswitch

и первый результатlangtools / SRC / доля / классов / ком / ВС / инструменты / Javac / JVM / Gen.java:

// 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;

Куда:

hi: maximum case value lo: minimum case value

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

Я не понимаю почемуlookup_time_cost = nlabels и неlog(nlabels), так какtableswitch может быть сделано в O (log (n)) с двоичным поиском.

Бонус: реализации C ++ также делают аналогичный выбор между таблицей переходов O (1) и двоичным поиском O (long (n)):Преимущество переключения оператора if-else

 31 авг. 2016 г., 09:25
Время O (log (n)) никогда не должно быть лучше, всегда есть несколько мультипликаторов, так что c1 * n & lt; c2 * log (n) может произойти для n & lt; java выбирает сканирование и c3 * 1 & lt; c2 * log (n) для n & gt; = java выбирает индекс. Но индекс может быть пустой тратой пространства.
 19 авг. 2015 г., 02:56
+1, потому что это помогло мне понять, как реализовать инструкции переключения в моем собственном компиляторе языка JVM

Спецификация виртуальной машины Java опишите разницу. & quot; Команда переключения таблиц используется, когда случаи переключения могут быть эффективно представлены в виде индексов в таблице целевых смещений. & quot; Спецификация описывает более подробную информацию.

что это в основном исторически из-за некоторой специфической привязки байт-кода Java к подчеркиванию машинного кода (например, собственного процессора Sun).

Переключатель таблиц по сути представляет собой вычисленный переход, где пункт назначения берется из таблицы поиска. Напротив, для переключателя поиска требуется сравнение каждого значения, в основном элементов таблицы итераций, пока не будет найдено соответствующее значение.

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

Решение Вопроса

a table with keys and labelsТем не менее, настольный переключатель используетa table with labels only.

При выполненииtableswitchзначение int на вершине стека напрямую используется в качестве индекса в таблице, чтобы получить назначение перехода и немедленно выполнить его. Весь процесс поиска + прыжок являетсяO(1) operationэто означает, что это быстро.

При выполненииlookupswitchзначение int в верхней части стека сравнивается с ключами в таблице до тех пор, пока не будет найдено совпадение, а затем для выполнения перехода используется пункт назначения рядом с этим ключом. Так как таблица переключения всегдаmust be sorted так что keyX & lt; keyY для каждого X & lt; Y, весь поиск + прыжок процессO(log n) operation в качестве ключа будет выполняться поиск с использованием алгоритма двоичного поиска (нет необходимости сравнивать значение int со всеми возможными ключами, чтобы найти совпадение или определить, что ни один из ключей не совпадает). O (log n) несколько медленнее, чем O (1), но все еще в порядке, поскольку многие известные алгоритмы - это O (log n), и их обычно считают быстрыми; даже O (n) или O (n * log n) все еще считается довольно хорошим алгоритмом (медленные / плохие алгоритмы имеют O (n ^ 2), O (n ^ 3) или даже хуже).

Решение о том, какую инструкцию использовать, принимается компилятором на основе того, какcompact оператор переключения, например,

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

Как видите, компилятор должен добавитьfake case for 2, FakeTwoLabel, Поскольку 2 не является реальным значением переключателя, FakeTwoLabel фактически является меткой, которая изменяет поток кода именно там, где находится регистр по умолчанию, поскольку значение 2 должно фактически выполнять регистр по умолчанию.

Таким образом, переключатель не должен быть идеально компактным, чтобы компилятор мог создать табличный переключатель, однако он должен, по крайней мере, быть очень близок к компактности. Теперь рассмотрим следующий переключатель:

switch (inputValue) {
  case 1:    // ...
  case 10:   // ...
  case 100:  // ...
  case 1000: // ...
  default:   // ...
}

Этот переключатель далеко не компактен, он имеет более чем в сто раз большеholes than values, Можно было бы назвать это запасным выключателем. Компилятор должен будет сгенерироватьalmost thousand fake cases чтобы выразить этот переключатель как табличный переключатель. Результатом будет огромная таблица, резко увеличивающая размер файла классов. Это не практично. Вместо этого он сгенерирует переключатель поиска:

lookupswitch
    1       : Label1
    10      : Label10
    100     : Label100
    1000    : Label1000
    default : DefaultLabel

В этой таблице всего 5 записей, а не более тысячи. Таблица имеет 4 действительных значения, O (log 4) равно 2 (здесь log - это лог для базы 2 BTW, а не для 10, поскольку компьютер работает с двоичными числами). Это означает, что виртуальной машине требуется не более двух сравнений, чтобы найти метку для inputValue или прийти к выводу, что значение отсутствует в таблице и, следовательно, должно выполняться значение по умолчанию. Даже если таблица содержит 100 записей, виртуальной машине потребуется не более 7 сравнений, чтобы найти правильную метку или решить перейти к метке по умолчанию (а 7 сравнений намного меньше 100 сравнений, как вы думаете?).

Поэтому бессмысленно, что эти две инструкции являются взаимозаменяемыми или что причина для двух инструкций имеет исторические причины. Существуют две инструкции для двух различных типов ситуаций, одна для переключателей с компактными значениями (для максимальной скорости) и одна для переключателей с резервными значениями (не для максимальной скорости, но все еще с хорошей скоростью и очень компактным представлением таблицы независимо от всех числовых отверстий).

 06 дек. 2015 г., 04:16
просто хотел сказать, чтоtableswitch не O (1), по крайней мере, на практике, он ведет себя линейно согласно некоторым тестам. Посмотреть здесьgithub.com/frostwire/frostwire-jlibtorrent/pull/…
 24 июн. 2015 г., 18:29
Точнее, это javac 8 дает вес 3 для сложности времени и 1 для сложности пространства:stackoverflow.com/a/31032054/895245
 31 окт. 2012 г., 01:54
@ FauxFaux: Спасибо за информацию, я исправил ответ соответственно.
 31 окт. 2012 г., 01:24
n*log(n) больше чемn для любогоn больше, чем основание журнала, которое, как я полагаю, обычно будет значительно меньше, чем размерn который мы оцениваем; то естьO(n) будет рассматриватьсяbetter чемO(n log n).
 22 сент. 2015 г., 22:53
«Журнал - это журнал для базы 2 BTW, а не для базы 10, поскольку компьютер работает с двоичными числами» - Я не думаю, что система двоичных чисел играет здесь какую-либо роль. Просто искомая коллекция каждый раз уменьшается вдвое, и, следовательно, основание журнала равно 2.

Ваш ответ на вопрос