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:
- 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? - 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.
- 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);
}
}
1
Kompilator nie może zagwarantować, że długość tablicy wynosi 2. Nie jestem pewien, czy rozwinąłby ją, nawet gdyby mógł.
—
marstran
@Setup(Level.Invocation): nie jestem pewien, czy to pomaga (patrz javadoc).
Ponieważ nigdzie nie ma gwarancji, że tablica ma zawsze długość 2, obie metody nie robią tego samego. W jaki sposób JIT może pozwolić sobie na zmianę pierwszego na drugi?
—
Andreas
@Andreas Proponuję odpowiedzieć na pytanie, ale wyjaśnij, dlaczego JIT nie może rozwinąć się w tym przypadku w porównaniu z innym podobnym przypadkiem, w którym może
—
Alexander
@Alexander JIT może zobaczyć, że długość tablicy nie można zmienić po utworzeniu, ponieważ pole jest
—
Andreas
final, ale JIT nie widzi, że wszystkie instancje klasy dostanie tablicę długości 2. Aby zobaczyć, że byłoby mieć do nurkowania w createLeafFilters()i przeanalizuj kod na tyle głęboko, aby dowiedzieć się, że tablica zawsze będzie miała 2 długości. Dlaczego uważasz, że optymalizator JIT zanurkowałby tak głęboko w twoim kodzie?