if (a - b <0)和if (a <b)

我正在阅读Java的ArrayList源代码，并注意到if语句中有一些比较。

在Java 7中，grow(int)使用的方法

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

在Java 6中，grow不存在。ensureCapacity(int)使用的方法

if (newCapacity < minCapacity)
newCapacity = minCapacity;

这一变化背后的原因是什么?是性能问题还是风格问题?

我可以想象，与0比较会更快，但仅仅为了检查它是否为负而执行一个完整的减法，对我来说似乎有点过头了。同样在字节码方面，这将涉及两个指令(ISUB和IF_ICMPGE)，而不是一个指令(IFGE)。

14792 次浏览
小开
最佳答案

a < b和a - b < 0可以表示两个不同的东西。考虑下面的代码:

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显然是假的，但是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.MAX_VALUE，因此newCapacity(即oldCapacity + 0.5 * oldCapacity)可能溢出并变成Integer.MIN_VALUE(即为负)。然后，将minCapacity 下溢减回一个正数。

这个检查确保if没有被执行。如果代码被编写为if (newCapacity < minCapacity)，在这种情况下它将是true(因为newCapacity是负的)，因此无论oldCapacity如何，newCapacity将被迫为minCapacity。

此溢出情况由下一个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。

注意:这就是这个方法中的// overflow-conscious code注释所说的。

小开

我找到这个解释:

2010年3月9日星期二03:02,Kevin L. Stern写道:

我做了一个快速搜索，看起来Java确实是两个的补充 的基础。尽管如此，请允许我指出，总的来说，这 这种类型的代码让我担心，因为我完全希望在某些时候有人会这样做 来吧，按照德米特罗的建议去做;也就是说，有人会 变化:< / p > 
if (a - b > 0)

来

if (a > b)

，整艘船就会沉没。就我个人而言，我喜欢避免晦涩难懂的东西 比如让整数溢出成为我算法的基本基础除非 这样做是有充分理由的。一般来说，我宁愿避免 完全溢出，并使溢出场景更显式:

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

这个观点很好。

在ArrayList中，我们不能这样做(或至少不兼容)，因为 ensureCapacity是一个公共API，实际上已经被接受 负数作为对正容量的请求，这是不可能的 满意。< / p >

当前的API是这样使用的:

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

如果你想避免溢出，你需要改变一些东西 不太自然，比如

ensureCapacity(count, len);
int newcount = count + len;
不管怎样，我保留了溢出意识代码，但增加了更多 警告注释，并“突出”巨大的数组创建以便 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，你可能会错误地认为ArrayList增加了len。

小开

查看代码:

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

如果oldCapacity相当大，则会溢出，并且newCapacity将是一个负数。像newCapacity < oldCapacity这样的比较将不正确地计算true，并且ArrayList将无法增长。

相反，所写的代码(newCapacity - minCapacity < 0返回false)将允许newCapacity的负值在下一行中进一步求值，从而通过调用hugeCapacity (newCapacity = hugeCapacity(minCapacity);)重新计算newCapacity，以允许ArrayList增长到MAX_ARRAY_SIZE。

这就是// overflow-conscious code注释试图传达的内容，尽管比较间接。

因此，底线是，新的比较可以防止分配一个比预定义的MAX_ARRAY_SIZE更大的ArrayList，同时允许它在需要时增长到这个限制。

小开

这两种形式的行为完全相同，除非表达式a - b溢出，在这种情况下，它们是相反的。如果a是一个大的负数，而b是一个大的正数，那么(a < b)显然为真，但a - b将溢出变成正数，因此(a - b < 0)为假。

如果你熟悉x86汇编代码，可以考虑(a < b)是由jge实现的，当SF = of时，它围绕If语句体展开分支。另一方面，(a - b < 0)将像jns一样，当SF = 0时，它会分支。因此，当OF = 1时，它们的行为恰好不同。


提交答案