Unterschied zwischen if (a - b <0) und if (a <b)

252

Ich las Javas ArrayListQuellcode und bemerkte einige Vergleiche in if-Anweisungen.

In Java 7 werden die Verfahren grow(int)Verwendungen

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

In Java 6 grownicht vorhanden. Die Methode verwendet ensureCapacity(int)jedoch

if (newCapacity < minCapacity)
    newCapacity = minCapacity;

Was war der Grund für die Änderung? War es ein Leistungsproblem oder nur ein Stil?

Ich könnte mir vorstellen, dass der Vergleich mit Null schneller ist, aber eine vollständige Subtraktion durchzuführen, um zu überprüfen, ob sie negativ ist, scheint mir ein bisschen übertrieben. Auch in Bezug auf den Bytecode würde dies zwei Anweisungen ( ISUBund IF_ICMPGE) anstelle von einer ( IFGE) beinhalten.

Dejvuth
quelle
35
@Tunaki Wie ist es if (newCapacity - minCapacity < 0)besser als if (newCapacity < minCapacity)Überlauf zu verhindern?
Eran
3
Ich frage mich, ob der erwähnte Zeichenüberlauf tatsächlich der Grund ist. Die Subtraktion scheint eher ein Kandidat für einen Überlauf zu sein. Die Komponente sagt möglicherweise "dies wird trotzdem nicht überlaufen", möglicherweise sind beide Variablen nicht negativ.
Joop Eggen
12
Zu Ihrer Information, Sie glauben, dass ein Vergleich schneller ist als eine "vollständige Subtraktion". Nach meiner Erfahrung werden Vergleiche auf der Ebene des Maschinencodes normalerweise durchgeführt, indem eine Subtraktion durchgeführt, das Ergebnis weggeworfen und die resultierenden Flags überprüft werden.
David Dubois
6
@ David Dubois: Das OP hat nicht angenommen, dass der Vergleich schneller als die Subtraktion ist, aber der Vergleich mit Null ist möglicherweise schneller als ein Vergleich zweier beliebiger Werte und geht auch korrekt davon aus, dass dies nicht gilt, wenn Sie zuerst eine tatsächliche Subtraktion durchführen um einen Wert zu erhalten, der mit Null verglichen werden kann. Das ist alles ganz vernünftig.
Holger

Antworten:

285

a < bund a - b < 0kann zwei verschiedene Dinge bedeuten. Betrachten Sie den folgenden Code:

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

Beim Ausführen wird nur gedruckt a - b < 0. Was passiert ist, dass a < bdas eindeutig falsch ist, aber a - büberläuft und wird -1, was negativ ist.

Bedenken Sie nun, dass das Array eine Länge hat, die wirklich nahe liegt Integer.MAX_VALUE. Der Code in ArrayListlautet wie folgt:

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

oldCapacityist wirklich nah an Integer.MAX_VALUEso newCapacity(was ist oldCapacity + 0.5 * oldCapacity) könnte überlaufen und werden Integer.MIN_VALUE(dh negativ). Dann subtrahiert man die minCapacity Unterläufe zurück in eine positive Zahl.

Diese Prüfung stellt sicher, dass die if nicht ausgeführt wird. Wenn der Code als geschrieben if (newCapacity < minCapacity)wäre, wäre es truein diesem Fall (da newCapacityist negativ), so dass der newCapacitygezwungen wäre, minCapacityunabhängig von der oldCapacity.

Dieser Überlauffall wird vom nächsten if behandelt. Wenn newCapacityübergelaufen ist, ist dies true: MAX_ARRAY_SIZEdefiniert alsInteger.MAX_VALUE - 8 und Integer.MIN_VALUE - (Integer.MAX_VALUE - 8) > 0ist true. Das newCapacitywird daher richtig gehandhabt: hugeCapacityMethode gibt MAX_ARRAY_SIZEoder zurück Integer.MAX_VALUE.

NB: das ist was die // overflow-conscious code Kommentar in dieser Methode sagt.

Tunaki
quelle
8
Gute Demo über den Unterschied zwischen Mathe und CS
Piggybox
36
@piggybox würde ich nicht sagen. Das ist Mathe. Es ist nur keine Mathematik in Z, sondern in einer Version der ganzen Zahlen modulo 2 ^ 32 (wobei die kanonischen Darstellungen anders als gewöhnlich gewählt werden). Es ist ein richtiges mathematisches System, nicht nur "lol Computer und ihre Macken".
Harold
2
Ich hätte Code geschrieben, der überhaupt nicht übergelaufen ist.
Aleksandr Dubinsky
IIRC-Prozessoren implementieren eine Anweisung kleiner als für vorzeichenbehaftete Ganzzahlen, indem sie ausführen a - bund prüfen, ob das oberste Bit a ist 1. Wie gehen sie mit Überlauf um?
Ben Leggiero
2
@ BenC.R.Leggiero x86 verfolgt unter anderem verschiedene Bedingungen durch Statusflags in einem separaten Register zur Verwendung mit bedingten Anweisungen. Dieses Register hat separate Bits für das Vorzeichen des Ergebnisses, die Nullheit des Ergebnisses und ob bei der letzten arithmetischen Operation ein Über- / Unterlauf aufgetreten ist.
105

Ich habe diese Erklärung gefunden :

Am Dienstag, den 9. März 2010 um 03:02 Uhr schrieb Kevin L. Stern:

Ich habe eine schnelle Suche durchgeführt und es scheint, dass Java tatsächlich auf zwei Komplementen basiert. Gestatten Sie mir dennoch, darauf hinzuweisen, dass mich diese Art von Code im Allgemeinen beunruhigt, da ich davon ausgehe, dass irgendwann jemand vorbeikommt und genau das tut, was Dmytro vorgeschlagen hat. das heißt, jemand wird sich ändern:

if (a - b > 0)

zu

if (a > b)

und das ganze Schiff wird sinken. Ich persönlich möchte Unklarheiten vermeiden, z. B. den Überlauf von Ganzzahlen zu einer wesentlichen Grundlage für meinen Algorithmus zu machen, es sei denn, es gibt einen guten Grund dafür. Im Allgemeinen würde ich es vorziehen, einen Überlauf insgesamt zu vermeiden und das Überlaufszenario deutlicher zu machen:

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

Das ist ein guter Punkt.

In können ArrayListwir das nicht (oder zumindest nicht kompatibel) machen, weil ensureCapacity es sich um eine öffentliche API handelt und negative Zahlen effektiv bereits als Anforderungen für eine positive Kapazität akzeptiert, die nicht erfüllt werden kann.

Die aktuelle API wird folgendermaßen verwendet:

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

Wenn Sie einen Überlauf vermeiden möchten, müssen Sie zu etwas weniger Natürlichem wechseln

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

Wie auch immer, ich behalte den überlaufbewussten Code bei, füge aber weitere Warnkommentare hinzu und "skizziere" die Erstellung riesiger Arrays, sodass der ArrayListCode jetzt wie folgt aussieht:

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

Martin

Wenn Sie in Java 6 die API verwenden als:

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

Und newCountÜberläufe (dies wird negativ) if (minCapacity > oldCapacity)geben false zurück und Sie können fälschlicherweise annehmen, dass der Wert um ArrayListerhöht wurde len.

Eran
quelle
2
Gute Idee, aber es wird durch die Umsetzung vonensureCapacity widersprochen ; Wenn dies minCapacitynegativ ist, gelangen Sie nie an diesen Punkt - es wird genauso stillschweigend ignoriert, wie die komplizierte Implementierung vorgibt, dies zu verhindern. "Wir können dies nicht tun" für die Kompatibilität mit öffentlichen APIs ist daher ein seltsames Argument, wie sie es bereits getan haben. Die einzigen Anrufer, die sich auf dieses Verhalten verlassen, sind die internen.
Holger
1
@Holger If minCapacityist sehr negativ (dh resultiert aus einem intÜberlauf beim Hinzufügen der aktuellen Größe der ArrayList zur Anzahl der Elemente, die Sie hinzufügen möchten ), minCapacity - elementData.lengthum erneut überzulaufen und positiv zu werden. So verstehe ich es.
Eran
1
@Holger Allerdings haben sie es in Java 8 wieder geändert if (minCapacity > minExpand), was ich nicht verstehe.
Eran
Ja, die beiden addAllMethoden sind der einzige Fall, in dem dies relevant ist, da die Summe aus aktueller Größe und Anzahl neuer Elemente überlaufen kann. Dies sind jedoch interne Aufrufe, und das Argument „Wir können es nicht ändern, weil ensureCapacityes sich um eine öffentliche API handelt“ ist ein seltsames Argument, ensureCapacityobwohl negative Werte tatsächlich ignoriert werden. Die Java 8-API hat dieses Verhalten nicht geändert. Sie ignoriert lediglich Kapazitäten unterhalb der Standardkapazität, wenn ArrayListsie sich im Anfangszustand befindet (dh mit Standardkapazität initialisiert und noch leer).
Holger
Mit anderen Worten, die Argumentation newcount = count + lenist richtig, wenn es um den internen Gebrauch geht, sie gilt jedoch nicht für die publicMethode ensureCapacity()
Holger
19

Den Code betrachten:

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

Wenn oldCapacityes ziemlich groß ist, läuft es über und newCapacityist eine negative Zahl. Ein Vergleich wie newCapacity < oldCapacitywird falsch bewertet trueund der ArrayListwird nicht wachsen.

Stattdessen ermöglicht der geschriebene Code ( newCapacity - minCapacity < 0gibt false zurück), dass der negative Wert von newCapacityin der nächsten Zeile weiter ausgewertet wird, was zu einer Neuberechnung newCapacitydurch Aufrufen von hugeCapacity( newCapacity = hugeCapacity(minCapacity);) führt, damit der Wert bis zu ArrayListwachsen kann MAX_ARRAY_SIZE.

Dies ist, was der // overflow-conscious codeKommentar zu kommunizieren versucht, wenn auch eher schräg.

Unterm Strich schützt der neue Vergleich also davor, einen ArrayListgrößeren als den vordefinierten zuzuweisenMAX_ARRAY_SIZE während es bei Bedarf bis zu diesem Grenzwert wachsen kann.

Erick G. Hagstrom
quelle
1

Die beiden Formen verhalten sich genau gleich, es sei denn, der Ausdruck a - bläuft über. In diesem Fall sind sie entgegengesetzt. Wenn aes ein großes Negativ und bein großes Positiv ist, dann (a < b)ist dies eindeutig wahr, wird aber a - büberlaufen, um positiv zu werden(a - b < 0) ist daher falsch.

Wenn Sie mit x86-Assemblycode vertraut sind, beachten Sie, dass dieser (a < b)durch a implementiert wird jge, der sich um den Hauptteil der if-Anweisung verzweigt, wenn SF = OF. Auf der anderen Seite verhält es sich (a - b < 0)wie a jns, das sich verzweigt, wenn SF = 0. Daher verhalten sich diese genau anders, wenn OF = 1.

Doradus
quelle