Разница между упакованным переключателем и разреженным переключателем Dalvik Opcode

Question

Я хочу знать разницу между упакованным переключателем и разреженным выключателем в Dalvik. Пожалуйста, если вы можете дать примеры. Объяснение, предоставленное Google, мне неясно.

упакованное переключение редкий переключатель

Спасибо.

Answer 1

Это звучит как будто packed-switch эквивалентен Java tableswitch, а также sparse-switch к lookupswitch.

А packed-switch использует простую таблицу прыжков, проиндексированную формой low + n, куда low является самой низкой тестовой стоимостью среди case ярлыки и n вход в switch. Анкет Значения в каждом индексе представляют собой смещения байт -кодов для каждого case. Анкет Поиск правильного адреса прыжка является операцией постоянного времени.

А sparse-switch использует отсортированный список пар клавишных значений, где каждый ключ является тестовым значением из case Метка, а значения - это смещения прыжков. Поиск правильной цели прыжков для lookupswitch Требуется бинарный поиск на ключе, так что это операция логарифмического времени.

Компилятор выберет, что использовать. Если ключи, как правило, сгруппированы или упакованный внимательно вместе, тогда packed-switch (или, с точки зрения Java, tableswitch) может быть излучен эффективно. Но если ключи редкий, и диапазон значений (high - low + 1) большой, тогда использование таблицы прыжков потребует большого блока байт -кода, так как все значения в этом диапазоне должны существовать в таблице прыжков независимо от того, есть ли соответствующие case этикетка. В этих сценариях компилятор излучит sparse-switch (lookupswitch).

Интересно, что инженеры Dalvik решили назвать эти Opcodes таким образом, что описывает ключевые распределения, для которых их следует использовать, тогда как инженеры Java выбирают имена, которые описывают концептуальные структуры данных, которые похожи операнды Bytecode.

Давайте посмотрим на некоторые примеры. Рассмотрим следующий код Java, который производит tableswitch (и при преобразовании в Далвик, packed-switch):

static String packedSwitch(final int n) {
    switch (n) {
        case 5:
            return "Five";
        case 3:
            return "Three";
        case 1:
            return "One";
        default:
            return "Other";
    }
}

Концептуально, полезная нагрузка для packed-switch Opcode будет выглядеть примерно так:

Как видите, это довольно компактно. Три из пяти слотов указывают на фактические case цели, с оставшимися двумя прыжками в default цель. Но что, если наши тестовые значения были более распространены?

static String sparseSwitch(final int n) {
    switch (n) {
        case 500:
            return "Five Hundred";
        case 300:
            return "Three Hundred";
        case 100:
            return "One Hundred";
        default:
            return "Other";
    }
}

Если компилятор попытался излучать это как packed-switch, полезная нагрузка будет выглядеть примерно так:

Обратите внимание, как на самом деле указывают только три из нескольких сотен слотов case Метки из исходного кода. Остальные есть просто заполнить таблицу прыжков. Не очень эффективно пространство, не так ли? Вот почему компилятор излучает sparse-switch, который имеет гораздо более компактный след ByteCode для этого конкретного примера:

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