Perbedaan antara if (a - b <0) dan if (a <b)

Saya sedang membaca Java ArrayList kode sumber dan melihat beberapa perbandingan dalam pernyataan if.

Di Java 7, metode ini grow(int)menggunakan

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

Di Java 6, growtidak ada. ensureCapacity(int)Namun metode ini menggunakan

if (newCapacity < minCapacity)
    newCapacity = minCapacity;

Apa alasan di balik perubahan itu? Apakah itu masalah kinerja atau hanya gaya?

Saya bisa membayangkan bahwa membandingkan dengan nol lebih cepat, tetapi melakukan pengurangan lengkap hanya untuk memeriksa apakah itu negatif tampaknya sedikit berlebihan bagi saya. Juga dalam hal bytecode, ini akan melibatkan dua instruksi ( ISUBdan IF_ICMPGE) bukannya satu ( IFGE).

a < bdan a - b < 0dapat berarti dua hal yang berbeda. Pertimbangkan kode berikut:

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

Saat dijalankan, ini hanya akan dicetak a - b < 0. Apa yang terjadi adalah yang a < bjelas salah, tetapi a - bmeluap dan menjadi -1, yang negatif.

Sekarang, setelah mengatakan itu, pertimbangkan bahwa array memiliki panjang yang sangat dekat Integer.MAX_VALUE. Kode dalam ArrayListseperti ini:

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

oldCapacitysangat dekat Integer.MAX_VALUEsehingga newCapacity(yang oldCapacity + 0.5 * oldCapacity) mungkin meluap dan menjadi Integer.MIN_VALUE(yaitu negatif). Kemudian, kurangi minCapacity arus balik kembali ke angka positif.

Pemeriksaan ini memastikan bahwa iftidak dieksekusi. Jika kode ditulis sebagai if (newCapacity < minCapacity), maka akan truedalam hal ini (karena newCapacitynegatif) jadinewCapacity akan dipaksa untuk minCapacityterlepas dari oldCapacity.

Case overflow ini ditangani oleh if berikutnya. Ketika newCapacitytelah meluap, ini akan true: MAX_ARRAY_SIZEdidefinisikan sebagai Integer.MAX_VALUE - 8dan Integer.MIN_VALUE - (Integer.MAX_VALUE - 8) > 0adalah true. Karena newCapacityitu ditangani dengan benar: hugeCapacitymetode mengembalikanMAX_ARRAY_SIZE atau Integer.MAX_VALUE.

NB: inilah yang dikatakan oleh // overflow-conscious codekomentar dalam metode ini.

Saya menemukan penjelasan ini :

Pada Selasa, 9 Maret 2010 pukul 03:02, Kevin L. Stern menulis:

Saya melakukan pencarian cepat dan tampaknya Java memang berdasarkan dua komplemen. Meskipun demikian, izinkan saya menunjukkan bahwa, secara umum, jenis kode ini membuat saya khawatir karena saya sepenuhnya berharap bahwa pada suatu saat seseorang akan datang dan melakukan persis seperti yang disarankan Dmytro; yaitu seseorang akan berubah:

if (a - b > 0)

untuk

if (a > b)

dan seluruh kapal akan tenggelam. Saya, secara pribadi, ingin menghindari ketidakjelasan seperti membuat integer overflow sebagai dasar penting untuk algoritme saya kecuali ada alasan bagus untuk melakukannya. Secara umum, saya lebih suka untuk menghindari overflow sama sekali dan membuat skenario overflow lebih eksplisit:

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

Ini poin yang bagus.

Di ArrayListkita tidak dapat melakukan ini (atau setidaknya tidak kompatibel), karena ensureCapacity merupakan API publik dan secara efektif sudah menerima angka negatif sebagai permintaan kapasitas positif yang tidak dapat dipenuhi.

API saat ini digunakan seperti ini:

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

Jika Anda ingin menghindari overflow, Anda perlu mengubah sesuatu yang kurang alami

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

Pokoknya, saya menjaga kode overflow-aware, tetapi menambahkan lebih banyak komentar peringatan, dan "out-lining" pembuatan array besar sehingga ArrayListkode sekarang terlihat seperti:

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

Martin

Di Java 6, jika Anda menggunakan API sebagai:

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

Dan newCountmelimpah (ini menjadi negatif), if (minCapacity > oldCapacity)akan kembali salah dan Anda mungkin salah berasumsi bahwa ArrayListitu meningkat len.

Melihat kode:

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

Jika oldCapacitycukup besar, ini akan meluap, dan newCapacityakan menjadi angka negatif. Perbandingan seperti newCapacity < oldCapacityakan salah mengevaluasi truedan ArrayListakan gagal tumbuh.

Sebagai gantinya, kode yang ditulis ( newCapacity - minCapacity < 0mengembalikan salah) akan memungkinkan nilai negatif newCapacityuntuk dievaluasi lebih lanjut di baris berikutnya, menghasilkan penghitungan ulang newCapacitydengan memanggil hugeCapacity( newCapacity = hugeCapacity(minCapacity);) untuk memungkinkan untuk ArrayListtumbuh hingga MAX_ARRAY_SIZE.

Inilah yang // overflow-conscious codecoba dikomentari oleh komentar itu, meskipun agak tidak jelas.

Jadi, intinya, perbandingan baru melindungi terhadap pengalokasian yang ArrayListlebih besar dari yang telah ditetapkan MAX_ARRAY_SIZEsementara memungkinkannya tumbuh hingga batas itu jika diperlukan.

Kedua bentuk berperilaku persis sama kecuali jika ekspresi a - bmeluap, dalam hal ini mereka bertolak belakang. Jika anegatif besar, dan bpositif besar, maka (a < b)jelas benar, tetapi a - bakan meluap menjadi positif, begitu (a - b < 0)juga salah.

Jika Anda terbiasa dengan kode rakitan x86, pertimbangkan yang (a < b)diterapkan oleh a jge, yang bercabang di sekitar badan pernyataan if ketika SF = OF. Di sisi lain, (a - b < 0)akan bertindak seperti a jns, yang bercabang ketika SF = 0. Oleh karena itu, ini berperilaku berbeda saat OF = 1.