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

252

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).

dejvuth
fonte
35
@Tunaki Como é if (newCapacity - minCapacity < 0)melhor do que if (newCapacity < minCapacity)em termos de prevenção de estouro?
Eran
3
Gostaria de saber se o excesso de sinal mencionado é realmente o motivo. A subtração parece mais uma candidata ao estouro. O componente que pode estar dizendo "isso não transbordará", talvez ambas as variáveis ​​não sejam negativas.
Joop Eggen
12
Para sua informação, você acredita que fazer uma comparação é mais rápido do que realizar uma "subtração completa". Na minha experiência, no nível do código da máquina, geralmente as comparações são feitas executando uma subtração, jogando fora o resultado e verificando os sinalizadores resultantes.
David Dubois
6
@ David Dubois: o OP não assumiu que a comparação é mais rápida que a subtração, mas essa comparação com zero pode ser mais rápida que uma comparação de dois valores arbitrários e também pressupõe corretamente que isso não se aplica quando você está executando uma subtração real primeiro para obter um valor para comparar com zero. Tudo isso é bastante razoável.
Holger

Respostas:

285

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.

Tunaki
fonte
8
Boa demonstração sobre a diferença entre matemática e CS
piggybox
36
@ piggybox Eu não diria isso. Isso é matemática. Não é apenas matemática em Z, mas em uma versão do módulo inteiro 2 ^ 32 (com as representações canônicas escolhidas de maneira diferente do habitual). É um sistema matemático adequado, não apenas "lol computadores e suas peculiaridades".
quer
2
Eu teria escrito um código que não transbordou.
Aleksandr Dubinsky
Os processadores IIRC implementam uma instrução menor que em números inteiros assinados fazendo a - be verificando se o bit superior é a 1. Como eles lidam com estouro?
Ben Leggiero
2
O @ BenC.R.Leggiero x86, entre outros, rastreia várias condições através de sinalizadores de status em um registro separado para uso com instruções condicionais. Esse registrador possui bits separados para o sinal do resultado, ausência de zeros do resultado e se ocorreu excesso ou subfluxo na última operação aritmética.
105

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.

Eran
fonte
2
Boa ideia, mas é contrariada pela implementação deensureCapacity ; se minCapacityfor negativo, você nunca chega a esse ponto - é ignorado tão silenciosamente quanto a implementação complicada pretende impedir. Portanto, "não podemos fazer isso" para compatibilidade com API pública é um argumento estranho, como eles já fizeram. Os únicos chamadores que dependem desse comportamento são os internos.
21915 Holger
1
@ Holger Se minCapacityfor muito negativo (ou seja, resultante do intestouro ao adicionar o tamanho atual da ArrayList ao número de elementos que você deseja adicionar), minCapacity - elementData.lengthtransbordar novamente e tornar-se positivo. É assim que eu entendo.
Eran
1
@ Holger No entanto, eles mudaram novamente no Java 8, para if (minCapacity > minExpand), o que eu não entendo.
Eran
Sim, os dois addAllmétodos são o único caso em que é relevante, pois a soma do tamanho atual e o número de novos elementos podem exceder. No entanto, essas são chamadas internas e o argumento "não podemos alterá-lo porque ensureCapacityé uma API pública" é um argumento estranho quando, de fato, ensureCapacityignora valores negativos. A API do Java 8 não mudou esse comportamento, tudo o que faz é ignorar capacidades abaixo da capacidade padrão quando ArrayListela estiver no estado inicial (isto é, inicializada com a capacidade padrão e ainda vazia).
Holger
Em outras palavras, o raciocínio newcount = count + lené correto quando se trata do uso interno, no entanto, não se aplica ao publicmétodo ensureCapacity()...
Holger
19

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.

Erick G. Hagstrom
fonte
1

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.

Doradus
fonte