Как jvm оптимизирует код цикла?

Question

Существует метод, который может искать подстроку из текста (используйте алгоритм перебора, игнорируйте нулевой указатель)

public static int forceSearch(String text, String pattern) {
    int patternLength = pattern.length();
    int textLength = text.length();

    for (int i = 0, n = textLength - patternLength; i <= n; i++) {
        int j = 0;
        for (; j < patternLength && text.charAt(i + j) == pattern.charAt(j); j++) {
            ;
        }
        if (j == patternLength) {
            return i;
        }
    }
    return -1;
}

Странно! Используйте тот же алгоритм, но следующий код работает быстрее !!!

public static int forceSearch(String text, String pattern) {
    int patternLength = pattern.length();
    int textLength = text.length();

    char first = pattern.charAt(0);
    for (int i = 0, n = textLength - patternLength; i <= n; i++) {
        if (text.charAt(i) != first) {
            while (++i <= n && text.charAt(i) != first)
                ;
        }

        int j = 0;
        for (; j < patternLength && text.charAt(i + j) == pattern.charAt(j); j++) {
            ;
        }
        if (j == patternLength) {
            return i;
        }
    }
    return -1;
}

Я обнаружил, что второй код, очевидно, быстрее первого, если я запускаю его с помощью jvm. Однако, когда я пишу это в c и запускаю, две функции занимают почти одинаковое время. Поэтому я думаю, что причина в том, что jvm оптимизирует код цикла

if (text.charAt(i) != first) {
    while (++i <= max && text.charAt(i) != first)
        ;
}

Я прав? Если я прав, как мы должны использовать стратегию оптимизации JVM для оптимизировать наш код?

Надеюсь, кто-нибудь поможет, спасибо :)

Answer 1

Если вы ищете оптимизацию компилятора JVM в Интернете,

"разматывание петли" или "развертывание петли"

должно выпрыгнуть. Опять же, сравнительный анализ - это сложно. Вы найдете много SO ответа на тот же.

Answer 2

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

Существует множество факторов, которые могут повлиять на компиляцию JIT вашего кода. Например, изменение размера метода может повлиять на ваше встраиваемое дерево, что может означать лучшую или худшую производительность в зависимости от того, как выглядит ваш стек вызовов. Если метод будет встроен дальше вверх по стеку вызовов, он может помешать вложенным сайтам вызовов быть встроенными в один и тот же кадр. Если эти вложенные сайты вызовов являются особенно «горячими», дополнительные накладные расходы могут быть существенными. Я не говорю, что это причина здесь; Я просто указываю на то, что существует множество порогов, определяющих, как JIT упорядочивает ваш код, и причины различий в производительности не всегда очевидны.

Хорошая особенность использования JMH для тестов заключается в том, что вы можете уменьшить влияние таких изменений, явно устанавливая границы встраивания. Но вы можете использовать -XX:CompileCommand для достижения того же эффекта вручную.

Конечно, есть и другие факторы, такие как удобство кэша, которые требуют более интуитивного анализа. Учитывая, что у вашего теста , вероятно, нет особенно глубокого дерева вызовов, я склонен склоняться к поведению кэша в качестве более вероятного объяснения. Я полагаю, что ваша вторая версия работает лучше, потому что ваш компанд (первый блок pattern) обычно находится в вашем кеше L1, в то время как ваша первая версия вызывает больше оттока кеша. Если ваши входы длинные (и звучит так, как они), то это вероятное объяснение. Если нет, то причины могут быть более тонкими, например, ваша первая версия могла бы «обмануть» ЦП, чтобы использовать более агрессивную предварительную выборку из кэша, но таким образом, что на самом деле снижает производительность (по крайней мере для входов, которые вы бенчмаркинг). В любом случае, если поведение кеша нужно объяснить, то мне интересно, почему вы не видите подобной разницы в версиях C. С какими флагами оптимизации вы компилируете версию C?

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

Я повторяю: если вы хотите докопаться до сути, вам нужно заставить JIT выгрузить сборку для каждой версии (и сравнить с версиями C).

Answer 3

Это выражение if упрощает большую работу (особенно когда шаблон находится в конце входной строки.

   if (text.charAt(i) != first) {
        while (++i <= n && text.charAt(i) != first)
            ;
    }

В первой версии вы должны проверить j < patternLength для каждого i, прежде чем сравнивать первый символ.

Во второй версии вам не нужно.

Но, как ни странно, я думаю, что для небольшого ввода это не сильно отличается.

Не могли бы вы поделиться длиной предметов, которые вы использовали для сравнения?