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

jira rest api definition

Question

Estaba leyendo el código fuente ArrayList 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, el grow no existía. Sin ensureCapacity(int) método ensureCapacity(int) usa

if (newCapacity < minCapacity)
    newCapacity = minCapacity;

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

Podría imaginar 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 ( ISUB e IF_ICMPGE ) en lugar de una ( IFGE ).

Answer 1

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 ArrayList no podemos hacer esto (o al menos no de manera 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 el código de ArrayList 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 se desborda newCount (esto se vuelve negativo), if (minCapacity > oldCapacity) devolverá falso y puede suponer erróneamente que len aumentó la ArrayList .

Answer 2

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

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

Answer 3

Mirando el código:

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

Si oldCapacity es bastante grande, esto se desbordará y newCapacity será un número negativo. Una comparación como newCapacity < oldCapacity evaluará incorrectamente true y ArrayList no crecerá.

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

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

Entonces, en MAX_ARRAY_SIZE , la nueva comparación protege contra la asignación de una ArrayList más grande que la MAX_ARRAY_SIZE predefinida, MAX_ARRAY_SIZE tiempo que le permite crecer hasta ese límite si es necesario.

Answer 4

a < b a - b < 0 puede 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 imprimirá a - b < 0 . Lo que sucede es que a < b es claramente falso, pero a - b desborda y se convierte en -1 , lo cual es negativo.

Ahora, dicho esto, considere que la matriz tiene una longitud muy cercana a Integer.MAX_VALUE . El código en ArrayList es 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);

oldCapacity está realmente cerca de Integer.MAX_VALUE por lo que newCapacity (que es oldCapacity + 0.5 * oldCapacity ) puede desbordarse y convertirse en Integer.MIN_VALUE (es decir, negativo). Luego, restando minCapacity desborda nuevamente en un número positivo.

Esta comprobación asegura que el if no se ejecute. Si el código se escribiera como if (newCapacity < minCapacity) , sería true en este caso (dado que newCapacity es negativo), por lo que newCapacity se vería obligado a minCapacity independientemente de la oldCapacity .

Este caso de desbordamiento es manejado por el siguiente if. Cuando newCapacity ha desbordado, esto será true : MAX_ARRAY_SIZE se define como Integer.MAX_VALUE - 8 e Integer.MIN_VALUE - (Integer.MAX_VALUE - 8) > 0 es true . Por lo tanto, newCapacity se maneja correctamente: el método MAX_ARRAY_SIZE devuelve MAX_ARRAY_SIZE o Integer.MAX_VALUE .

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