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

Question

J'ai été la lecture de Java ArrayList code source et a remarqué des comparaisons dans le si-états.

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

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

Dans la version 6 de Java, grow n'existe pas. La méthode ensureCapacity(int) cependant utilise

if (newCapacity < minCapacity)
    newCapacity = minCapacity;

Quelle était la raison derrière ce changement? Était-ce un problème de performance ou simplement d'un style?

Je ne pouvais imaginer que le comparant à zéro est plus rapide, mais l'exécution complète de la soustraction juste pour vérifier si il est négatif, semble un peu exagéré pour moi. Aussi en termes de "bytecode", cela impliquerait deux instructions (ISUB et IF_ICMPGE) au lieu d'une (IFGE).

Answer 1

a < b et a - b < 0 peut signifier deux choses différentes. Considérons 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é, ce sera seulement imprimer a - b < 0. Ce qui se passe c'est qu' a < b est clairement faux, mais a - b déborde et devient -1, ce qui est négatif.

Maintenant, après avoir dit que, considèrent que le tableau a une longueur qui est vraiment proche de l' Integer.MAX_VALUE. Le code en 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 l' Integer.MAX_VALUE donc newCapacity (ce qui est oldCapacity + 0.5 * oldCapacity) risque de débordement et de devenir Integer.MIN_VALUE (c'est à dire de négatif). Puis, en soustrayant minCapacity underflows de retour dans un nombre positif.

Ce contrôle permet de s'assurer que l' if n'est pas exécutée. Si le code ont été écrites en if (newCapacity < minCapacity), il serait true dans ce cas (depuis newCapacity est négatif) de sorte que le newCapacity serait forcé d' minCapacity quel que soit le oldCapacity.

Ce cas de dépassement de capacité est gérée par l'autre si. Lors de l' newCapacity a débordé, ce sera true: MAX_ARRAY_SIZE est défini comme Integer.MAX_VALUE - 8 et Integer.MIN_VALUE - (Integer.MAX_VALUE - 8) > 0 est true. L' newCapacity est donc à juste titre traités: hugeCapacity méthode renvoie MAX_ARRAY_SIZE ou Integer.MAX_VALUE.

NB: c'est ce que l' // overflow-conscious code commentaire dans cette méthode, c'est dire.

Answer 2

J'ai trouvé cette explication:

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

J'ai fait une rapide recherche, et il semble que Java est, en effet, en complément à deux en fonction. Néanmoins, permettez-moi de souligner que, en général, ce type de code qui m'inquiète, car je m'attends à ce que, à un moment donné, quelqu'un va venez faire exactement ce que Dmytro proposé; c'est, quelqu'un va changement:

if (a - b > 0)

pour

if (a > b)

et le navire va couler. J'ai, personnellement, comme pour éviter d'obscurités comme la fabrication de dépassement d'entier, un fondement essentiel de mon algorithme, à moins que il y a une bonne raison de le faire. Je voudrais, en général, préfèrent éviter débordement de entièrement et de faire le débordement scénario plus explicite:

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

C'est un bon point.

En ArrayList nous ne pouvons pas le faire (ou au moins pas compatible), parce que ensureCapacity est une API publique et efficacement accepte d'ores et déjà les nombres négatifs que les demandes pour une vision positive de la capacité qui ne peut pas être satisfait.

L'API actuelle est utilisée comme ceci:

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

Si vous voulez éviter les débordements, vous auriez besoin de les changer pour quelque chose moins naturelles comme

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

De toute façon, je vais garder le dépassement conscient de code, mais en ajoutant plus avertissement les commentaires, et de "doublure" d'énormes création de la matrice de sorte que ArrayLists'code ressemble maintenant à:

/**
 * Increases the capacity of this <tt>ArrayList</tt> 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

Dans la version 6 de Java, si vous utilisez l'API:

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

Et newCount débordements (cela devient négatif), if (minCapacity > oldCapacity) retournera false et vous pouvez croient à tort que l' ArrayList a été augmenté par len.

Answer 3

En regardant le code:

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

Si oldCapacity est assez grand, ce débordement, et newCapacity va être un nombre négatif. Une comparaison comme newCapacity < oldCapacity , à tort, d'évaluer true et de la ArrayList échouent à se développer.

Au lieu de cela, le code écrit (newCapacity - minCapacity < 0 renvoie la valeur false) permettra à la valeur négative de l' newCapacity être évaluées dans la ligne suivante, résultant en recalculant newCapacity en invoquant hugeCapacity (newCapacity = hugeCapacity(minCapacity);) afin de permettre l' ArrayList de croître jusqu'à MAX_ARRAY_SIZE.

C'est ce que l' // overflow-conscious code commentaire est d'essayer de communiquer, mais un peu obliquement.

Donc, la ligne du bas, la nouvelle comparaison protège contre l'attribution d'un ArrayList plus grande que la prédéfinis MAX_ARRAY_SIZE tout en lui permettant de grandir jusqu'à cette limite, si nécessaire.