if(a - b <0)和if(a <b)之间的差异

Question

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

在Java 7中,该方法grow(int)使用

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

在Java 6中,grow不存在.ensureCapacity(int)然而,该方法使用

if (newCapacity < minCapacity)
    newCapacity = minCapacity;

改变背后的原因是什么？这是性能问题还是风格？

我可以想象,与零进行比较会更快,但执行完全减法只是为了检查它是否为负似乎对我来说有点矫枉过正.同样在字节码方面,这将涉及两个指令(ISUB和IF_ICMPGE)而不是一个(IFGE).

Answer 1

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是否定的)所以newCapacity无论如何都将被强制minCapacity执行oldCapacity.

这个溢出的情况由下一个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这种方法中的评论所说的.

Answer 2

我找到了这个解释:

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

我做了一个快速搜索,看起来Java确实是两个补充.尽管如此,请允许我指出,一般来说,这种类型的代码让我很担心,因为我完全相信某些人会出现并完全按照Dmytro的建议行事; 也就是说,有人会改变:

if (a - b > 0)

至

if (a > b)

而整艘船都会沉没.我个人喜欢避免使用整数溢出这样的晦涩难懂,这是我的算法必不可少的基础,除非有充分的理由这样做.一般来说,我宁愿完全避免溢出并使溢出场景更明确:

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

这是一个好点.

在ArrayList我们不能做到这一点(或至少不兼容),因为 ensureCapacity是一个公共的API,有效地接受已经为负数的不能满足一个积极的容量请求.

当前的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.

Answer 3

看代码:

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

如果oldCapacity非常大,这将溢出,并且newCapacity将是负数.像这样的比较newCapacity < oldCapacity会错误地评估true,并且ArrayList会失败.

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

这是// overflow-conscious code评论试图沟通的内容,而不是倾斜.

因此,最重要的是,新的比较可以防止分配ArrayList大于预定义的值,MAX_ARRAY_SIZE同时允许它在需要时增长到该限制.