Переключение кажется медленнее, чем если

Мне было любопытно, что скорость на switch, полагая, что она была "очень" быстрой, но у меня есть тестовый пример, который, кажется, показывает один переключатель примерно так же быстро, как около 4 if тестов, когда Я ожидал (нет веской причины), чтобы это было так же быстро, как 1 тест. Вот два метода, которые я написал, чтобы сравнить switch с if:

public static int useSwitch(int i) {
    switch (i) {
        case 1: return 2;
        case 2: return 3;
        case 3: return 4;
        case 4: return 5;
        case 5: return 6;
        case 6: return 7;
        default: return 0;
    }
}

public static int useIf(int i) {
    if (i == 1) return 2;
    if (i == 2) return 3;
    if (i == 3) return 4;
    if (i == 4) return 5;
    if (i == 5) return 6;
    if (i == 6) return 7;
    return 0;
}

Здесь мой тестовый код:

long x = 0;
for (int i = 0; i < 999999; i++)
    x += useIf(i % 7); // I use "x" so calls won't get optimized out

И еще один идентичный цикл для useSwitch()

На моей машине эти петли занимают примерно то же самое время, что и стало неожиданностью.
Я пришел к числу ifs как "4", потому что среднее значение задало диапазон ввода (я думаю).
Если я уменьшу количество логических опций, версия if будет заметно быстрее.

Мой вопрос:

Неужели это switch на самом деле не так быстро или это "несправедливый" тест каким-то образом?

Ответ 1

Это несправедливое сравнение в некоторой степени. Большая часть времени процессора будет потрачена на обработку операции по модулю: i % 7. Modulo даже на самых последних процессорах очень медленный и, вероятно, занимает 20 раз больше, чем реализация if() или switch(), которую вы пытаетесь выполнить.

Кроме того, существует два разных способа оптимизации оптимизаций операторов. Один из них - поисковая таблица, которая используется в последовательных случаях, таких как тот, который вы указали. Другим способом является использование деревьев разделов поиска, где это необходимо. Это происходит, когда случаи разрежены, например, в следующем примере:

switch (someInt) {
    case 0:  ... break;
    case 10:  ... break;
    case 102:  ... break;
    case 6543:  ... break;
    case 19303:  ... break;
    case 19305:  ... break;
    // and so forth...
}

Большинство компиляторов будут использовать развернутое дерево разделов, чтобы найти правильный случай, который на длинных коммутаторах дает очень хорошие средние и худшие скачки, необходимые для достижения правильного. Полученный псевдокод будет примерно таким:

if (someInt >= 6543) {
    if (someInt >= 19303) {
        // continue tree search, etc.
    }
    else if (someInt==6543) {}
}
else if (someInt >= 0) {
    if (someInt >= 10) {
        // continue tree search, etc.
    }
    else if (someInt == 0) {} 
}
else {
    // default case handler...
}

Это не очень помогает с 6-8 случаями, как показано здесь, но если у вас есть переключатель с возможно более 50 случаями, тогда это может быть очень полезно. Линейный поиск имел бы O (n) (50 наихудших условий, 25 avg), в то время как версия дерева разделов была бы близка к sqrt (n) (худшие условия 8-9, 5-7 avg, в зависимости от выбора компилятора).

Ответ 2

Коммутатор должен быть быстрее, достаточно взглянуть на байт-код

   TABLESWITCH
      1: L1
      2: L2
      3: L3
      4: L4
      5: L5
      6: L6

чтобы убедиться, что это специальная операция. В реальной жизни не может быть никакой разницы из-за оптимизации JVM. Но если мы запускаем ваш код с помощью -Xint (только для режима interepret), разница должна быть очевидной, на моем ПК это от 63 до 93 (мс) в пользу коммутатора.

Ответ 3

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

Итак, я не могу дать вам ответ, но могу вам сказать, что если вы хотите еще больше уточнить свой тест, вы всегда можете дать ему ввод 7. Это позволит пройти все тесты до тех пор, пока возвращая ответ, и если переключатель оптимизирован, он даст вам лучшие результаты, если он будет похож на if-else, он будет иметь похожие результаты. Просто не жуйте код 7, чтобы компилятор не знал его раньше времени, используйте что-то вроде parseint, чтобы получить его из строки.

Ответ 4

Поскольку у вас есть код, который может быть или не быть устранен на основе того, насколько интеллектуальным является JIT, вы, возможно, определили, что операторы if легче устранить, чем коммутатор. Это не удивительно, так как многие утверждения if, скорее всего, будут устранены, например. утверждения и проверки отладки.