if（a-b <0）とif（a <b）の違い

Question

私はJavaのArrayListソースコードを読んでいて、if文でいくつかの比較を気付いていました。

は、Java 7では、方法grow(int)は、Java 6で

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

を使用して、growは存在しませんでした。ただし、方法ensureCapacity(int)が使用されます

if (newCapacity < minCapacity) 
    newCapacity = minCapacity; 

変更理由は何ですか？それはパフォーマンス上の問題か、それとも単なるスタイルですか？

私はゼロとの比較が高速ですが、それが否定的であるかどうかをチェックするために完全な減算を実行するのはちょっと残酷すぎるようです。また、バイトコードに関しては、これには2つの命令（とIF_ICMPGE）が1つ（IFGE）の代わりに含まれます。

Answer 1

a < bおよびa - b < 0は、2つの異なることを意味する可能性があります。次のコードを検討してください：

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

これを実行すると、a - b < 0が印刷されます。何が起こるかは、a < bが明らかにfalseですが、a - bがオーバーフローし、-1になります。これは負の値になります。

今、アレイの長さは実際にはInteger.MAX_VALUEに近いと考えています。 ArrayList内のコードは次のようになります：

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

oldCapacityがオーバーフローしてInteger.MIN_VALUE（すなわち負）になるかもしれません（oldCapacity + 0.5 * oldCapacityです）Integer.MAX_VALUEのでnewCapacityに本当に近いです。次に、minCapacityを減算すると、が正の数に戻ってアンダーフローします。

このチェックは、ifが実行されないことを保証します。コードがif (newCapacity < minCapacity)と書かれていた場合、newCapacityはoldCapacityに関係なくminCapacityに強制されるので、newCapacityが負であるので、この場合はtrueとなります（newCapacityが負であるため）。

このオーバーフローのケースは、次のifによって処理されます。 newCapacityがオーバーフローした場合、true：MAX_ARRAY_SIZEはInteger.MAX_VALUE - 8となり、Integer.MIN_VALUE - (Integer.MAX_VALUE - 8) > 0はtrueとなります。したがってnewCapacityは正しく処理されます。hugeCapacityメソッドはMAX_ARRAY_SIZEまたはInteger.MAX_VALUEを返します。

NB：これは、この方法のコメントが言っていることです。

Answer 2

私はthis explanationが見つかりました：

火、2010年3月9日で3時02分で、ケビン・L.スターンは書きました：

私はクイック検索を行なったし、Javaが実際に基づいて、2の補数 であることが表示されます。それにもかかわらず、私はいつも誰かが誰かに が来て、Dmytroが示唆したことを完全に期待するので、この コードのタイプが私に心配していることを指摘してください。

if (a - b > 0) 

if (a > b) 

に、全船が沈んでしまう。つまり、誰かが 変更されます。私は、個人的には、 のような理由がある場合を除き、整数オーバーフローを私のアルゴリズムの不可欠な基礎にするなど、不明瞭さを避けることを好む。私は、一般的には、完全に オーバーフローを避けることを好むだろうとオーバーフローのシナリオがより明確にするために：

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

それは良い点です。 ensureCapacityがパブリックAPIで、効果的にすでに を満たすことができない正の容量に対する要求として 負の数を受け入れるため

はArrayListでは、我々は、（少なくともない互換）これを行うことはできません。

現在のAPIをこのように使用されて

：私は保ってるあなたがオーバーフローを避けたい場合は、あなたが何か に変更する必要があります

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

少ない自然のような

とにかく

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

、オーバーフローを意識したコードですが、 警告のコメントを追加し、「out-lining」という巨大な配列作成を行いました。 ArrayListのコードは次のようになりました：

/** 
* 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を再生した。

マーティン

のJava 6では、あなたはとしてAPIを使用している場合：

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

とnewCountオーバーフロー（これが負になる）、if (minCapacity > oldCapacity)はfalseを返します、あなたが誤って取ることができることArrayListlenによって増加した。

Answer 3

コードを見てみる：

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

oldCapacityが非常に大きい場合、これはオーバーフローし、newCapacityが負の数です。 newCapacity < oldCapacityのような比較は、trueを間違って評価し、ArrayListは成長しません。

代わりに、（偽newCapacity - minCapacity < 0戻る）書かれたように、コードは、ArrayListにまで成長することを可能にするためにhugeCapacity（newCapacity = hugeCapacity(minCapacity);）を呼び出すことによってnewCapacityを再計算で得られ、さらに次の行に評価されるnewCapacityの負の値を可能にしますMAX_ARRAY_SIZE。

これは、おおよそ斜めにでも、通信しようとしているコメントです。

したがって、新しい比較では、定義済みのMAX_ARRAY_SIZEより大きいArrayListを割り当てることを防ぎます。同時に、必要に応じてその上限まで拡大することができます。

Answer 4

式a - bがオーバーフローしない限り、2つのフォームはまったく同じように動作します。その場合は逆です。 aが大きな負数で、bが大きい場合は(a < b)が明らかですが、a - bがオーバーフローして正の値になるため、(a - b < 0)はfalseです。

(a < b)は、jgeで実装されていることを考慮してください。これは、SF = OFのときにif文の本文の周囲で分岐します。一方、(a - b < 0)は、SF = 0のときに分岐するjnsのように振る舞います。したがって、これらはOF = 1のときの動作が異なります。