Diferencia entre si (a – b < 0) y si (a < b)

9 minutos de lectura

avatar de usuario
dejvuth

estaba leyendo Java ArrayList código fuente y noté algunas comparaciones en las declaraciones if.

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

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

En Java 6, grow no existía El método ensureCapacity(int) sin embargo 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?

Podría imaginar que comparar contra 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 código de bytes, esto implicaría dos instrucciones (ISUB y IF_ICMPGE) en lugar de uno (IFGE).

  • @Tunaki ¿Cómo es? if (newCapacity - minCapacity < 0) mejor que if (newCapacity < minCapacity) en términos de prevención de desbordamiento?

    – Eran

    15/10/2015 a las 11:34

  • Me pregunto si el desbordamiento de la señal mencionada es realmente la razón. La resta parece más candidata al desbordamiento. El componente puede decir “esto, sin embargo, no se desbordará”, tal vez ambas variables no sean negativas.

    – Joop Eggen

    15/10/2015 a las 11:43

  • Para tu información, crees que hacer una comparación es más rápido que realizar una “resta completa”. En mi experiencia, a nivel de código de máquina, las comparaciones generalmente se realizan al realizar una resta, descartar el resultado y verificar las banderas resultantes.

    –David Dubois

    15/10/2015 a las 13:56

  • @David Dubois: el OP no asumió que la comparación es más rápida que la resta, pero esa comparación con cero podría ser más rápido que una comparación de dos valores arbitrarios y también asume correctamente que esto no se cumple cuando realiza una resta real primero para obtener un valor para comparar con cero. Todo eso es bastante razonable.

    – Holger

    15/10/2015 a las 16:02

avatar de usuario
Tunaki

a < b y 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 pasa es que a < b es claramente falso, pero a - b se desborda y se convierte -1que es negativo.

Ahora, habiendo dicho eso, considere que la matriz tiene una longitud que es realmente cercana a Integer.MAX_VALUE. El código en ArrayList va 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á muy cerca de Integer.MAX_VALUE asi que newCapacity (cual es oldCapacity + 0.5 * oldCapacity) podría desbordarse y convertirse Integer.MIN_VALUE (es decir, negativo). Luego, restando minCapacity desbordamientos de vuelta a un número positivo.

Esta verificación asegura que el if no se ejecuta. Si el código se escribiera como if (newCapacity < minCapacity)podría ser true en este caso (ya que newCapacity es negativo) por lo que newCapacity se vería obligado a minCapacity a pesar de oldCapacity.

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

NB: esto es lo que // overflow-conscious code comentar en este método es decir.

  • Buena demostración sobre la diferencia entre matemáticas y CS.

    – alcancía

    16/10/2015 a las 18:47

  • @piggybox Yo no diría eso. Esto es matemática. Simplemente no es matemática en Z, sino en una versión de los números enteros módulo 2^32 (con las representaciones canónicas elegidas de manera diferente a lo habitual). Es un sistema matemático adecuado, no solo “lol computadoras y sus peculiaridades”.

    – harold

    17 oct 2015 a las 11:18

  • Hubiera escrito un código que no se desbordara en absoluto.

    -Aleksandr Dubinsky

    20/10/2015 a las 22:06

  • Los procesadores IIRC implementan una instrucción menor que en enteros con signo al hacer a - b y comprobando si el bit superior es un 1. ¿Cómo manejan el desbordamiento?

    – Ky.

    22/10/2015 a las 18:53

  • @BenC.R.Leggiero x86, entre otros, realiza un seguimiento de varias condiciones a través de indicadores de estado en un registro separado para usar con instrucciones condicionales. Este registro tiene bits separados para el signo del resultado, el cero del resultado y si se produjo un exceso o un defecto en la última operación aritmética.

    usuario824425

    11 de noviembre de 2015 a las 0:14

avatar de usuario
Eran

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ítanme señalar que, en general, este tipo de código me preocupa, ya que espero que en algún momento aparezca alguien y haga exactamente lo que sugirió Dmytro; es decir, alguien cambiará:

if (a - b > 0)

a

if (a > b)

y todo el barco se hundirá. Personalmente, me gusta evitar oscuridades 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, de hecho, ya acepta números negativos como solicitudes de una capacidad positiva que no se puede satisfacer.

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 “delineo” la creación de una gran matriz para que
ArrayListEl código de ahora se parece a:

/**
 * 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 newCount se desborda (esto se vuelve negativo), if (minCapacity > oldCapacity) devolverá falso y puede suponer erróneamente que el ArrayList se incrementó en len.

  • Buena idea pero se contradice con la implementación de ensureCapacity; si minCapacity es negativo, nunca se llega a ese punto: se ignora tan silenciosamente como la complicada implementación pretende evitar. Entonces, “no podemos hacer esto” para la compatibilidad de API pública es un argumento extraño como ya lo hicieron. Las únicas personas que llaman que dependen de este comportamiento son las internas.

    – Holger

    15/10/2015 a las 11:58


  • @holger si minCapacity es muy negativo (es decir, resultado de int desbordamiento al agregar el tamaño actual de ArrayList a la cantidad de elementos que desea agregar), minCapacity - elementData.length desbordarse de nuevo y volverse positivo. Así lo entiendo.

    – Eran

    15 de octubre de 2015 a las 12:06

  • @Holger Sin embargo, lo cambiaron nuevamente en Java 8, para if (minCapacity > minExpand)que no entiendo.

    – Eran

    15 de octubre de 2015 a las 12:07

  • si, los dos addAll los métodos son el único caso en el que es relevante, ya que la suma del tamaño actual y la cantidad de elementos nuevos puede desbordarse. Sin embargo, son llamadas internas y el argumento “no podemos cambiarlo porque ensureCapacity es una API pública” es un argumento extraño cuando, de hecho, ensureCapacity ignora los valores negativos. La API de Java 8 no cambió ese comportamiento, todo lo que hace es ignorar las capacidades por debajo de la capacidad predeterminada cuando el ArrayList está en su estado inicial (es decir, inicializado con capacidad predeterminada y aún vacío).

    – Holger

    15 de octubre de 2015 a las 12:12

  • En otras palabras, el razonamiento sobre newcount = count + len es correcto cuando se trata del uso interno, sin embargo, no se aplica al public método ensureCapacity()

    – Holger

    15 de octubre de 2015 a las 12:16

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 el ArrayList dejará de crecer.

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

Esto es lo que // overflow-conscious code comentario está tratando de comunicar, aunque de manera más bien oblicua.

Entonces, en resumidas cuentas, la nueva comparación protege contra la asignación de un ArrayList más grande que el predefinido MAX_ARRAY_SIZE mientras le permite crecer hasta ese límite si es necesario.

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

Si está familiarizado con el código ensamblador x86, considere que (a < b) es implementado por un jge, que se bifurca alrededor del cuerpo de la instrucción if cuando SF = OF. Por otra parte, (a - b < 0) actuará como un jnsque se bifurca cuando SF = 0. Por lo tanto, estos se comportan de manera diferente precisamente cuando OF = 1.

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad