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

252

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

dejvuth
źródło
35
@Tunaki W jaki sposób jest if (newCapacity - minCapacity < 0)lepsze niż if (newCapacity < minCapacity)zapobieganie przepełnieniu?
Eran
3
Zastanawiam się, czy wspomniany przepełnienie znaku jest rzeczywiście przyczyną. Odejmowanie wydaje się bardziej kandydatem na przepełnienie. Składnik może powiedzieć „to się jednak nie przepełni”, być może obie zmienne są nieujemne.
Joop Eggen
12
Do Twojej dyspozycji jest przekonanie, że porównanie jest szybsze niż „całkowite odjęcie”. Z mojego doświadczenia wynika, że ​​na poziomie kodu maszynowego zwykle dokonuje się porównań, wykonując odejmowanie, wyrzucając wynik i sprawdzając powstałe flagi.
David Dubois,
6
@David Dubois: OP nie założył, że porównanie jest szybsze niż odejmowanie, ale to porównanie z zerem może być szybsze niż porównanie dwóch dowolnych wartości, a także poprawnie zakłada, że ​​nie zachodzi to, gdy najpierw wykonuje się faktyczne odejmowanie w celu uzyskania wartości do porównania z zerem. To wszystko całkiem rozsądne.
Holger,

Odpowiedzi:

285

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.

Tunaki
źródło
8
Dobre demo na temat różnicy między matematyką a CS
piggybox
36
@piggybox Nie powiedziałbym tego. To jest matematyka. To po prostu nie matematyka w Z, ale w wersji liczb całkowitych modulo 2 ^ 32 (z reprezentacjami kanonicznymi wybranymi inaczej niż zwykle). To właściwy system matematyczny, nie tylko „komputery lol i ich dziwactwa”.
Harold
2
Napisałbym kod, który wcale się nie przepełnił.
Aleksandr Dubinsky,
Procesory IIRC implementują mniej niż instrukcję na liczbach całkowitych ze a - bznakiem, wykonując i sprawdzając, czy górny bit to 1. Jak radzą sobie z przepełnieniem?
Ben Leggiero,
2
@ BenC.R. Leggiero x86, między innymi, śledzi różne warunki poprzez flagi statusu w oddzielnym rejestrze do użycia z instrukcjami warunkowymi. Rejestr ten ma osobne bity dla znaku wyniku, zerowego wyniku i tego, czy w ostatniej operacji arytmetycznej wystąpiło przepełnienie / niedopełnienie.
105

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.

Eran
źródło
2
Fajny pomysł, ale jest sprzeczny z wdrożeniemensureCapacity ; jeśli minCapacityjest negatywne, nigdy nie dochodzisz do tego punktu - jest tak samo cicho ignorowane, jak skomplikowane wdrożenie udaje, aby temu zapobiec. Zatem „nie możemy tego zrobić” dla zgodności publicznego interfejsu API jest dziwnym argumentem, tak jak już to zrobili. Jedynymi osobami wywołującymi to zachowanie są osoby wewnętrzne.
Holger
1
@Holger If minCapacityjest bardzo ujemny (tj. Wynika z intprzepełnienia podczas dodawania bieżącego rozmiaru ArrayList do liczby elementów, które chcesz dodać), minCapacity - elementData.lengthaby ponownie przepełnić i stać się dodatni. Tak to rozumiem.
Eran
1
@Holger Jednak zmienili go ponownie w Javie 8 na if (minCapacity > minExpand), czego nie rozumiem.
Eran
Tak, te dwie addAllmetody są jedynym przypadkiem, w którym jest to istotne, ponieważ suma bieżącego rozmiaru i liczby nowych elementów może się przepełnić. Niemniej jednak są to wywołania wewnętrzne, a argument „nie możemy tego zmienić, ponieważ ensureCapacityjest publicznym interfejsem API” jest dziwnym argumentem, gdy w rzeczywistości ensureCapacityignoruje wartości ujemne. Interfejs API Java 8 nie zmienił tego zachowania, wszystko to ignoruje pojemności poniżej pojemności domyślnej, gdy ArrayListjest w stanie początkowym (tj. Zainicjowany z domyślną pojemnością i nadal pusty).
Holger
Innymi słowy, uzasadnienie dotyczące newcount = count + lenzastosowania wewnętrznego jest poprawne, jednak nie dotyczy ono publicmetody ensureCapacity()
Holger
19

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.

Erick G. Hagstrom
źródło
1

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.

Doradus
źródło