Java: ręcznie rozwijana pętla jest nadal szybsza niż oryginalna. Dlaczego?

Rozważ następujące dwa fragmenty kodu w tablicy o długości 2:

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

i

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

Zakładam, że wydajność tych dwóch utworów powinna być podobna po wystarczającym rozgrzaniu.
Sprawdziłem to przy użyciu frameworku JMH, jak opisano np. Tu i tutaj, i zauważyłem, że drugi fragment kodu jest o ponad 10% szybszy.

Pytanie: dlaczego Java nie zoptymalizował mojego pierwszego fragmentu za pomocą podstawowej techniki rozwijania pętli?
W szczególności chciałbym zrozumieć następujące kwestie:

1. Mogę łatwo produkować kod, który jest optymalny dla przypadków 2 filtrów i nadal może pracować w przypadku innej liczby filtrów (wyobrazić sobie prosty konstruktor)
   return (filters.length) == 2 ? new FilterChain2(filters) : new FilterChain1(filters). Czy JITC może zrobić to samo, a jeśli nie, to dlaczego?
2. Czy JITC może wykryć, że „ filter.length == 2 ” jest najczęstszym przypadkiem i wygenerować kod, który jest optymalny dla tego przypadku po pewnym rozgrzaniu? Powinno to być prawie tak optymalne, jak wersja rozwijana ręcznie.
3. Czy JITC może wykryć, że dana instancja jest używana bardzo często, a następnie wygenerować kod dla tej konkretnej instancji (dla której wie, że liczba filtrów wynosi zawsze 2)?
   Aktualizacja: otrzymałem odpowiedź, że JITC działa tylko na poziomie klasy. Ok, rozumiem.

Idealnie chciałbym otrzymać odpowiedź od kogoś, kto ma głębokie zrozumienie działania JITC.

Szczegóły przebiegu testowego:

• Wypróbowane w najnowszych wersjach Java 8 OpenJDK i Oracle HotSpot, wyniki są podobne
• Użyte flagi Java: -Xmx4g -Xms4g -server -Xbatch -XX: CICompilerCount = 2 (uzyskał podobne wyniki również bez fantazyjnych flag)
• Nawiasem mówiąc, otrzymuję podobny współczynnik czasu działania, jeśli po prostu uruchomię go kilka miliardów razy w pętli (nie przez JMH), tj. Drugi fragment jest zawsze wyraźnie szybszy

Typowe wyniki testu porównawczego:

Benchmark (filterIndex) Tryb Cnt Wynik Błąd Jednostki
LoopUnrollingBenchmark.runBenchmark 0 avgt 400 44,202 ± 0,224 ns / op
LoopUnrollingBenchmark.runBenchmark 1 avgt 400 38,477 ± 0,063 ns / op

(Pierwszy wiersz odpowiada pierwszemu fragmentowi, drugi wiersz - drugiemu.

Pełny kod testu:

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 Główny powód różnicy wydajności nie jest związany z rozwijaniem pętli. To raczej spekulacja typu i wbudowane pamięci podręczne .

Rozwijanie strategii

W terminologii HotSpot takie pętle są traktowane jako zliczane , aw niektórych przypadkach JVM może je rozwinąć. Ale nie w twoim przypadku.

HotSpot ma dwie strategie rozwijania pętli: 1) rozwijaj maksymalnie, tzn. Całkowicie usuń pętlę; lub 2) skleić ze sobą kilka kolejnych iteracji.

Maksymalne rozwinięcie można wykonać tylko wtedy, gdy znana jest dokładna liczba iteracji .

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

W twoim przypadku funkcja może jednak wrócić wcześniej po pierwszej iteracji.

Prawdopodobnie można zastosować częściowe rozwinięcie, ale następujący warunek przerywa rozwijanie:

  // 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;
  }

Ponieważ w twoim przypadku oczekiwana liczba podróży jest mniejsza niż 2, HotSpot zakłada, że ​​nie warto rozwijać nawet dwóch iteracji. Zauważ, że pierwsza iteracja jest i tak wyodrębniana do wstępnej pętli ( optymalizacja obierania pętli ), więc rozwijanie się nie jest tutaj naprawdę korzystne.

Typ spekulacji

W twojej nie rozwiniętej wersji istnieją dwa różne invokeinterfacekody bajtowe. Witryny te mają dwa różne typy profili. Pierwszy odbiornik jest zawsze Filter1, a drugi odbiornik jest zawsze Filter2. Tak więc w zasadzie masz dwie monomorficzne witryny wywołań, a HotSpot może idealnie wbudować oba połączenia - tak zwaną „wbudowaną pamięć podręczną”, która w tym przypadku ma współczynnik trafień 100%.

W pętli jest tylko jeden invokeinterfacekod bajtowy i zbierany jest tylko jeden profil typu. HotSpot JVM widzi, że filters[j].isOK()jest nazywany 86% razy z Filter1odbiornikiem i 14% razy z Filter2odbiornikiem. To będzie wezwanie bimorficzne. Na szczęście HotSpot może również spekulacyjnie wbudowywać wywołania bimorficzne. Obejmuje oba cele za pomocą gałęzi warunkowej. Jednak w tym przypadku współczynnik trafień wyniesie najwyżej 86%, a wydajność będzie ucierpieć z powodu odpowiednio nieprzewidzianych gałęzi na poziomie architektury.

Będzie jeszcze gorzej, jeśli masz 3 lub więcej różnych filtrów. W takim przypadku isOK()będzie to rozmowa megamorficzna, której HotSpot nie może w ogóle wstawić. Tak więc skompilowany kod będzie zawierał prawdziwe wywołanie interfejsu, które ma większy wpływ na wydajność.

Więcej o wkładaniu spekulacyjnym w artykule The Black Magic of (Java) Method Dispatch .

Wniosek

W celu wbudowanych wywołań wirtualnych / interfejsowych, HotSpot JVM zbiera profile typów dla każdego bajtu kodu wywołania. Jeśli w pętli jest wirtualne połączenie, będzie tylko jeden profil typu dla połączenia, bez względu na to, czy pętla jest rozwinięta, czy nie.

Aby jak najlepiej wykorzystać wirtualne optymalizacje połączeń, należy ręcznie podzielić pętlę, przede wszystkim w celu podziału profili typów. Jak dotąd HotSpot nie może tego robić automatycznie.

Prezentowana pętla prawdopodobnie mieści się w kategorii „niezliczonych” pętli, które są pętlami, dla których liczby iteracji nie można ustalić ani w czasie kompilacji, ani w czasie wykonywania. Nie tylko z powodu argumentu @Andreas o wielkości tablicy, ale również z powodu losowego warunkowego break(który był w teście porównawczym, kiedy pisałem ten post).

Najnowocześniejsze kompilatory nie optymalizują ich agresywnie, ponieważ rozwijanie niezliczonych pętli często obejmuje duplikowanie również warunku wyjścia pętli, co poprawia wydajność w czasie wykonywania tylko wtedy, gdy kolejne optymalizacje kompilatora mogą zoptymalizować rozwijany kod. Zobacz ten artykuł z 2017 roku, aby uzyskać szczegółowe informacje, w których przedstawiają propozycje, jak rozwinąć takie rzeczy.

Z tego wynika, że ​​twoje założenie nie utrzymuje, że wykonałeś swego rodzaju „ręczne rozwijanie” pętli. Rozważasz to jako podstawową technikę rozwijania pętli, która przekształca iterację nad tablicą z warunkowym podziałem na &&łańcuchowe wyrażenie boolowskie. Uznałbym to za dość szczególny przypadek i zdziwiłbym się, gdy optymalizator w gorącym punkcie dokonałby złożonego refaktoryzacji w locie. Tutaj dyskutują o tym, co faktycznie może zrobić, być może ten odnośnik jest interesujący.

Odzwierciedlałoby to mechanikę współczesnego rozwijania i być może nie jest jeszcze bliżej tego, jak wyglądałby rozwinięty kod maszynowy:

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

Stwierdzasz, że ponieważ jeden fragment kodu działa szybciej niż inny fragment kodu, pętla się nie rozwijała. Nawet jeśli tak, nadal widać różnicę czasu wykonywania ze względu na fakt, że porównujesz różne implementacje.

Jeśli chcesz uzyskać większą pewność, istnieje analizator / wizualizator jitwatch rzeczywistych operacji Jit, w tym kod maszynowy (github) (slajdy prezentacji) . Jeśli w końcu jest coś do zobaczenia, bardziej ufam moim oczom niż jakąkolwiek opinię na temat tego, co JIT może robić, a czego nie, ponieważ każda sprawa ma swoją specyfikę. Tutaj martwią się trudnością uzyskania ogólnych oświadczeń dla konkretnych przypadków w odniesieniu do JIT i podają ciekawe linki.

Ponieważ twoim celem jest minimalny czas działania, a && b && c ...forma jest prawdopodobnie najbardziej wydajna, jeśli nie chcesz polegać na nadziei na rozwijanie pętli, przynajmniej bardziej wydajną niż cokolwiek jeszcze prezentowanego. Ale nie możesz mieć tego w ogólny sposób. Dzięki funkcjonalnemu składowi java.util.Function znów pojawia się ogromny narzut (każda funkcja jest klasą, każde wywołanie jest metodą wirtualną, która wymaga wysyłki). Być może w takim scenariuszu sensowne byłoby obniżenie poziomu języka i wygenerowanie niestandardowego kodu bajtowego w czasie wykonywania. Z drugiej strony &&logika wymaga rozgałęzienia również na poziomie kodu bajtowego i może być równoważna z if / return (którego również nie można wygenerować bez obciążenia).