Różnica między if (a - b <0) a if (a <b)

Czytałem ArrayListkod źródłowy Javy i zauważyłem pewne porównania w instrukcjach if.

W Javie 7 metoda grow(int)wykorzystuje

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

W Javie 6 grownie istniał. Metoda ensureCapacity(int)jednak wykorzystuje

if (newCapacity < minCapacity)
    newCapacity = minCapacity;

Jaki był powód zmiany? Czy to był problem z wydajnością, czy tylko styl?

Mogę sobie wyobrazić, że porównywanie z zerem jest szybsze, ale wykonanie pełnego odejmowania tylko po to, aby sprawdzić, czy jest ujemne, wydaje mi się nieco przesadne. Również pod względem kodu bajtowego wymagałoby to dwóch instrukcji ( ISUBi IF_ICMPGE) zamiast jednej ( IFGE).

a < bi a - b < 0może oznaczać dwie różne rzeczy. Rozważ następujący kod:

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

Po uruchomieniu zostanie to wydrukowane a - b < 0. To, co się dzieje, a < bjest wyraźnie fałszywe, ale a - bprzelewa się i staje -1, co jest negatywne.

Powiedziawszy to, zastanów się, że tablica ma długość, która jest naprawdę bliska Integer.MAX_VALUE. Kod ArrayListwygląda następująco:

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

oldCapacityjest naprawdę blisko, Integer.MAX_VALUEwięc newCapacity(który jest oldCapacity + 0.5 * oldCapacity) może się przepełnić i stać Integer.MIN_VALUE(tj. ujemny). Następnie odejmując minCapacity niedomiar z powrotem do liczby dodatniej.

To sprawdzenie zapewnia, że ifnie zostanie wykonane. Gdyby kod został napisany jako if (newCapacity < minCapacity), byłby truew tym przypadku (ponieważ newCapacityjest ujemny), więc newCapacitybyłby zmuszony do minCapacityniezależnie od oldCapacity.

Ten przypadek przepełnienia jest obsługiwany przez następny if. Kiedy newCapacitysię przepełni, będzie to true: MAX_ARRAY_SIZEjest zdefiniowane jako Integer.MAX_VALUE - 8i Integer.MIN_VALUE - (Integer.MAX_VALUE - 8) > 0jest true. Dlatego newCapacityjest odpowiednio obsługiwane: hugeCapacitymetoda zwraca MAX_ARRAY_SIZElub Integer.MAX_VALUE.

Uwaga: tak mówi // overflow-conscious codekomentarz w tej metodzie.

Znalazłem to wyjaśnienie :

W wtorek, 9 marca 2010 o 03:02, Kevin L. Stern napisał:

Przeprowadziłem szybkie wyszukiwanie i wydaje się, że Java jest rzeczywiście oparta na uzupełnieniu dwóch. Niemniej jednak proszę pozwolić mi zaznaczyć, że generalnie ten rodzaj kodu martwi mnie, ponieważ w pełni oczekuję, że w pewnym momencie ktoś przyjdzie i zrobi dokładnie to, co zasugerował Dmytro; to znaczy, ktoś się zmieni:

if (a - b > 0)

do

if (a > b)

i cały statek zatonie. Osobiście lubię unikać niejasności, takich jak uczynienie z przepełnienia liczb całkowitych niezbędnej podstawy dla mojego algorytmu, chyba że istnieje ku temu dobry powód. Zasadniczo wolałbym całkowicie uniknąć przepełnienia i uściślić scenariusz przepełnienia:

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

To dobra uwaga.

W ArrayListnie możemy tego zrobić (lub przynajmniej nie kompatybilność), ponieważ ensureCapacityjest publiczne API i skutecznie już akceptuje liczb ujemnych jako wnioski o pozytywnym charakterze, które nie mogą być spełnione.

Bieżący interfejs API jest używany w następujący sposób:

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

Jeśli chcesz uniknąć przepełnienia, musisz zmienić na coś mniej naturalnego

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

W każdym razie trzymam kod świadomy przepełnienia, ale dodaję więcej ostrzeżeń i dodam do kreacji ogromną tablicę, aby ArrayListkod wyglądał teraz tak:

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

Jaskółka oknówka

W Javie 6, jeśli używasz interfejsu API jako:

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

I newCountprzepełnienia (to staje się ujemna), if (minCapacity > oldCapacity)zwróci false i może błędnie zakładają, że ArrayListzostała zwiększona o len.

Patrząc na kod:

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

Jeśli oldCapacityjest dość duży, to się przepełni i newCapacitybędzie liczbą ujemną. Takie porównanie newCapacity < oldCapacityźle oceni truei ArrayListnie będzie rosło.

Zamiast tego zapisany kod ( newCapacity - minCapacity < 0zwraca false) pozwoli na newCapacitydalszą ocenę wartości ujemnej w następnym wierszu, co spowoduje ponowne obliczenie newCapacityprzez wywołanie hugeCapacity( newCapacity = hugeCapacity(minCapacity);), aby umożliwić ArrayListwzrost MAX_ARRAY_SIZE.

To właśnie // overflow-conscious codekomentarz próbuje przekazać, choć raczej skośnie.

Podsumowując , nowe porównanie chroni przed przydzieleniem wartości ArrayListwiększej niż wstępnie zdefiniowana, MAX_ARRAY_SIZEjednocześnie umożliwiając jej wzrost do tego limitu w razie potrzeby.

Obie formy zachowują się dokładnie tak samo, chyba że wyrażenie się a - bprzepełni, w którym to przypadku są przeciwne. Jeśli ajest dużym ujemnym i bjest dużym dodatnim, to (a < b)jest to oczywiście prawda, ale a - bprzepełni się, aby stać się dodatnim, więc (a - b < 0)jest fałszywe.

Jeśli znasz kod zestawu x86, zastanów się, że (a < b)jest on implementowany przez a jge, który rozgałęzia się wokół treści instrukcji if, gdy SF = OF. Z drugiej strony (a - b < 0)będzie zachowywał się jak a jns, który rozgałęzia się, gdy SF = 0. Stąd zachowują się inaczej dokładnie, gdy OF = 1.