Java: развернутый вручную цикл все еще быстрее, чем исходный цикл. Почему?

Рассмотрим следующие два фрагмента кода для массива длиной 2:

boolean isOK(int i) {
    for (int j = 0; j < filters.length; ++j) {
        if (!filters[j].isOK(i)) {
            return false;
        }
    }
    return true;
}

а также

boolean isOK(int i) {
     return filters[0].isOK(i) && filters[1].isOK(i);
}

Я бы предположил, что производительность этих двух частей должна быть одинаковой после достаточного прогрева.
Я проверил это с помощью JMH, как описано здесь и здесь, и заметил, что второй фрагмент работает более чем на 10% быстрее.

Вопрос: почему Java не оптимизировал мой первый фрагмент, используя базовую технику развертывания цикла?
В частности, я хотел бы понять следующее:

1. Я могу легко создать код , который является оптимальным для случаев 2 фильтров и по- прежнему может работать в случае другого количества фильтров (представьте себе простой строитель)
   return (filters.length) == 2 ? new FilterChain2(filters) : new FilterChain1(filters). Может ли JITC сделать то же самое, и если нет, то почему?
2. Может ли JITC обнаружить, что « filters.length == 2 » является наиболее частым случаем, и выдать код, который является оптимальным для этого случая после некоторого прогрева? Это должно быть почти так же оптимально, как и версия, развернутая вручную.
3. Может ли JITC обнаружить, что конкретный экземпляр используется очень часто, и затем создать код для этого конкретного экземпляра (для которого он знает, что количество фильтров всегда равно 2)?
   Обновление: получил ответ, что JITC работает только на уровне класса. Хорошо понял.

В идеале я хотел бы получить ответ от кого-то с глубоким пониманием того, как работает JITC.

Детали запуска теста:

• Пробовал на последних версиях Java 8 OpenJDK и Oracle HotSpot, результаты похожи
• Используемые флаги Java: -Xmx4g -Xms4g -server -Xbatch -XX: CICompilerCount = 2 (также были получены аналогичные результаты без необычных флагов)
• Кстати, я получаю аналогичное соотношение времени выполнения, если просто запустить его несколько миллиардов раз в цикле (не через JMH), то есть второй фрагмент всегда явно быстрее

Типичный результат теста:

Бенчмарк (filterIndex) Режим Cnt Оценка Ошибка Единицы измерения
LoopUnrollingBenchmark.runBenchmark 0 avgt 400 44.202 ± 0.224 нс /
опт

(Первая строка соответствует первому фрагменту, вторая строка - второй.

Полный код теста:

public class LoopUnrollingBenchmark {

    @State(Scope.Benchmark)
    public static class BenchmarkData {
        public Filter[] filters;
        @Param({"0", "1"})
        public int filterIndex;
        public int num;

        @Setup(Level.Invocation) //similar ratio with Level.TRIAL
        public void setUp() {
            filters = new Filter[]{new FilterChain1(), new FilterChain2()};
            num = new Random().nextInt();
        }
    }

    @Benchmark
    @Fork(warmups = 5, value = 20)
    @BenchmarkMode(Mode.AverageTime)
    @OutputTimeUnit(TimeUnit.NANOSECONDS)
    public int runBenchmark(BenchmarkData data) {
        Filter filter = data.filters[data.filterIndex];
        int sum = 0;
        int num = data.num;
        if (filter.isOK(num)) {
            ++sum;
        }
        if (filter.isOK(num + 1)) {
            ++sum;
        }
        if (filter.isOK(num - 1)) {
            ++sum;
        }
        if (filter.isOK(num * 2)) {
            ++sum;
        }
        if (filter.isOK(num * 3)) {
            ++sum;
        }
        if (filter.isOK(num * 5)) {
            ++sum;
        }
        return sum;
    }


    interface Filter {
        boolean isOK(int i);
    }

    static class Filter1 implements Filter {
        @Override
        public boolean isOK(int i) {
            return i % 3 == 1;
        }
    }

    static class Filter2 implements Filter {
        @Override
        public boolean isOK(int i) {
            return i % 7 == 3;
        }
    }

    static class FilterChain1 implements Filter {
        final Filter[] filters = createLeafFilters();

        @Override
        public boolean isOK(int i) {
            for (int j = 0; j < filters.length; ++j) {
                if (!filters[j].isOK(i)) {
                    return false;
                }
            }
            return true;
        }
    }

    static class FilterChain2 implements Filter {
        final Filter[] filters = createLeafFilters();

        @Override
        public boolean isOK(int i) {
            return filters[0].isOK(i) && filters[1].isOK(i);
        }
    }

    private static Filter[] createLeafFilters() {
        Filter[] filters = new Filter[2];
        filters[0] = new Filter1();
        filters[1] = new Filter2();
        return filters;
    }

    public static void main(String[] args) throws Exception {
        org.openjdk.jmh.Main.main(args);
    }
}

TL; DR Основная причина различий в производительности здесь не связана с развертыванием цикла. Это скорее спекуляция типа и встроенные кэши .

Развертывание стратегий

Фактически, в терминологии HotSpot такие циклы считаются подсчитанными , и в некоторых случаях JVM может их развернуть. Не в вашем случае, хотя.

HotSpot имеет две стратегии разворачивания цикла: 1) развернуть максимально, то есть полностью удалить цикл; или 2) склеить несколько последовательных итераций вместе.

Максимальная развертка может быть выполнена, только если известно точное количество итераций .

  if (!cl->has_exact_trip_count()) {
    // Trip count is not exact.
    return false;
  }

В вашем случае, однако, функция может вернуться рано после первой итерации.

Частичное развертывание может быть применено, но следующее условие прерывает развертывание:

  // Don't unroll if the next round of unrolling would push us
  // over the expected trip count of the loop.  One is subtracted
  // from the expected trip count because the pre-loop normally
  // executes 1 iteration.
  if (UnrollLimitForProfileCheck > 0 &&
      cl->profile_trip_cnt() != COUNT_UNKNOWN &&
      future_unroll_ct        > UnrollLimitForProfileCheck &&
      (float)future_unroll_ct > cl->profile_trip_cnt() - 1.0) {
    return false;
  }

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

Тип спекуляции

В вашей развернутой версии есть два разных invokeinterfaceбайт-кода. Эти сайты имеют два разных типа профиля. Первый получатель всегда Filter1, а второй получатель всегда Filter2. Таким образом, у вас в основном два мономорфных сайта вызовов, и HotSpot может идеально встроить оба вызова - так называемый «встроенный кэш», который в данном случае имеет коэффициент совпадения 100%.

В цикле есть только один invokeinterfaceбайт-код, и собирается только один профиль типа. HotSpot JVM видит, что filters[j].isOK()вызывается 86% раз с Filter1приемником и 14% раз с Filter2приемником. Это будет биморфный вызов. К счастью, HotSpot также может спекулировать биморфными вызовами. Обе цели ставятся условной ветвью. Однако в этом случае коэффициент попадания будет не более 86%, а производительность будет страдать от соответствующих ошибочно предсказанных ветвей на уровне архитектуры.

Все будет еще хуже, если у вас есть 3 или более разных фильтров. В этом случае isOK()будет мегаморфный вызов, который HotSpot не может встроить вообще. Таким образом, скомпилированный код будет содержать настоящий интерфейсный вызов, который оказывает большее влияние на производительность.

Подробнее о умозрительном встраивании в статью «Черная магия (Java) метода рассылки» .

Вывод

Чтобы встроить виртуальные / интерфейсные вызовы, HotSpot JVM собирает профили типов для каждого байт-кода вызова. Если в цикле есть виртуальный вызов, для вызова будет только один тип профиля, независимо от того, развернут ли цикл или нет.

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

Представленный цикл, скорее всего, подпадает под категорию «неисчисляемых» циклов, которые представляют собой циклы, для которых количество итераций не может быть определено ни во время компиляции, ни во время выполнения. Не только из-за аргумента @Andreas о размере массива, но и из-за случайно условных break(это было в вашем тесте, когда я писал этот пост).

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

Из этого следует, что ваше предположение не соответствует тому, что вы выполняли своего рода «ручное развертывание» цикла. Вы рассматриваете это как базовую технику развертывания цикла для преобразования итерации по массиву с условным разрывом в &&цепочечное логическое выражение. Я бы посчитал это довольно частным случаем и был бы удивлен, обнаружив, что оптимизатор горячих точек выполняет сложный рефакторинг на лету. Здесь они обсуждают, что на самом деле может сделать, возможно, эта ссылка интересна.

Это будет ближе отражать механику современного развертывания и, возможно, еще далеко от того, как будет выглядеть развернутый машинный код:

if (! filters[0].isOK(i))
{
   return false;
} 
if(! filters[1].isOK(i))
{
   return false;
}
return true;

Вы пришли к выводу, что поскольку один фрагмент кода работает быстрее, чем другой, цикл не развернулся. Даже если это произойдет, вы все равно увидите разницу во время выполнения из-за того, что вы сравниваете разные реализации.

Если вы хотите получить больше уверенности, есть jitwatch анализатор / визуализатор фактических операций JIT включая машинный код (GitHub) (презентация слайдов) . Если в конце концов есть что-то, что я мог бы увидеть, я бы больше доверял своим глазам, чем мнению о том, что JIT может или не может делать вообще, поскольку каждый случай имеет свою специфику. Здесь они беспокоятся о том, что трудно прийти к общим утверждениям для конкретных случаев, касающихся JIT, и предоставляют некоторые интересные ссылки.

Поскольку ваша цель - минимальное время выполнения, a && b && c ...форма, вероятно, самая эффективная, если вы не хотите зависеть от надежды на развертывание цикла, по крайней мере, более эффективная, чем что-либо еще представленное. Но вы не можете иметь это в общем виде. С функциональной композицией java.util.Function снова огромные издержки (каждая функция - это класс, каждый вызов - виртуальный метод, который требует диспетчеризации). Возможно, в таком сценарии может иметь смысл подорвать уровень языка и сгенерировать пользовательский байт-код во время выполнения. С другой стороны, &&логика также требует ветвления на уровне байтового кода и может быть эквивалентна if / return (который также не может быть сгенерирован без издержек).