什么是堆写入流量以及为什么在ArrayList中需要它？

Question

我只是想知道heap write traffic是什么意思以及为什么在ArrayList实现中需要它？

ArrayList实施的片段，请参阅评论行

@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
    Objects.requireNonNull(consumer);
    final int size = ArrayList.this.size;
    int i = cursor;
    if (i >= size) {
        return;
    }
    final Object[] elementData = ArrayList.this.elementData;
    if (i >= elementData.length) {
        throw new ConcurrentModificationException();
    }
    while (i != size && modCount == expectedModCount) {
        consumer.accept((E) elementData[i++]);
    }
    // update once at end of iteration to reduce heap write traffic
    cursor = i;
    lastRet = i - 1;
    checkForComodification();
}

Answer 1

可能是作者想要使用局部变量i，因为它可能在escape analysis and stack allocation开始时被分配堆栈。与cursor不同，由于i循环内部的i++语句，while变量被多次更改。在堆栈上增加它并且跳过所有Java内存模型含义应该更便宜。 Iterator.cursor是一个成员字段，它可能总是在堆上，尤其是Iterator对象在用户代码中传递。

Answer 2

通常，cursor变量指向由Iterator返回的下一个元素。因此，在迭代时，您需要每次都更新cursor变量，以便它始终指向正确的元素。

但是，forEachRemaining方法自己完成迭代。这并不意味着暂停。因此，您可以忽略更新游标变量，直到方法完成。当方法迭代时，cursor将指向错误的元素。但是，由于你不能暂停这个方法，它没有任何区别。

通过这种方式，您可以减少对cursor的分配量以及堆流量。所以他们指的是更正确的实现

while (i != size && modCount == expectedModCount) {
    consumer.accept((E) elementData[i++]);
    // Update cursor while iterating
    cursor = i;
}

或直接使用光标而不是额外的i

while (cursor != size && modCount == expectedModCount) {
    consumer.accept((E) elementData[cursor++]);
}

但是然后你处理成员变量而不是局部变量i。使用i更便宜，详情请参阅@kdowbecki的答案。

Answer 3

如果你忽略所有守卫条件，next()会做以下事情：

public E next() {
    Object[] elementData = ArrayList.this.elementData;

    int i = cursor;
    cursor = i + 1;
    lastRet = i;
    return (E) elementData[i];
}

forEachRemaining()将基本上继续调用next()并在每个元素上调用消费者，所以如果我们这样做，内联next()逻辑，我们得到：

public void forEachRemaining(Consumer<? super E> consumer) {
    final int size = ArrayList.this.size;
    final Object[] elementData = ArrayList.this.elementData;

    int i = cursor;
    while (i != size) { // same as hasNext()
        // begin: consumer.accept(next())
        cursor = i + 1;
        lastRet = i;
        consumer.accept((E) elementData[i]);
        // end: consumer.accept(next())
        i++;
    }
}

由于cursor和lastRet都是字段，它们存在于堆上，而i存在于堆栈中。

为了减少内存写入次数，可以将cursor和lastRet的更新移到循环外部，因为它们实际上并未在循环内部使用。

当然，你现在正在做一个额外的i++，所以你需要从1中减去i。

public void forEachRemaining(Consumer<? super E> consumer) {
    final int size = ArrayList.this.size;
    final Object[] elementData = ArrayList.this.elementData;

    int i = cursor;
    while (i != size) {
        consumer.accept((E) elementData[i++]);
    }
    cursor = i;
    lastRet = i - 1;
}

结果是，在迭代期间只更新堆栈变量i，并且两个堆值保持不变。

一旦JIT启动，如果accept()调用内联，堆栈变量i甚至可能被消除并变成一个寄存器值，大大减少了对“慢”内存的更新次数。

Answer 4

谢谢你提供答案。为了更好地解释，我将添加内部Java内存模型的外观，如下图所示。正如@kdowbecki，@ Zabuza和@Andreas指出的那样，使用Thread Stack内存进行本地执行然后在每次迭代中使用Heap内存是有效的。它可能属于amortized analysis类别。

在操作系统中检查memory model of a process（JVM是一个进程）也很有趣。