Perché Java passa a inti contigui sembra correre più veloce con casi aggiunti?

Sto lavorando su un codice Java che deve essere altamente ottimizzato poiché verrà eseguito in funzioni molto attive richiamate in molti punti della logica del mio programma principale. Parte di questo codice coinvolge moltiplicare le double variabili per 10 elevato ad arbitrario non negativo int exponent . Un modo veloce (modifica: ma non il più veloce ansible, vedi Aggiornamento 2 sotto) per ottenere il valore moltiplicato è quello di switch l’ exponent :

 double multiplyByPowerOfTen(final double d, final int exponent) { switch (exponent) { case 0: return d; case 1: return d*10; case 2: return d*100; // ... same pattern case 9: return d*1000000000; case 10: return d*10000000000L; // ... same pattern with long literals case 18: return d*1000000000000000000L; default: throw new ParseException("Unhandled power of ten " + power, 0); } } 

Le ellissi commentate sopra indicano che le costanti int del case continuano ad aumentare di 1, quindi ci sono davvero 19 case nel frammento di codice sopra. Dato che non ero sicuro di aver effettivamente bisogno di tutte le potenze di 10 in case statement da 10 a 18 , ho eseguito alcuni microbenchmarks confrontando il tempo necessario per completare 10 milioni di operazioni con questa switch rispetto a un switch con solo il case s da 0 a 9 ( con l’ exponent limitato a 9 o meno per evitare di rompere l’ switch ridotto). Ho ottenuto il risultato piuttosto sorprendente (almeno per me!) Del fatto che lo switch più lungo con più affermazioni di case ha funzionato più velocemente.

Su un’allodola, ho provato ad aggiungere ancora più case che hanno appena restituito valori fittizi, e ho scoperto che avrei potuto far funzionare il passaggio ancora più velocemente con circa 22-27 case dichiarati (anche se quei casi fittizi non vengono mai effettivamente colpiti mentre il codice è in esecuzione). (Anche in questo case , i case sono stati aggiunti in modo contiguo incrementando la costante case precedente di 1 ). Queste differenze di tempo di esecuzione non sono molto significative: per un exponent casuale compreso tra 0 e 10 , l’istruzione switch fittizio termina 10 milioni di esecuzioni in 1.49 secondi contro 1.54 secondi per la versione non imbottita, per un risparmio totale di 5ns per esecuzione. Quindi, non è il tipo di cosa che rende ossessionante il fatto di riempire una dichiarazione di switch che vale lo sforzo da un punto di vista dell’ottimizzazione. Ma trovo ancora curioso e contro-intuitivo che un switch non diventi più lento (o forse al massimo mantenga il tempo O (1) costante) per eseguirlo man mano che vengono aggiunti più case .

cambia i risultati del benchmarking

Questi sono i risultati che ho ottenuto correndo con vari limiti sui valori di exponent generati casualmente. Non ho incluso i risultati fino a 1 per il limite di exponent , ma la forma generale della curva rimane la stessa, con una cresta attorno al 12-17 e una valle tra 18-28. Tutti i test sono stati eseguiti in JUnitBenchmarks utilizzando contenitori condivisi per i valori casuali per garantire identici input di test. Ho anche eseguito i test sia in ordine dall’istruzione switch più lunga a quella più breve, e viceversa, per cercare di eliminare la possibilità di problemi di test relativi agli ordini. Ho messo il mio codice di test su un repository Github se qualcuno vuole provare a riprodurre questi risultati.

    Allora, cosa sta succedendo qui? Alcuni capricci della mia architettura o costruzione di micro-benchmark? Oppure lo switch Java è davvero un po ‘più veloce da eseguire nell’intervallo da 18 a 28 rispetto a 17 ?

    github test repo “switch-experiment”

    AGGIORNAMENTO: ho ripulito un po ‘la libreria di benchmarking e ho aggiunto un file di testo in / results con un certo output su una gamma più ampia di possibili valori exponent . Ho anche aggiunto un’opzione nel codice di test per non lanciare Exception dall’impostazione default , ma questo non sembra influire sui risultati.

    AGGIORNAMENTO 2: Abbiamo trovato alcune discussioni abbastanza buone su questo problema nel 2009 sul forum xkcd qui: http://forums.xkcd.com/viewtopic.php?f=11&t=33524 . La discussione dell’OP sull’utilizzo di Array.binarySearch() mi ha dato l’idea di una semplice implementazione basata su array del modello di Array.binarySearch() alto. Non c’è bisogno della ricerca binaria poiché so quali sono le voci array . Sembra funzionare circa 3 volte più velocemente rispetto all’utilizzo switch , ovviamente a scapito di alcuni dei flussi di controllo che l’ switch offre. Quel codice è stato aggiunto anche al repository github.

    Come sottolineato dall’altra risposta , poiché i valori del caso sono contigui (al contrario di sparse), il codice byte generato per i vari test utilizza una tabella di commutazione ( tableswitch tabella di istruzioni bytecode).

    Tuttavia, una volta che il JIT inizia il suo lavoro e compila il bytecode in assembly, l’istruzione tableswitch non sempre risulta in una serie di puntatori: a volte la tabella degli switch viene trasformata in ciò che assomiglia a un lookupswitch (simile a if else if structure) .

    La decompilazione dell’assieme generato dal JIT (hotspot JDK 1.7) mostra che usa una successione di if / else se quando ci sono 17 casi o meno, una matrice di puntatori quando ce ne sono più di 18 (più efficienti).

    Il motivo per cui viene usato questo numero magico di 18 sembra scendere al valore predefinito del flag JVM MinJumpTableSize (attorno alla riga 352 nel codice).

    Ho sollevato il problema nella lista dei compilatori di hotspot e sembra essere un retaggio di test passati . Si noti che questo valore predefinito è stato rimosso in JDK 8 dopo aver eseguito più benchmark .

    Infine, quando il metodo diventa troppo lungo (> 25 casi nei miei test), non è più in linea con le impostazioni JVM predefinite – è la causa più probabile per il calo delle prestazioni in quel punto.


    Con 5 casi, il codice decompilato appare come questo (notare le istruzioni cmp / je / jg / jmp, l’assembly per if / goto):

     [Verified Entry Point] # {method} 'multiplyByPowerOfTen' '(DI)D' in 'javaapplication4/Test1' # parm0: xmm0:xmm0 = double # parm1: rdx = int # [sp+0x20] (sp of caller) 0x00000000024f0160: mov DWORD PTR [rsp-0x6000],eax ; {no_reloc} 0x00000000024f0167: push rbp 0x00000000024f0168: sub rsp,0x10 ;*synchronization entry ; - javaapplication4.Test1::[email protected] (line 56) 0x00000000024f016c: cmp edx,0x3 0x00000000024f016f: je 0x00000000024f01c3 0x00000000024f0171: cmp edx,0x3 0x00000000024f0174: jg 0x00000000024f01a5 0x00000000024f0176: cmp edx,0x1 0x00000000024f0179: je 0x00000000024f019b 0x00000000024f017b: cmp edx,0x1 0x00000000024f017e: jg 0x00000000024f0191 0x00000000024f0180: test edx,edx 0x00000000024f0182: je 0x00000000024f01cb 0x00000000024f0184: mov ebp,edx 0x00000000024f0186: mov edx,0x17 0x00000000024f018b: call 0x00000000024c90a0 ; OopMap{off=48} ;*new ; - javaapplication4.Test1::[email protected] (line 83) ; {runtime_call} 0x00000000024f0190: int3 ;*new ; - javaapplication4.Test1::[email protected] (line 83) 0x00000000024f0191: mulsd xmm0,QWORD PTR [rip+0xffffffffffffffa7] # 0x00000000024f0140 ;*dmul ; - javaapplication4.Test1::[email protected] (line 62) ; {section_word} 0x00000000024f0199: jmp 0x00000000024f01cb 0x00000000024f019b: mulsd xmm0,QWORD PTR [rip+0xffffffffffffff8d] # 0x00000000024f0130 ;*dmul ; - javaapplication4.Test1::[email protected] (line 60) ; {section_word} 0x00000000024f01a3: jmp 0x00000000024f01cb 0x00000000024f01a5: cmp edx,0x5 0x00000000024f01a8: je 0x00000000024f01b9 0x00000000024f01aa: cmp edx,0x5 0x00000000024f01ad: jg 0x00000000024f0184 ;*tableswitch ; - javaapplication4.Test1::[email protected] (line 56) 0x00000000024f01af: mulsd xmm0,QWORD PTR [rip+0xffffffffffffff81] # 0x00000000024f0138 ;*dmul ; - javaapplication4.Test1::[email protected] (line 66) ; {section_word} 0x00000000024f01b7: jmp 0x00000000024f01cb 0x00000000024f01b9: mulsd xmm0,QWORD PTR [rip+0xffffffffffffff67] # 0x00000000024f0128 ;*dmul ; - javaapplication4.Test1::[email protected] (line 68) ; {section_word} 0x00000000024f01c1: jmp 0x00000000024f01cb 0x00000000024f01c3: mulsd xmm0,QWORD PTR [rip+0xffffffffffffff55] # 0x00000000024f0120 ;*tableswitch ; - javaapplication4.Test1::[email protected] (line 56) ; {section_word} 0x00000000024f01cb: add rsp,0x10 0x00000000024f01cf: pop rbp 0x00000000024f01d0: test DWORD PTR [rip+0xfffffffffdf3fe2a],eax # 0x0000000000430000 ; {poll_return} 0x00000000024f01d6: ret 

    Con 18 casi, l’assembly è simile a questo (notare l’array di puntatori che viene utilizzato e sopprime la necessità di tutti i confronti: jmp QWORD PTR [r8+r10*1] salta direttamente alla moltiplicazione di destra) – questa è la probabile ragione per il miglioramento delle prestazioni:

     [Verified Entry Point] # {method} 'multiplyByPowerOfTen' '(DI)D' in 'javaapplication4/Test1' # parm0: xmm0:xmm0 = double # parm1: rdx = int # [sp+0x20] (sp of caller) 0x000000000287fe20: mov DWORD PTR [rsp-0x6000],eax ; {no_reloc} 0x000000000287fe27: push rbp 0x000000000287fe28: sub rsp,0x10 ;*synchronization entry ; - javaapplication4.Test1::[email protected] (line 56) 0x000000000287fe2c: cmp edx,0x13 0x000000000287fe2f: jae 0x000000000287fe46 0x000000000287fe31: movsxd r10,edx 0x000000000287fe34: shl r10,0x3 0x000000000287fe38: movabs r8,0x287fd70 ; {section_word} 0x000000000287fe42: jmp QWORD PTR [r8+r10*1] ;*tableswitch ; - javaapplication4.Test1::[email protected] (line 56) 0x000000000287fe46: mov ebp,edx 0x000000000287fe48: mov edx,0x31 0x000000000287fe4d: xchg ax,ax 0x000000000287fe4f: call 0x00000000028590a0 ; OopMap{off=52} ;*new ; - javaapplication4.Test1::[email protected] (line 96) ; {runtime_call} 0x000000000287fe54: int3 ;*new ; - javaapplication4.Test1::[email protected] (line 96) 0x000000000287fe55: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe8b] # 0x000000000287fce8 ;*dmul ; - javaapplication4.Test1::[email protected] (line 92) ; {section_word} 0x000000000287fe5d: jmp 0x000000000287ff16 0x000000000287fe62: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe86] # 0x000000000287fcf0 ;*dmul ; - javaapplication4.Test1::[email protected] (line 90) ; {section_word} 0x000000000287fe6a: jmp 0x000000000287ff16 0x000000000287fe6f: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe81] # 0x000000000287fcf8 ;*dmul ; - javaapplication4.Test1::[email protected] (line 88) ; {section_word} 0x000000000287fe77: jmp 0x000000000287ff16 0x000000000287fe7c: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe7c] # 0x000000000287fd00 ;*dmul ; - javaapplication4.Test1::[email protected] (line 86) ; {section_word} 0x000000000287fe84: jmp 0x000000000287ff16 0x000000000287fe89: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe77] # 0x000000000287fd08 ;*dmul ; - javaapplication4.Test1::[email protected] (line 84) ; {section_word} 0x000000000287fe91: jmp 0x000000000287ff16 0x000000000287fe96: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe72] # 0x000000000287fd10 ;*dmul ; - javaapplication4.Test1::[email protected] (line 82) ; {section_word} 0x000000000287fe9e: jmp 0x000000000287ff16 0x000000000287fea0: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe70] # 0x000000000287fd18 ;*dmul ; - javaapplication4.Test1::[email protected] (line 80) ; {section_word} 0x000000000287fea8: jmp 0x000000000287ff16 0x000000000287feaa: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe6e] # 0x000000000287fd20 ;*dmul ; - javaapplication4.Test1::[email protected] (line 78) ; {section_word} 0x000000000287feb2: jmp 0x000000000287ff16 0x000000000287feb4: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe24] # 0x000000000287fce0 ;*dmul ; - javaapplication4.Test1::[email protected] (line 76) ; {section_word} 0x000000000287febc: jmp 0x000000000287ff16 0x000000000287febe: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe6a] # 0x000000000287fd30 ;*dmul ; - javaapplication4.Test1::[email protected] (line 74) ; {section_word} 0x000000000287fec6: jmp 0x000000000287ff16 0x000000000287fec8: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe68] # 0x000000000287fd38 ;*dmul ; - javaapplication4.Test1::[email protected] (line 72) ; {section_word} 0x000000000287fed0: jmp 0x000000000287ff16 0x000000000287fed2: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe66] # 0x000000000287fd40 ;*dmul ; - javaapplication4.Test1::multiply[email protected] (line 70) ; {section_word} 0x000000000287feda: jmp 0x000000000287ff16 0x000000000287fedc: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe64] # 0x000000000287fd48 ;*dmul ; - javaapplication4.Test1::[email protected] (line 68) ; {section_word} 0x000000000287fee4: jmp 0x000000000287ff16 0x000000000287fee6: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe62] # 0x000000000287fd50 ;*dmul ; - javaapplication4.Test1::[email protected] (line 66) ; {section_word} 0x000000000287feee: jmp 0x000000000287ff16 0x000000000287fef0: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe60] # 0x000000000287fd58 ;*dmul ; - javaapplication4.Test1::[email protected] (line 64) ; {section_word} 0x000000000287fef8: jmp 0x000000000287ff16 0x000000000287fefa: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe5e] # 0x000000000287fd60 ;*dmul ; - javaapplication4.Test1::[email protected] (line 62) ; {section_word} 0x000000000287ff02: jmp 0x000000000287ff16 0x000000000287ff04: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe5c] # 0x000000000287fd68 ;*dmul ; - javaapplication4.Test1::[email protected] (line 60) ; {section_word} 0x000000000287ff0c: jmp 0x000000000287ff16 0x000000000287ff0e: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe12] # 0x000000000287fd28 ;*tableswitch ; - javaapplication4.Test1::[email protected] (line 56) ; {section_word} 0x000000000287ff16: add rsp,0x10 0x000000000287ff1a: pop rbp 0x000000000287ff1b: test DWORD PTR [rip+0xfffffffffd9b00df],eax # 0x0000000000230000 ; {poll_return} 0x000000000287ff21: ret 

    E infine l’assemblaggio con 30 casi (sotto) sembra simile a 18 casi, fatta eccezione per la movapd xmm0,xmm1 che appare verso il centro del codice, come indicato da @cHao – tuttavia il motivo più probabile per il calo delle prestazioni è che il metodo è troppo lungo per essere allineato con le impostazioni JVM predefinite:

     [Verified Entry Point] # {method} 'multiplyByPowerOfTen' '(DI)D' in 'javaapplication4/Test1' # parm0: xmm0:xmm0 = double # parm1: rdx = int # [sp+0x20] (sp of caller) 0x0000000002524560: mov DWORD PTR [rsp-0x6000],eax ; {no_reloc} 0x0000000002524567: push rbp 0x0000000002524568: sub rsp,0x10 ;*synchronization entry ; - javaapplication4.Test1::[email protected] (line 56) 0x000000000252456c: movapd xmm1,xmm0 0x0000000002524570: cmp edx,0x1f 0x0000000002524573: jae 0x0000000002524592 ;*tableswitch ; - javaapplication4.Test1::[email protected] (line 56) 0x0000000002524575: movsxd r10,edx 0x0000000002524578: shl r10,0x3 0x000000000252457c: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe3c] # 0x00000000025243c0 ;*dmul ; - javaapplication4.Test1::[email protected] (line 118) ; {section_word} 0x0000000002524584: movabs r8,0x2524450 ; {section_word} 0x000000000252458e: jmp QWORD PTR [r8+r10*1] ;*tableswitch ; - javaapplication4.Test1::[email protected] (line 56) 0x0000000002524592: mov ebp,edx 0x0000000002524594: mov edx,0x31 0x0000000002524599: xchg ax,ax 0x000000000252459b: call 0x00000000024f90a0 ; OopMap{off=64} ;*new ; - javaapplication4.Test1::[email protected] (line 120) ; {runtime_call} 0x00000000025245a0: int3 ;*new ; - javaapplication4.Test1::[email protected] (line 120) 0x00000000025245a1: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe27] # 0x00000000025243d0 ;*dmul ; - javaapplication4.Test1::[email protected] (line 116) ; {section_word} 0x00000000025245a9: jmp 0x0000000002524744 0x00000000025245ae: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe22] # 0x00000000025243d8 ;*dmul ; - javaapplication4.Test1::[email protected] (line 114) ; {section_word} 0x00000000025245b6: jmp 0x0000000002524744 0x00000000025245bb: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe1d] # 0x00000000025243e0 ;*dmul ; - javaapplication4.Test1::[email protected] (line 112) ; {section_word} 0x00000000025245c3: jmp 0x0000000002524744 0x00000000025245c8: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe18] # 0x00000000025243e8 ;*dmul ; - javaapplication4.Test1::[email protected] (line 110) ; {section_word} 0x00000000025245d0: jmp 0x0000000002524744 0x00000000025245d5: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe13] # 0x00000000025243f0 ;*dmul ; - javaapplication4.Test1::[email protected] (line 108) ; {section_word} 0x00000000025245dd: jmp 0x0000000002524744 0x00000000025245e2: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe0e] # 0x00000000025243f8 ;*dmul ; - javaapplication4.Test1::[email protected] (line 106) ; {section_word} 0x00000000025245ea: jmp 0x0000000002524744 0x00000000025245ef: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe09] # 0x0000000002524400 ;*dmul ; - javaapplication4.Test1::[email protected] (line 104) ; {section_word} 0x00000000025245f7: jmp 0x0000000002524744 0x00000000025245fc: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe04] # 0x0000000002524408 ;*dmul ; - javaapplication4.Test1::[email protected] (line 102) ; {section_word} 0x0000000002524604: jmp 0x0000000002524744 0x0000000002524609: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffdff] # 0x0000000002524410 ;*dmul ; - javaapplication4.Test1::[email protected] (line 100) ; {section_word} 0x0000000002524611: jmp 0x0000000002524744 0x0000000002524616: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffdfa] # 0x0000000002524418 ;*dmul ; - javaapplication4.Test1::[email protected] (line 98) ; {section_word} 0x000000000252461e: jmp 0x0000000002524744 0x0000000002524623: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffd9d] # 0x00000000025243c8 ;*dmul ; - javaapplication4.Test1::[email protected] (line 96) ; {section_word} 0x000000000252462b: jmp 0x0000000002524744 0x0000000002524630: movapd xmm0,xmm1 0x0000000002524634: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffe0c] # 0x0000000002524448 ;*dmul ; - javaapplication4.Test1::[email protected] (line 92) ; {section_word} 0x000000000252463c: jmp 0x0000000002524744 0x0000000002524641: movapd xmm0,xmm1 0x0000000002524645: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffddb] # 0x0000000002524428 ;*dmul ; - javaapplication4.Test1::[email protected] (line 90) ; {section_word} 0x000000000252464d: jmp 0x0000000002524744 0x0000000002524652: movapd xmm0,xmm1 0x0000000002524656: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffdd2] # 0x0000000002524430 ;*dmul ; - javaapplication4.Test1::[email protected] (line 88) ; {section_word} 0x000000000252465e: jmp 0x0000000002524744 0x0000000002524663: movapd xmm0,xmm1 0x0000000002524667: mulsd xmm0,QWORD PTR [rip+0xfffffffffffffdc9] # 0x0000000002524438 ;*dmul ; - javaapplication4.Test1::[email protected] (line 86) ; {section_word} [etc.] 0x0000000002524744: add rsp,0x10 0x0000000002524748: pop rbp 0x0000000002524749: test DWORD PTR [rip+0xfffffffffde1b8b1],eax # 0x0000000000340000 ; {poll_return} 0x000000000252474f: ret 

    Switch – case è più veloce se i valori del caso sono posizionati in un intervallo ristretto. Ad es.

     case 1: case 2: case 3: .. .. case n: 

    Perché in questo caso il compilatore può evitare di eseguire un confronto per ogni gamba del caso nell’istruzione switch. Il compilatore crea una tabella di salto che contiene gli indirizzi delle azioni da intraprendere su gambe diverse. Il valore su cui viene eseguito lo switch viene manipolato per convertirlo in un indice nella jump table . In questa implementazione, il tempo impiegato nell’istruzione switch è molto inferiore al tempo impiegato in un’equivalente istruzione if-else-if. Anche il tempo impiegato nell’istruzione switch è indipendente dal numero di piedini del caso nell’istruzione switch.

    Come affermato in wikipedia sull’istruzione switch nella sezione Compilation.

    Se l’intervallo di valori di input è identicamente “piccolo” e presenta solo poche lacune, alcuni compilatori che incorporano un ottimizzatore possono effettivamente implementare l’istruzione switch come una tabella di diramazione o una matrice di puntatori a funzione indicizzata invece di una lunga serie di istruzioni condizionali. Ciò consente all’istruzione switch di determinare immediatamente quale ramo eseguire senza dover passare da un elenco di confronti.

    La risposta sta nel bytecode:

    SwitchTest10.java

     public class SwitchTest10 { public static void main(String[] args) { int n = 0; switcher(n); } public static void switcher(int n) { switch(n) { case 0: System.out.println(0); break; case 1: System.out.println(1); break; case 2: System.out.println(2); break; case 3: System.out.println(3); break; case 4: System.out.println(4); break; case 5: System.out.println(5); break; case 6: System.out.println(6); break; case 7: System.out.println(7); break; case 8: System.out.println(8); break; case 9: System.out.println(9); break; case 10: System.out.println(10); break; default: System.out.println("test"); } } } 

    Bytecode corrispondente; solo le parti rilevanti mostrate:

     public static void switcher(int); Code: 0: iload_0 1: tableswitch{ //0 to 10 0: 60; 1: 70; 2: 80; 3: 90; 4: 100; 5: 110; 6: 120; 7: 131; 8: 142; 9: 153; 10: 164; default: 175 } 

    SwitchTest22.java:

     public class SwitchTest22 { public static void main(String[] args) { int n = 0; switcher(n); } public static void switcher(int n) { switch(n) { case 0: System.out.println(0); break; case 1: System.out.println(1); break; case 2: System.out.println(2); break; case 3: System.out.println(3); break; case 4: System.out.println(4); break; case 5: System.out.println(5); break; case 6: System.out.println(6); break; case 7: System.out.println(7); break; case 8: System.out.println(8); break; case 9: System.out.println(9); break; case 100: System.out.println(10); break; case 110: System.out.println(10); break; case 120: System.out.println(10); break; case 130: System.out.println(10); break; case 140: System.out.println(10); break; case 150: System.out.println(10); break; case 160: System.out.println(10); break; case 170: System.out.println(10); break; case 180: System.out.println(10); break; case 190: System.out.println(10); break; case 200: System.out.println(10); break; case 210: System.out.println(10); break; case 220: System.out.println(10); break; default: System.out.println("test"); } } } 

    Bytecode corrispondente; di nuovo, solo le parti rilevanti mostrate:

     public static void switcher(int); Code: 0: iload_0 1: lookupswitch{ //23 0: 196; 1: 206; 2: 216; 3: 226; 4: 236; 5: 246; 6: 256; 7: 267; 8: 278; 9: 289; 100: 300; 110: 311; 120: 322; 130: 333; 140: 344; 150: 355; 160: 366; 170: 377; 180: 388; 190: 399; 200: 410; 210: 421; 220: 432; default: 443 } 

    Nel primo caso, con intervalli ristretti, il bytecode compilato utilizza un tableswitch . Nel secondo caso, il bytecode compilato utilizza un lookupswitch .

    Nell’interruttore delle tableswitch , il valore intero nella parte superiore della pila viene utilizzato per indicizzare nella tabella, per trovare il target di salto / salto. Questo salto / ramo viene quindi eseguito immediatamente. Quindi, questa è un’operazione O(1) .

    Un lookupswitch è più complicato. In questo caso, il valore intero deve essere confrontato con tutte le chiavi della tabella finché non viene trovata la chiave corretta. Dopo aver trovato la chiave, per il salto viene utilizzato il target di salto / salto (su cui questa chiave è mappata). La tabella utilizzata in lookupswitch viene ordinata e un algoritmo di ricerca binaria può essere utilizzato per trovare la chiave corretta. Le prestazioni per una ricerca binaria sono O(log n) , e l’intero processo è anche O(log n) , perché il salto è ancora O(1) . Quindi il motivo per cui le prestazioni sono inferiori nel caso di intervalli sparsi è che la chiave corretta deve prima essere cercata perché non è ansible indicizzare direttamente nella tabella.

    Se ci sono valori sparsi e hai solo un tableswitch di tableswitch da utilizzare, la tabella contiene essenzialmente voci fittizie che puntano all’opzione default . Ad esempio, supponendo che l’ultima voce in SwitchTest10.java stata 21 anziché 10 , ottieni:

     public static void switcher(int); Code:  0: iload_0  1: tableswitch{ //0 to 21 0: 104; 1: 114; 2: 124; 3: 134; 4: 144; 5: 154; 6: 164; 7: 175; 8: 186; 9: 197; 10: 219; 11: 219; 12: 219; 13: 219; 14: 219; 15: 219; 16: 219; 17: 219; 18: 219; 19: 219; 20: 219; 21: 208; default: 219 } 

    Quindi il compilatore fondamentalmente crea questa enorme tabella contenente voci fittizie tra gli spazi, che punta al ramo target dell’istruzione default . Anche se non esiste un default , conterrà le voci che puntano all’istruzione dopo il blocco dell’interruttore. Ho fatto alcuni test di base e ho scoperto che se il divario tra l’ultimo indice e quello precedente ( 9 ) è maggiore di 35 , utilizza un lookupswitch invece di un tableswitch .

    Il comportamento dell’istruzione switch è definito in Java Virtual Machine Specification (§3.10) :

    Laddove i casi dell’interruttore sono sparsi, la rappresentazione della tabella dell’istruzione del commutatore di tabelle diventa inefficiente in termini di spazio. L’istruzione lookupswitch può invece essere utilizzata. L’istruzione lookupswitch accoppia le chiavi int (i valori delle etichette case) con gli offset target in una tabella. Quando viene eseguita un’istruzione lookupswitch, il valore dell’espressione dell’interruttore viene confrontato con i tasti della tabella. Se una delle chiavi corrisponde al valore dell’espressione, l’esecuzione continua all’offset target associato. Se nessuna chiave corrisponde, l’esecuzione continua con la destinazione predefinita. […]

    Poiché la domanda ha già una risposta (più o meno), ecco un suggerimento. Uso

     private static final double[] mul={1d, 10d...}; static double multiplyByPowerOfTen(final double d, final int exponent) { if (exponent<0 || exponent>=mul.length) throw new ParseException();//or just leave the IOOBE be return mul[exponent]*d; } 

    Quel codice usa significativamente meno IC (cache delle istruzioni) e sarà sempre in linea. La matrice sarà nella cache di dati L1 se il codice è caldo. La tabella di ricerca è quasi sempre una vittoria. (specialmente sui microbenchmarks: D)

    Modifica: se si desidera che il metodo sia caldo-in-linea, considerare i percorsi non veloci come throw new ParseException() per essere il più corti ansible o spostarli in un metodo statico separato (quindi ridurli al minimo). Questa è la throw new ParseException("Unhandled power of ten " + power, 0); è un’idea debole b / c si mangia un sacco di budget per il codice che può essere semplicemente interpretato – la concatenazione delle stringhe è piuttosto dettagliata in bytecode. Maggiori informazioni e un caso reale con ArrayList