Différence entre if (a – b <0) et if (a <b)

Je lisais le code source de Java ArrayList et remarquais des comparaisons dans les instructions if.

Dans Java 7, la méthode grow(int) utilise

 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; 

En Java 6, la grow n’existait pas. La méthode ensureCapacity(int) utilise cependant

 if (newCapacity < minCapacity) newCapacity = minCapacity; 

Quelle était la raison du changement? Était-ce un problème de performance ou juste un style?

Je peux imaginer que la comparaison avec zéro est plus rapide, mais effectuer une soustraction complète pour vérifier si elle est négative me semble un peu exagérée. Toujours en termes de bytecode, cela impliquerait deux instructions ( ISUB et IF_ICMPGE ) au lieu d’un seul ( IFGE ).

a < b et a - b < 0 peut signifier deux choses différentes. Considérez le code suivant:

 int a = Integer.MAX_VALUE; int b = Integer.MIN_VALUE; if (a < b) { System.out.println("a < b"); } if (a - b < 0) { System.out.println("a - b < 0"); } 

Lorsqu'il est exécuté, cela imprimera uniquement a - b < 0 . Ce qui se passe, c'est a < b est clairement faux, mais a - b déborde et devient -1 , ce qui est négatif.

Maintenant, cela dit, considérez que le tableau a une longueur vraiment proche de Integer.MAX_VALUE . Le code dans ArrayList va comme ceci:

 int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); 

oldCapacity est vraiment proche de Integer.MAX_VALUE donc newCapacity (qui est oldCapacity + 0.5 * oldCapacity ) peut déborder et devenir Integer.MIN_VALUE (c'est-à-dire négatif). Ensuite, la soustraction de minCapacity revient à un nombre positif.

Cette vérification garantit que le if n'est pas exécuté. Si le code était écrit comme if (newCapacity < minCapacity) , ce serait true dans ce cas (puisque newCapacity est négatif), le newCapacity serait forcé à minCapacity indépendamment de oldCapacity .

Ce cas de dépassement est traité par le prochain if. Lorsque newCapacity a débordé, cela sera true : MAX_ARRAY_SIZE est défini comme Integer.MAX_VALUE - 8 et Integer.MIN_VALUE - (Integer.MAX_VALUE - 8) > 0 est true . Le newCapacity est donc correctement géré: la méthode MAX_ARRAY_SIZE renvoie MAX_ARRAY_SIZE ou Integer.MAX_VALUE .

NB: c'est ce que dit le commentaire de // overflow-conscious code dans cette méthode.

J’ai trouvé cette explication :

Le mardi 9 mars 2010 à 03:02, Kevin L. Stern a écrit:

J’ai fait une recherche rapide et il semble que Java soit en effet basé sur deux complément. Néanmoins, permettez-moi de souligner que, en général, ce type de code m’inquiète car je m’attends à ce que quelqu’un vienne et fasse exactement ce que Dmytro a proposé; c’est-à-dire que quelqu’un changera:

 if (a - b > 0) 

à

 if (a > b) 

et le navire entier coulera. Personnellement, j’aime éviter les obscurités, par exemple en faisant du débordement d’entiers une base essentielle de mon algorithme, à moins qu’il y ait une bonne raison de le faire. De manière générale, je préférerais éviter tout débordement et rendre le scénario de dépassement plus explicite:

 if (oldCapacity > RESIZE_OVERFLOW_THRESHOLD) { // Do something } else { // Do something else } 

C’est un bon point.

Dans ArrayList nous ne pouvons pas faire cela (ou du moins pas de manière compatible), car ensureCapacity est une API publique et accepte déjà les nombres négatifs comme des demandes pour une capacité positive qui ne peut pas être satisfaite.

L’API actuelle est utilisée comme ceci:

 int newcount = count + len; ensureCapacity(newcount); 

Si vous voulez éviter le débordement, vous devrez changer pour quelque chose de moins naturel comme

 ensureCapacity(count, len); int newcount = count + len; 

Quoi qu’il en soit, je garde le code conscient des débordements, mais en ajoutant plus de commentaires d’avertissement, et en “alignant” une énorme création de tableaux pour que le code d’ ArrayList ressemble maintenant à ceci:

 /** * Increases the capacity of this ArrayList instance, if * necessary, to ensure that it can hold at least the number of elements * specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */ public void ensureCapacity(int minCapacity) { modCount++; // Overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } /** * The maximum size of array to allocate. * Some VMs reserve some header words in an array. * Attempts to allocate larger arrays may result in * OutOfMemoryError: Requested array size exceeds VM limit */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; /** * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */ private void grow(int minCapacity) { // Overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } private int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } 

Webrev régénéré.

Martin

En Java 6, si vous utilisez l’API en tant que:

 int newcount = count + len; ensureCapacity(newcount); 

Et newCount déborde (cela devient négatif), if (minCapacity > oldCapacity) retournera false et vous pouvez supposer à tort que la ArrayList été augmentée de len .

En regardant le code:

 int newCapacity = oldCapacity + (oldCapacity >> 1); 

Si oldCapacity est assez volumineux, cela va déborder et newCapacity sera un nombre négatif. Une comparaison comme newCapacity < oldCapacity évaluera incorrectement true et ArrayList ne pourra pas se développer.

Au lieu de cela, le code tel qu’écrit ( newCapacity - minCapacity < 0 renvoie false) permettra d’ newCapacity valeur négative de newCapacity dans la ligne suivante, ce qui entraînera le recalcul de newCapacity en hugeCapacity ( newCapacity = hugeCapacity(minCapacity); ) la ArrayList pour atteindre MAX_ARRAY_SIZE .

C'est ce que le commentaire de // overflow-conscious code essaie de communiquer, quoique de manière plutôt oblique.

Donc, en bout de ligne, la nouvelle comparaison MAX_ARRAY_SIZE allouer une ArrayList plus grande que la valeur MAX_ARRAY_SIZE prédéfinie tout en lui permettant de croître jusqu'à cette limite si nécessaire.

Les deux formes se comportent exactement de la même manière, à moins que l’expression a - b déborde, auquel cas elles sont opposées. Si a est un grand grand et b est un grand positif, alors (a < b) est clairement vrai, mais a - b va déborder pour devenir positif, donc (a - b < 0) est faux.

Si vous êtes familier avec le code de l'assembly x86, considérez que (a < b) est implémenté par un jge , qui contourne le corps de l'instruction if lorsque SF = OF. Par contre, (a - b < 0) agira comme un jns , qui se twig quand SF = 0. Par conséquent, ceux-ci se comportent différemment précisément quand OF = 1.