Large écart de performance entre l’instruction div du processeur et le code JIT de HotSpot

Depuis le début des processeurs, il est de notoriété publique que l’instruction de division entière est coûteuse. Je suis allé voir à quel point c’est mauvais aujourd’hui, sur des processeurs qui ont le luxe de milliards de transistors. J’ai constaté que l’instruction idiv matérielle idiv toujours de manière bien pire pour les diviseurs constants que le code que le compilateur JIT est capable d’émettre, qui ne contient pas l’instruction idiv .

Pour mettre cela en évidence dans un micro-critère dédié, j’ai écrit ce qui suit:

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

En un mot, j’ai deux méthodes identiques à tous égards sauf que l’une ( divVar ) effectue la division par un nombre lu par un tableau, tandis que l’autre est divisée par une constante de compilation. Ce sont les résultats:

 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

Le rapport de performance est assez extraordinaire. Mon attente serait qu’un processeur Intel moderne dispose de suffisamment de biens immobiliers et que ses ingénieurs aient un intérêt suffisant pour mettre en œuvre un algorithme de division complexe mais performant dans le matériel. Pourtant, le compilateur JIT bat Intel en lui envoyant un stream d’instructions qui effectuent le même travail sept fois plus vite. Au mieux, le microcode dédié devrait pouvoir utiliser le processeur encore mieux que ce que JIT peut faire via l’API publique des instructions d’assemblage.

Comment se fait-il que idiv soit encore tellement plus lent, quelle est la limitation fondamentale?

Une explication qui nous vient à l’esprit est l’existence hypothétique d’un algorithme de division qui implique le dividende pour la première fois très tard dans le processus. Le compilateur JIT aurait alors une longueur d’avance, car il évaluerait la première partie impliquant uniquement le diviseur au moment de la compilation et n’émettrait que la seconde partie de l’algorithme sous forme de code d’exécution. Cette hypothèse est-elle vraie?

Comme l’explique l’utilisateur pvg à travers les commentaires, l’algorithme supposé existe et est le meilleur qui soit. L’algorithme implique la division par le même diviseur lors de la phase préparatoire, il est donc fondamentalement irréductible dans son ensemble. Il est couvert au chapitre 10 de la publication classique Hacker’s Delight .