Diferencia entre if (a - b <0) y if (a <b)

Estaba leyendo el ArrayListcódigo fuente de Java y noté algunas comparaciones en sentencias if.

En Java 7, el método grow(int)usa

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

En Java 6, growno existía. Sin ensureCapacity(int)embargo, el método utiliza

if (newCapacity < minCapacity)
    newCapacity = minCapacity;

¿Cuál fue la razón detrás del cambio? ¿Fue un problema de rendimiento o simplemente un estilo?

Me imagino que comparar con cero es más rápido, pero realizar una resta completa solo para verificar si es negativo me parece un poco exagerado. También en términos de bytecode, esto implicaría dos instrucciones ( ISUBy IF_ICMPGE) en lugar de una ( IFGE).

a < by a - b < 0puede significar dos cosas diferentes. Considere el siguiente código:

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");
}

Cuando se ejecuta, esto solo se imprimirá a - b < 0. Lo que sucede es que a < bes claramente falso, pero se a - bdesborda y se vuelve -1negativo.

Ahora, dicho esto, considere que la matriz tiene una longitud muy cercana Integer.MAX_VALUE. El código en ArrayListva así:

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

oldCapacityestá realmente cerca de Integer.MAX_VALUElo newCapacityque (que es oldCapacity + 0.5 * oldCapacity) podría desbordarse y volverse Integer.MIN_VALUE(es decir, negativo). Luego, restando los minCapacity subflujos nuevamente en un número positivo.

Esta verificación asegura que ifno se ejecute. Si el código se escribiera comoif (newCapacity < minCapacity) , sería trueen este caso (ya que newCapacityes negativo), por lo que newCapacityse vería obligado a hacerlo minCapacityindependientemente de oldCapacity.

Este caso de desbordamiento es manejado por el siguiente if. Cuando se newCapacityha desbordado, esto será true: MAX_ARRAY_SIZEse define como Integer.MAX_VALUE - 8y Integer.MIN_VALUE - (Integer.MAX_VALUE - 8) > 0estrue . Por newCapacitylo tanto, se maneja correctamente: el hugeCapacitymétodo devuelve MAX_ARRAY_SIZEo Integer.MAX_VALUE.

NB: esto es lo que dice el // overflow-conscious codecomentario en este método.

Encontré esta explicación :

El martes 9 de marzo de 2010 a las 03:02, Kevin L. Stern escribió:

Hice una búsqueda rápida y parece que Java está basado en el complemento de dos. No obstante, permítame señalar que, en general, este tipo de código me preocupa, ya que espero que en algún momento alguien venga y haga exactamente lo que Dmytro sugirió; es decir, alguien cambiará:

if (a - b > 0)

a

if (a > b)

y toda la nave se hundirá. Personalmente, me gusta evitar las obscuridades, como hacer que el desbordamiento de enteros sea una base esencial para mi algoritmo, a menos que haya una buena razón para hacerlo. En general, preferiría evitar el desbordamiento por completo y hacer que el escenario de desbordamiento sea más explícito:

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

Es un buen punto.

En ArrayListno podemos hacer esto (o al menos no es compatible), porque ensureCapacity es una API pública y efectivamente ya acepta números negativos como solicitudes de una capacidad positiva que no puede satisfacerse.

La API actual se usa así:

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

Si desea evitar el desbordamiento, deberá cambiar a algo menos natural como

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

De todos modos, mantengo el código consciente del desbordamiento, pero agrego más comentarios de advertencia y crea una gran variedad de "esquemas" para que ArrayListel código ahora se vea así:

/**
 * 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 regenerado.

Martín

En Java 6, si usa la API como:

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

Y los newCountdesbordamientos (esto se vuelve negativo), if (minCapacity > oldCapacity)devolverán falso y puede suponer erróneamente que ArrayListse incrementó en len.

Mirando el código:

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

Si oldCapacityes bastante grande, se desbordará y newCapacityserá un número negativo. Una comparación como newCapacity < oldCapacityse evaluará incorrectamente truey ArrayListno crecerá.

En cambio, el código tal como está escrito ( newCapacity - minCapacity < 0devuelve falso) permitirá que el valor negativo de newCapacityse evalúe más en la siguiente línea, lo que resulta en recalcular newCapacityinvocando hugeCapacity( newCapacity = hugeCapacity(minCapacity);) para permitir ArrayListque crezca MAX_ARRAY_SIZE.

Esto es lo que el // overflow-conscious codecomentario intenta comunicar, aunque de manera bastante oblicua.

Por lo tanto, en resumen, la nueva comparación protege contra la asignación de un valor ArrayListmayor que el predefinido, al MAX_ARRAY_SIZEtiempo que le permite crecer hasta ese límite si es necesario.

Las dos formas se comportan exactamente igual a menos que la expresión se a - bdesborde, en cuyo caso son opuestas. Si aes un gran negativo, y bes un gran positivo, entonces (a < b)es claramente cierto, pero a - bse desbordará para volverse positivo, por lo que (a - b < 0)es falso.

Si está familiarizado con el código de ensamblaje x86, considere que (a < b)lo implementa a jge, que se ramifica alrededor del cuerpo de la instrucción if cuando SF = OF. Por otro lado, (a - b < 0)actuará como a jns, que se ramifica cuando SF = 0. Por lo tanto, estos se comportan de manera diferente precisamente cuando OF = 1.