Duża luka w wydajności między instrukcją div procesora a kodem JIT HotSpot

Question

Od początku procesorów powszechnie wiadomo, że instrukcja dzielenia liczby całkowitej jest droga. Poszedłem zobaczyć, jak źle dziś jest, na procesorach, które mają luksus miliardów tranzystorów. Zauważyłem, że instrukcja sprzętowa nadal działa znacznie gorzej dla stałych dzielników niż kod, który kompilator JIT może emitować, który nie zawiera instrukcji idiv.

Aby to wydobyć w dedykowanym microbenchmark Pisałem następujące:

@BenchmarkMode(Mode.AverageTime) 
@OutputTimeUnit(TimeUnit.NANOSECONDS) 
@OperationsPerInvocation(MeasureDiv.ARRAY_SIZE) 
@Warmup(iterations = 8, time = 500, timeUnit = TimeUnit.MILLISECONDS) 
@Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS) 
@State(Scope.Thread) 
@Fork(1) 
public class MeasureDiv 
{ 
    public static final int ARRAY_SIZE = 128; 
    public static final long DIVIDEND_BASE = 239520948509234807L; 
    static final int DIVISOR = 10; 
    final long[] input = new long[ARRAY_SIZE]; 

    @Setup(Level.Iteration) public void setup() { 
    for (int i = 0; i < input.length; i++) { 
     input[i] = DIVISOR; 
    } 
    } 

    @Benchmark public long divVar() { 
    long sum = 0; 
    for (int i = 0; i < ARRAY_SIZE; i++) { 
     final long in = input[i]; 
     final long dividend = DIVIDEND_BASE + i; 
     final long divisor = in; 
     final long quotient = dividend/divisor; 
     sum += quotient; 
    } 
    return sum; 
    } 

    @Benchmark public long divConst() { 
    long sum = 0; 
    for (int i = 0; i < ARRAY_SIZE; i++) { 
     final long in = input[i]; 
     final long dividend = DIVIDEND_BASE + in; 
     final int divisor = DIVISOR; 
     final long quotient = dividend/divisor; 
     sum += quotient; 
    } 
    return sum; 
    } 
} 

W skrócie, mam dwie metody identyczne pod każdym względem z wyjątkiem tego jednego (divVar) wykonuje dzielenie przez liczbę odczytu poza tablicą, podczas gdy druga dzieli się przez stałą czasu kompilacji. Oto wyniki:

Benchmark   Mode Cnt Score Error Units 
MeasureDiv.divConst avgt 5 1.228 ± 0.032 ns/op 
MeasureDiv.divVar avgt 5 8.913 ± 0.192 ns/op 

Stosunek wydajności jest dość niezwykły. Spodziewam się, że nowoczesny procesor Intela ma wystarczająco dużo nieruchomości, a jego inżynierowie mają dość zainteresowania, aby wdrożyć złożony, ale wydajny algorytm podziału sprzętu. Jednak kompilator JIT bije Intel'a, wysyłając mu strumień innych instrukcji, które wykonują tę samą pracę, siedem razy szybciej. Jeśli cokolwiek, dedykowany mikrokod powinien być w stanie wykorzystać procesor nawet lepiej niż to, co JIT może zrobić za pomocą publicznego API instrukcji montażu.

Jak to się dzieje, że idiv jest wciąż o wiele wolniejszy, jakie jest podstawowe ograniczenie?

Jednym z wyjaśnień, które przychodzi na myśl, jest hipotetyczne istnienie algorytmu podziału, który po raz pierwszy bardzo późno wchodzi w proces z dywidendą. Kompilator JIT miałby wtedy początek, ponieważ oceniłby pierwszą część, która obejmuje tylko dzielnik w czasie kompilacji i wyśle ​​tylko drugą część algorytmu jako kod środowiska wykonawczego. Czy ta hipoteza jest prawdziwa?

Answer 1

Jak wyjaśniono przez użytkownika pvg poprzez komentarze, hipotetyczny algorytm rzeczywiście istnieje i jest najlepszy obecnie znany. Algorytm obejmuje podział przez ten sam dzielnik w etapie przygotowawczym, a więc zasadniczo jest nieredukowalny jako całość. Jest on opisany w rozdziale 10 klasycznej publikacji Hacker's Delight.