Il modo più veloce per verificare la condizione l + 1 < r per int l, r in Java

Question

Qual è il modo più veloce per verificare la condizione

l + 1 < r

per int l, r in Java?

l e r non sono costanti e so che l < = r . Il confronto è una condizione di arresto per un ciclo while in un'implementazione di ricerca binaria. Ovviamente sto confrontando il mio codice, sia in un test separato (ricerca di un array di grandi dimensioni) sia nel codice che lo utilizza.

Ciò che sto cercando, immagino, è una sorta di operazione che sarebbe più veloce della condizione attuale. Ma non lo so.

Answer 1

Penso che sia probabilmente tanto veloce quanto sta per arrivare. Ciò si ridurrà a un bytecode molto semplice e JIT (compilatore just-in-time) probabilmente lo ridurrà a un'implementazione nativa molto semplice.

(Non correlato: interessante vedere un 'sviluppatore quantico' usare Java tra l'altro. Non succede spesso)

Answer 2

Questo tipo di micro-ottimizzazione è quasi sempre una cattiva idea; le tue prestazioni per un pezzettino così piccolo dipenderanno interamente da come il compilatore di hotspot ottimizza il tuo codice e i sottili effetti della cache che hanno a che fare con il codice circostante.

Answer 3

Bene, il confronto sottostante deve:

aggiungi 1 a l, confronta il risultato con r

o

sottrai 1 da r e confronta il risultato con l

Tutto l'hardware moderno avrà le stesse prestazioni grezze per entrambe le operazioni (in cui l'aggiunta e la sottrazione di qualsiasi tipo di dati nativo ha prestazioni identiche in termini di cicli per completare ed effetti collaterali della pipeline).

L'unico modo in cui ciò avrà qualche effetto è se:

una delle l o r sono costanti note al momento della compilazione. ad es.

l + 1 < 5
5 + 1 < r

in questo caso un compilatore con scarsa ottimizzazione potrebbe non rendersi conto che può convertire il primo in l < 4

ma tutti i compilatori java sono tenuti a individuare che il secondo caso è 6 < r

L'altro è se i tipi di dati di le r sono diversi.

L'operazione di:

1. aggiunta / sottrazione in virgola mobile quindi confronto con un int
   versi
2. aggiunta / sottrazione integrale quindi il confronto con un doppio può essere diverso.

È corretto affermare che le possibilità che ciò costituisca un problema serio nella propria applicazione sono trascurabili, poiché il costo del ciclo di una di queste è minimo rispetto al colpo della pipeline di eventuali previsioni errate della filiale associate alla decisione.

Anche una JIT decente può fare ogni sorta di ottimizzazione in relazione al codice circostante che supera la micro ottimizzazione eseguita.

Answer 4

Hanno una variabile lr1 che è sempre uguale a (l - r + 1) . Ogni volta che aumenti o diminuisci l , fai lo stesso per lr1 . Allo stesso modo per r .

Quindi il test diventa (lr1 < 0) e le istruzioni per modificare lr1 non vengono eseguite più spesso del necessario.

Mi sento un po 'sciocco a darti una micro-ottimizzazione, che nella maggior parte dei casi è saggia, pazzesca. Come se stai confrontando le stringhe, sommergerà totalmente quel test.

AGGIUNTO: Dal momento che stai facendo una ricerca binaria, vorrei citare il fantastico srotolamento della ricerca binaria di Jon Bentley. Prima riempi la tabella A fino a una potenza di 2, come 1024. Quindi scrivi qualcosa del genere:

i = 0;
if (X >= A[i+512]) i += 512;
if (X >= A[i+256]) i += 256;
   . . .
if (X >= A[i+  1]) i +=   1;

e infine prova se (X == A [i]) . Oppure, se non vuoi riempirlo, lascia che le istruzioni if siano simili a
if (i + 512 < N & amp; & amp; X > = A [ i + 512]) i + = 512;

Answer 5

Cosa hanno detto tutti questi ragazzi. Il compilatore lo ottimizzerà per te. Scrivilo in modo che appaia e ti legga correttamente e vai avanti.

Answer 6

La soluzione migliore è modificare la JVM anziché il codice, dato che questo è il tuo collo di bottiglia.

Prova ad avviare jvm con gli argomenti -server -XX: + AggressiveOpts .

Answer 7

Che ne dici di spostare il tuo test di uguaglianza al di fuori del ciclo while, quindi controlli .equals () solo dopo la fine. btw non sono riuscito a trovare un po 'di modi per testare se l + 1 < r. Se è noto che le lunghezze degli array sono inferiori a determinate dimensioni, se si utilizza un tipo di dati diverso per gli indici? car / short / byte?