Java For-Loop - 终止表达式速度

Question

在我的 java 程序中，我有一个大致如下所示的 for 循环:

ArrayList<MyObject> myList = new ArrayList<MyObject>();
putThingsInList(myList);
for (int i = 0; i < myList.size(); i++) { 
     doWhatsoever(); 
}

由于列表的大小没有改变，我尝试通过用变量替换循环的终止表达式来加速循环。

My idea was: Since the size of an ArrayList can possibly change while iterating it, the termination expression has to be executed each loop cycle. If I know (but the JVM doesn't), that its size will stay constant, the usage of a variable might speed things up.

ArrayList<MyObject> myList = new ArrayList<MyObject>();
putThingsInList(myList);
int myListSize = myList.size();
for (int i = 0; i < myListSize; i++) { 
     doWhatsoever(); 
}

但是，这个解决方案比较慢，非常慢；也使 myListSize final 不会改变任何东西!我的意思是我可以理解，如果速度根本没有改变的话；因为也许 JVM 刚刚发现，大小不会改变并优化了代码。但是为什么会慢呢？

但是，我重写了程序；现在列表的大小随着每个循环而变化:if i%2==0，我删除列表的最后一个元素，否则我将一个元素添加到列表的末尾。所以现在必须在每次迭代中调用 myList.size() 操作，我猜。

我不知道这是否真的正确，但 myList.size() 终止表达式仍然比仅使用一个始终保持不变的变量作为终止表达式更快...

有什么想法吗？

编辑(我是新来的，我希望这是方法，怎么做)我的整个测试程序如下所示:

ArrayList<Integer> myList = new ArrayList<Integer>();
for (int i = 0; i < 1000000; i++)
{
    myList.add(i);
}

final long myListSize = myList.size();
long sum = 0;
long timeStarted = System.nanoTime();
for (int i = 0; i < 500; i++)
{
    for (int j = 0; j < myList.size(); j++)
    {
        sum += j;

        if (j%2==0)
        {
            myList.add(999999);
        }
        else
        {
            myList.remove(999999);
        }
    }
}
long timeNeeded = (System.nanoTime() - timeStarted)/1000000;
System.out.println(timeNeeded);
System.out.println(sum);

已发布代码的性能(10 次执行的平均值):myList.size() 为 4102 毫秒myListSize 为 4230 毫秒

没有 if-then-else 语句(因此 myList 大小不变)myList.size() 为 172 毫秒myListSize 为 329 毫秒

所以两个版本的速度差异仍然存在。在带有 if-then-else 部分的版本中，百分比差异当然更小，因为大量时间投入到列表的添加和删除操作上。

Answer 1

问题出在这一行:

final long myListSize = myList.size();

将其更改为 int，您瞧，运行时间将相同。为什么？因为每次迭代比较 int 和 long 都需要扩大 int 的转换范围，这需要时间。

请注意，当代码被编译和优化时，差异在很大程度上(但可能不完全)消失，从以下 JMH 基准测试结果可以看出:

# JMH 1.11.2 (released 7 days ago)
# VM version: JDK 1.8.0_51, VM 25.51-b03
# VM options: <none>
# Warmup: 20 iterations, 1 s each
# Measurement: 20 iterations, 1 s each
# Timeout: 10 min per iteration
# Threads: 1 thread, will synchronize iterations
# Benchmark mode: Throughput, ops/time
...
# Run complete. Total time: 00:02:01

Benchmark                           Mode  Cnt      Score      Error  Units
MyBenchmark.testIntLocalVariable   thrpt   20  81892.018 ±  734.621  ops/s
MyBenchmark.testLongLocalVariable  thrpt   20  74180.774 ± 1289.338  ops/s
MyBenchmark.testMethodInvocation   thrpt   20  82732.317 ±  749.430  ops/s

这是它的基准代码:

public class MyBenchmark {

    @State( Scope.Benchmark)
    public static class Values {
        private final ArrayList<Double> values;

        public Values() {
            this.values = new ArrayList<Double>(10000);
            for (int i = 0; i < 10000; i++) {
                this.values.add(Math.random());
            }
        }
    }

    @Benchmark
    public double testMethodInvocation(Values v) {
        double sum = 0;
        for (int i = 0; i < v.values.size(); i++) {
            sum += v.values.get(i);
        }
        return sum;
    }

    @Benchmark
    public double testIntLocalVariable(Values v) {
        double sum = 0;
        int max = v.values.size();
        for (int i = 0; i < max; i++) {
            sum += v.values.get(i);
        }
        return sum;
    }

    @Benchmark
    public double testLongLocalVariable(Values v) {
        double sum = 0;
        long max = v.values.size();
        for (int i = 0; i < max; i++) {
            sum += v.values.get(i);
        }
        return sum;
    }
}

附言:

My idea was: Since the size of an ArrayList can possibly change while iterating it, the termination expression has to be executed each loop cycle. If I know (but the JVM doesn't), that its size will stay constant, the usage of a variable might speed things up.

你的假设是错误的有两个原因:首先，VM 可以通过逃逸分析很容易地确定存储在 myList 中的列表没有逃逸方法(所以它可以自由分配它例如堆栈)。

更重要的是，即使列表在多个线程之间共享，因此在我们运行循环时可能会从外部修改，在没有任何同步的情况下，运行我们循环的线程假装那些是完全有效的根本没有发生任何变化。