Diferença entre if (a - b <0) e if (a <b)

Eu estava lendo o ArrayListcódigo fonte do Java e notei algumas comparações nas instruções if.

No Java 7, o método grow(int)usa

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

No Java 6, grownão existia. O método, ensureCapacity(int)no entanto, usa

if (newCapacity < minCapacity)
    newCapacity = minCapacity;

Qual foi o motivo por trás da mudança? Foi um problema de desempenho ou apenas um estilo?

Eu poderia imaginar que comparar com zero é mais rápido, mas realizar uma subtração completa apenas para verificar se é negativo parece um pouco exagero para mim. Também em termos de bytecode, isso envolveria duas instruções ( ISUBe IF_ICMPGE) em vez de uma ( IFGE).

a < be a - b < 0pode significar duas coisas diferentes. Considere o seguinte 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");
}

Quando executado, isso será impresso apenas a - b < 0. O que acontece é que a < bé claramente falso, mas a - btransborda e se torna -1negativo.

Agora, tendo dito isso, considere que a matriz tem um comprimento muito próximo Integer.MAX_VALUE. O código ArrayListé assim:

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 próximo de Integer.MAX_VALUEque newCapacity(que é oldCapacity + 0.5 * oldCapacity) pode transbordar e se tornar Integer.MIN_VALUE(ou seja, negativo). Subtraindo minCapacity subfluxos de volta para um número positivo.

Essa verificação garante que o ifnão seja executado. Se o código fosse escrito como if (newCapacity < minCapacity), seria trueneste caso (uma vez que newCapacityé negativo) e, portanto, newCapacityseria forçado a minCapacityindependentemente do oldCapacity.

Esse caso de estouro é tratado pelo próximo if. Quando newCapacityestourou, será true: MAX_ARRAY_SIZEé definido como Integer.MAX_VALUE - 8e Integer.MIN_VALUE - (Integer.MAX_VALUE - 8) > 0é true. A newCapacityé, por conseguinte, tratadas com razão: hugeCapacitymétodo retorna MAX_ARRAY_SIZEou Integer.MAX_VALUE.

Nota: é o que o // overflow-conscious codecomentário deste método está dizendo.

Eu encontrei esta explicação :

Em terça-feira, 9 de março de 2010 às 03:02, Kevin L. Stern escreveu:

Eu fiz uma pesquisa rápida e parece que o Java é de fato baseado em dois. No entanto, permita-me salientar que, em geral, esse tipo de código me preocupa, pois espero que em algum momento alguém venha e faça exatamente o que o Dmytro sugeriu; isto é, alguém mudará:

if (a - b > 0)

para

if (a > b)

e todo o navio afundará. Pessoalmente, gosto de evitar obscuridades, como tornar o número inteiro excedente uma base essencial para o meu algoritmo, a menos que haja uma boa razão para fazê-lo. Em geral, eu preferiria evitar o estouro por completo e tornar o cenário de estouro mais explícito:

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

É um bom argumento.

Em ArrayListnós não podemos fazer isso (ou pelo menos não a compatibilidade), porque ensureCapacityé uma API pública e eficaz já aceita números negativos como os pedidos para uma capacidade positivo que não pode ser satisfeita.

A API atual é usada assim:

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

Se você quiser evitar transbordamentos, precisará mudar para algo menos natural como

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

De qualquer forma, estou mantendo o código com excesso de consciência, mas adicionando mais comentários de aviso e "delineando" a enorme criação de matriz para que ArrayListo código agora se pareça com:

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

Martin

No Java 6, se você usar a API como:

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

E os newCountestouros (isso se torna negativo) if (minCapacity > oldCapacity)retornará falso e você pode assumir, por engano, que o ArrayListaumento foi de len.

Olhando para o código:

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

Se oldCapacityfor muito grande, isso excederá e newCapacityserá um número negativo. Uma comparação como newCapacity < oldCapacityserá avaliada incorretamente truee a ArrayListfalha no crescimento.

Em vez disso, o código gravado ( newCapacity - minCapacity < 0retorna false) permitirá que o valor negativo newCapacityseja avaliado ainda mais na próxima linha, resultando em um novo cálculo newCapacityinvocando hugeCapacity( newCapacity = hugeCapacity(minCapacity);) para permitir que o valor ArrayListcresça MAX_ARRAY_SIZE.

É isso que o // overflow-conscious codecomentário está tentando comunicar, embora de maneira oblíqua.

Portanto, a nova comparação protege contra a alocação de um valor ArrayListmaior que o predefinido MAX_ARRAY_SIZE, permitindo que ele cresça até esse limite, se necessário.

As duas formas se comportam exatamente da mesma forma, a menos que a expressão a - btransborde, caso em que são opostas. Se aé um grande negativo e bé um grande positivo, então (a < b)é claramente verdade, mas a - btransbordará para se tornar positivo, o que (a - b < 0)é falso.

Se você estiver familiarizado com o código de montagem x86, considere que ele (a < b)é implementado por a jge, que se ramifica no corpo da instrução if quando SF = OF. Por outro lado, (a - b < 0)agirá como a jns, que se ramifica quando SF = 0. Portanto, eles se comportam de maneira diferente com precisão quando OF = 1.