Moyen le plus rapide de vérifier la condition l + 1 < r pour int l, r en Java

Question

Quel est le moyen le plus rapide de vérifier l'état

l + 1 < r

pour int l, r en Java?

l et r ne sont pas constants et je sais que l < = r . La comparaison est une condition d'arrêt pour une boucle while dans une implémentation de recherche binaire. Bien sûr, je compare mon code, à la fois dans un test séparé (recherche dans un grand tableau) et dans le code qui l’utilise.

Ce que je recherche, j’imagine, c’est une sorte d’opération un peu plus rapide que la situation actuelle. Mais je ne sais pas.

Answer 1

Je pense que c'est probablement aussi rapide que cela va arriver. Cela réduira le bytecode très simple, et le JIT (compilateur juste à temps) le réduira probablement à une implémentation native très simple.

(Indépendante: il est intéressant de voir un "quant dev" utiliser Java btw. Cela n'arrive pas souvent)

Answer 2

Ce type de micro-optimisation est presque toujours une mauvaise idée. votre performance pour un si petit bit dépendra entièrement de la façon dont le compilateur de hotspot optimise votre code et des effets de cache subtils relatifs au code environnant.

Answer 3

La comparaison sous-jacente doit soit:

ajouter 1 à l, comparer le résultat à r

ou

soustrayez 1 de r et comparez le résultat à l

Tous les matériels modernes auront les mêmes performances brutes pour l'une ou l'autre opération (où l'addition et la soustraction de tout type de données natif ont des performances identiques en termes de cycles à compléter et d'effets secondaires de pipeline).

La seule façon dont cela aura un effet est si:

une des valeurs l ou r sont des constantes connues au moment de la compilation. par exemple.

l + 1 < 5
5 + 1 < r

dans ce cas, un compilateur optimiste médiocre peut ne pas se rendre compte qu'il peut convertir le premier en l < 4

mais tous les compilateurs Java sont tenus de détecter que le second cas est 6 < r

L'autre est si les types de données de l et r sont différents.

L'opération de:

1. addition / soustraction en virgule flottante puis comparaison à un int
   
   versets
2. addition / soustraction intégrale, la comparaison avec un double peut être différente.

Il est juste de dire que les chances que cela pose un problème grave dans votre demande sont négligeables, car le coût du cycle de ces opérations est minime par rapport au nombre de prédictions erronées d'une branche associée à la décision.

De plus, un JIT décent peut effectuer toutes sortes d’optimisations par rapport au code environnant qui surpasse la micro-optimisation réalisée.

Answer 4

Avoir une variable lr1 qui est toujours égale à (l - r + 1) . Chaque fois que vous incrémentez ou décrémentez l , procédez de la même manière pour lr1 . De même pour r .

Votre test devient alors (lr1 < 0) et les instructions pour modifier lr1 ne sont pas exécutées plus souvent que nécessaire.

Je me sens un peu bête de vous donner une micro-optimisation qui, dans la plupart des cas, équivaut à un sou. Comme si vous compariez des chaînes, le test sera totalement submergé.

ADDED: Puisque vous effectuez une recherche binaire, je voudrais mentionner le déroulement froid de la recherche binaire de Jon Bentley. Commencez par remplir la table A jusqu'à une puissance de 2, comme 1024. Ensuite, vous écrivez quelque chose comme ceci:

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

et enfin tester si (X == A [i]) . Ou, si vous ne souhaitez pas le remplir, laissez les instructions if ressembler à celles de
if (i + 512 < N & amp; & amp; X > = A [ i + 512]) i + = 512;

Answer 5

Ce que tous ces gars ont dit. Le compilateur va optimiser cela pour vous. Ecrivez-le pour qu'il ressemble et se lise correctement et continuez.

Answer 6

Votre meilleur choix est de modifier la machine virtuelle plutôt que le code - ceci étant votre goulot d'étranglement.

Essayez de démarrer jvm avec les arguments -server -XX: + AggressiveOpts .

Answer 7

Pourquoi ne pas déplacer votre test d'égalité en dehors de la boucle while afin de vérifier .equals () uniquement après la fin. Au fait, je ne trouvais pas le moindre moyen de tester si l + 1 < r. Si vous savez que la longueur de vos tableaux est inférieure à certaines tailles, qu’en est-il si vous utilisez un type de données différent pour les index? char / short / byte?