在for循环中使用集合大小进行比较

Question

是否有针对Java集合中size()方法的编译器优化？

考虑以下代码：

for(int i=0;i<list.size();i++)
      ...some operation.....

每次都会调用size()方法获取长度，是否考虑先获取长度并重复使用呢？（方法调用会有开销）

final int len = list.size()
for(int i=0;i<len;i++)
      ...some operation.....

然而，当我对这两段代码进行计时时，即使i的值高达10000000，也没有明显的时间差异。 我是否漏掉了什么？

更新1：我知道除非集合发生更改，否则不会重新计算大小。 但是方法调用肯定存在一些开销吧。编译器是否总是内联这些方法（请参见Esko的答案）？

更新2：我的好奇心进一步被燃起。从给出的答案中，我看到良好的JIT编译器通常会内联此函数调用。但是，它们仍然必须确定集合是否已修改。我没有接受答案，希望有人可以给我关于编译器如何处理这个问题的指导。

- athena

---

最好不要担心这类事情，直到分析器向您展示这是应用程序的实际瓶颈，而这可能永远不会发生。拥有更易读的代码比微不足道地更快的代码更好。但从纯学术角度来看，这仍然是一个很好的问题。 - Sergei Tachenov

@Sergey：是的。我进行的简单测试向我展示了我不必担心效率问题。因此，我进行了更新。但这激起了我的好奇心。请查看我对Tom Anderson评论的回复。 - athena

Answer 1

好的，这是从JDK源代码（JDK文件夹中的src.zip）摘录的一段：

public int size() {
    return size;
}

这段代码来自ArrayList，但我认为其他集合类也有类似的实现。现在如果我们想象编译器会内联size()调用（这是很合理的），那么你的循环就变成了这样：

for(int i=0;i<list.size;i++)
// ...

（好吧，先不管大小是私有的。）编译器如何检查集合是否已被修改？答案是它不检查也不需要检查，因为大小已经在字段中可用，所以它只需要在每次迭代时访问大小字段，而访问int变量是非常快的操作。请注意，它可能会计算其地址一次，因此甚至不必在每次迭代中对列表进行解引用。

当集合被修改时（例如通过add（）方法），会发生什么？

public boolean add(E e) {
    ensureCapacity(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

正如您所看到的，它只增加了大小字段。 因此，编译器实际上不需要做任何事情来确保它可以访问最新的大小。 唯一的例外是，如果从另一个线程修改集合，则需要进行同步，否则循环线程可能会看到其本地缓存的大小值，该值可能已更新或未更新。

- Sergei Tachenov

Answer 2

集合的.size()方法返回的值通常被缓存，只有在实际的集合被修改（添加新元素或移除旧元素）时才会重新计算。

与其比较for循环控制变量的作用域，不如尝试使用for each循环，因为它实际上使用了Iterator，在某些集合实现中比使用索引迭代要快得多。

- Esko

---

例如，当使用LinkedList时。 - Guillaume

@Esko：你所说的缓存是指在子类中，例如ArrayList中的“size”字段吗？但这仍然是一个方法调用，不是吗？或者在Java中，方法调用没有太多开销？ - athena

@athena：确实，该字段的值仅在需要时重新计算。JVM通过内联实际字段访问优化方法调用，因此从技术上讲，尤其是在长时间运行的应用程序中，大多数方法调用根本没有任何开销。 - Esko

@Esko：这与问题无关，但你能举一个使用迭代器比按索引迭代更快的集合的例子吗（除了LinkedList）？ - athena

@Esko：谢谢。你能给我一些内联字段的文章/文档的指引吗？ - athena

Answer 3

调用集合的size()方法只是返回一个已经被跟踪的整数值。因为size()实际上并没有计算项目数量，而是在添加或删除项目时跟踪项目数量，所以时间差别不大。

- prgmast3r

---

是的和不是的。Collection 不需要以 O(1) 的时间复杂度返回它自己的大小，但大多数实现都这样做。 - Andreas Dolk

Answer 4

Java语言规范解释了表达式在每次迭代步骤中都会被评估。对于您的示例，list.size()被调用了1000万次。

这在您的情况下不重要，因为列表实现（通常）有一个私有属性来存储实际列表大小。但如果计算确实需要时间，它可能会引起麻烦。在这些情况下，建议将表达式的结果存储到局部变量中。

- Andreas Dolk

---

这仍然是一个方法调用吗？还是说，在Java中，方法调用没有太多开销？ - athena

@athena：一个好的JIT编译器 - 就像Sun的JVM中的编译器 - 往往能够内联方法调用，将其转换为简单的加载操作，这是最快的操作之一。 - Tom Anderson

@Tom：但编译器仍然需要确定集合是否被修改。你能给我一些指针，了解一下（Sun的）JVM是如何处理这个问题的吗？ - athena

@athena - 使用内联后，执行代码在优化后可能包含对（私有）size字段的引用。如果该方法是一个简单的getter，返回私有字段的引用/值，那么这是完全安全的。就像大多数size()方法一样。 - Andreas Dolk