Разница между упакованным коммутатором и разреженным коммутатором dalvik opcode

Звучит так, как будто packed-switch эквивалентно tableswitch в Java, а 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 решили назвать эти коды операций таким образом, чтобы описывать распределения ключей, для которых они должны использоваться, в то время как инженеры Java выбрали имена, которые описывают концептуальные структуры данных, похожие на операнды байт-кода.

Давайте посмотрим на некоторые примеры. Рассмотрим следующий код Java, который создаст tableswitch (и, при преобразовании в Dalvik, 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 будет выглядеть примерно так:

Как видите, он довольно компактный. Три из пяти слотов указывают на фактические цели 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, который имеет гораздо более компактный размер байт-кода для этого конкретного примера:

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