Ampio intervallo di prestazioni tra l'istruzione div della CPU e il codice JIT di HotSpot

Question

Dall'inizio delle CPU è noto che l'istruzione di divisione dei numeri interi è costosa. Sono andato a vedere quanto è pessimo oggi, su CPU che hanno il lusso di miliardi di transistor. Ho scoperto che l'hardware dell'hardware idiv funziona ancora significativamente peggio per i divisori costanti rispetto al codice che il compilatore JIT è in grado di emettere, che non contiene l'istruzione idiv.

Per portare questo in un microbenchmark dedicata ho scritto il seguente:

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

In poche parole, ho due metodi identici a tutti gli effetti, tranne che uno (divVar) esegue la divisione per un numero di leggere di un array mentre l'altro si divide per una costante in fase di compilazione. Questi sono i risultati:

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 

Il rapporto prestazioni è piuttosto straordinario. La mia aspettativa è che un moderno processore Intel abbia abbastanza spazio e che i suoi ingegneri abbiano abbastanza interesse per implementare un algoritmo di divisione complesso ma performante nell'hardware. Eppure il compilatore JIT batte Intel inviandogli un flusso di altre istruzioni che eseguono lo stesso lavoro, solo sette volte più velocemente. Se non altro, il microcodice dedicato dovrebbe essere in grado di utilizzare la CPU anche meglio di quello che JIT può fare tramite l'API pubblica delle istruzioni di assemblaggio.

Come mai idiv è ancora molto più lento, qual è il limite fondamentale?

Una spiegazione che viene in mente è l'esistenza ipotetica di un algoritmo di divisione che coinvolge il dividendo per la prima volta molto tardi nel processo. Il compilatore JIT avrebbe quindi un vantaggio iniziale perché valuterebbe la prima parte che coinvolge solo il divisore in fase di compilazione ed emetterà solo la seconda parte dell'algoritmo come codice di runtime. Questa ipotesi è vera?

Answer 1

Come spiegato dall'utente pvg attraverso i commenti, l'algoritmo ipotizzato è effettivamente esistente e il migliore attualmente conosciuto. L'algoritmo implica la divisione per lo stesso divisore nella fase preparatoria, quindi è fondamentalmente irriducibile nel suo complesso. È trattato nel capitolo 10 della pubblicazione classica Hacker's Delight.