logo标签列表

调用数组.length的成本是多少？

javaarrayspremature-optimization
62

在我们的应用程序中将for循环更新为for-each循环时，我遇到了很多这种“模式”：

for (int i = 0, n = a.length; i < n; i++) {
    ...
}

取代

for (int i = 0; i < a.length; i++) {
    ...
}

我可以看到你在使用集合时可以获得更好的性能，因为你不需要在每次循环中调用size()方法。但是对于数组呢？

所以问题出现了：与普通变量相比，array.length是否更昂贵？

4
为了易读性，请使用第二种模式或for..each循环。请！ - Andreas Dolk
8个回答
81

array.length的调用是O(1)或常量时间操作。

由于.length就像array的public final成员一样，所以访问速度与访问本地变量无异。(这与调用类似size()方法不同)

现代JIT编译器很可能会优化掉对.length的调用。

您可以通过查看OpenJDK中JIT编译器的源代码或者让JVM转储编译后的本机代码并检查代码来确认这一点。

请注意，有些情况下JIT编译器可能无法进行优化，例如：

  1. 如果您正在调试封闭方法，或者
  2. 如果循环体有足够的本地变量强制使用寄存器溢出。
9
@jjnguy：调用array.length的时间复杂度不可以是O(1)，而且它可能比int len = array.length; i < len; 还要更长，尽管后者的时间复杂度也是O(1)。 - Grant Wagner
3
如果你担心这种事情，我认为你应该使用C或C++进行编程。 （但是，是的，你可能是正确的） - jjnguy
11
@jjnguy在这里有些迂腐，他指出并非所有O(1)操作都是相等的。 - Grant Wagner
1
我添加了更多信息。现在应该更有意义了。 - jjnguy
3
现代编译器很可能会将对.length的调用进行优化，以便更好地优化代码。[需要引证来源] - xehpuk
显示剩余5条评论
19

我在午餐时间有点空闲：

public static void main(String[] args) {
    final int[] a = new int[250000000];
    long t;

    for (int j = 0; j < 10; j++) {
        t = System.currentTimeMillis();
        for (int i = 0, n = a.length; i < n; i++) { int x = a[i]; }
        System.out.println("n = a.length: " + (System.currentTimeMillis() - t));

        t = System.currentTimeMillis();
        for (int i = 0; i < a.length; i++) { int x = a[i]; }
        System.out.println("i < a.length: " + (System.currentTimeMillis() - t));
    }
}

结果如下：
n = a.length: 672
i < a.length: 516
n = a.length: 640
i < a.length: 516
n = a.length: 656
i < a.length: 516
n = a.length: 656
i < a.length: 516
n = a.length: 640
i < a.length: 532
n = a.length: 640
i < a.length: 531
n = a.length: 641
i < a.length: 516
n = a.length: 656
i < a.length: 531
n = a.length: 656
i < a.length: 516
n = a.length: 656
i < a.length: 516

注：

  1. 如果你反转测试，那么 n = a.length 显示比 i < a.length 快约一半，可能是由于垃圾回收导致的。
  2. 我不能将 250000000 设得更大，因为我在 270000000 时遇到了 OutOfMemoryError。

重点是，正如其他人所说，你必须让Java耗尽内存，但仍然看不到两种替代方案之间速度上的显着差异。把你的开发时间花在真正有意义的事情上。

@wbkang：识别出我的默认堆大小对于一个非常大的数组来说是不足够的并不是这个练习的重点。 - Grant Wagner
@Brian：在C/C++中总是很重要吗？如果您有一个进行1秒计算的1000次迭代循环，您真的会担心用一种方式比另一种方式访问数组的长度需要多花费几毫秒吗？您更好地花时间来优化进行1000次的1秒计算。我知道您想说的是“有时这很重要”，但即使对于C/C++，它也并不总是很重要。正如我所说，将您的开发时间花在实际上真正重要的事情上。 - Grant Wagner
4
我有点失望编译器没有意识到整个循环完全没有作用，并简单地将其优化掉了。 - 5gon12eder
如果您使用50毫秒的游戏时钟，则我认为150毫秒是一个显著的差异 :-) 不过再说一遍，您永远不会使用这样巨大的数组。 - Tschallacka
这是一个糟糕的基准测试，结果并不能说明实际代码中会发生什么。当我使用Java 11运行它时，循环似乎被JIT编译器优化掉了。我得到了40,5,15,0,0,0,0,0,0,0,0,0,0,0,0,0...从你得到的数字来看，我会说该方法没有被JIT编译。 - Stephen C
11

我怀疑这样做根本没有任何显著的区别，即使有，也很可能在编译时被优化掉了。当你试图进行微观优化时，你只是浪费时间。首先要让代码可读且正确，如果有性能问题，使用分析工具，然后才考虑选择更好的数据结构/算法（如果适用），然后再担心优化分析工具显示的部分。

1
除非您在循环内执行的操作非常琐碎，否则您在循环内执行的任何操作可能比按数量级访问.length要花费更长的时间。 - Grant Wagner
7

在Java中，数组的长度被存储为数组的成员变量（而不是元素），因此获取该长度是一个常数时间操作，与从普通类读取成员变量相同。许多旧语言（如C和C ++）不将长度存储为数组的一部分，因此您需要在循环开始之前存储长度。在Java中不需要这样做。

4
它并不完全像成员变量；实际上，它具有自己特殊的字节码。 - Michael Myers
3

把它存储在一个变量中可能会稍微快一点。但是如果分析器指出它是一个问题，我会非常惊讶。

在字节码级别上，获取数组的长度是通过arraylength字节码完成的。我不知道它是否比iload字节码慢，但是差异应该不足以注意到。

3
在这种情况下，您为什么不制作一个反向循环：
for (int i = a.length - 1; i >= 0; --i) {
    ...
}

这里有两个微小的优化：
  • 循环反转
  • 后缀递减
为什么“循环反转”更好？因为与0的比较更快吗？ - Stroboskop
是的，我也这么认为。有人为此制作了一个基准测试：http://www.mkyong.com/java/reverse-loop-versus-forward-loop-in-performance-java/。 - instcode
1
至于“为什么不”，因为我想保持代码简单。我提出这个问题的原因只是想看看是否有合理的理由使用问题中描述的模式。 - Stroboskop
1
@instcode 后缀递减比后缀递增更快吗？ - Honinbo Shusaku
2
这篇答案是从C#角度来看的，但我认为Java同样适用。
在C#中，惯用语法
for (int i = 0; i < a.length; i++) {    ...}

当在循环中访问数组时，它被认为是迭代数组，因此在访问数组时避免了边界检查。

这可能会在以下代码中被识别：

for (int i = 0, n = a.length; i < n; i++) {    ...}

或者

n = a.length;

for (int i = 0; i < n; i++) {   ...}

我不知道这种优化有多少是由编译器执行的，而有多少是由JITter执行的，特别是如果是由JITter执行的话，我希望所有三个都会生成相同的本地代码。

然而，第一种形式也可以说更容易被人理解，所以我建议选择那个。

是的，我认为Java也进行了相同的优化（至少较新的JVM应该会这样做）。 - Michael Myers
1

Array.length是一个常量，JIT编译器应该在两种情况下都能看到它。我希望生成的机器代码在两种情况下都是相同的。至少对于服务器编译器来说是这样。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接