2

我有两段代码，我想知道它们运行时哪个更快以及为什么更快。我对 JVM 和 CPU 的了解较少，但我正在努力研究它们。每个提示都会有所帮助。

int[] a=new int[1000];
int[] b=new int[10000000];
long start = System.currentTimeMillis();
//method 1
for(int i=0;i<1000;i++){
    for(int j=0;j<10000000;j++){
        a[i]++;
    }
}
long end = System.currentTimeMillis();
System.out.println(end-start);

start=System.currentTimeMillis();
//method 2
for(int i=0 ;i<10000000;i++){
    for(int j=0;j<1000;j++){
        b[i]++;
    }
}
end = System.currentTimeMillis();
System.out.println(end-start);
4

8 回答 8

5

我会把我的答案扔在那里，理论上它们会完全相同，但实际上会有一个很小但可以忽略不计的差异。实际上，太小了，根本不重要。

基本思想是数组如何b存储在内存中。因为它要大得多，取决于您的平台/实现，它可能以块的形式存储，也就是不连续的。这很可能是因为 1000 万个整数的数组是 4000 万字节 = 40 MB！

编辑：我分别得到 572 和 593。

于 2013-09-27T07:33:15.487 回答
5

复杂

就渐近复杂度（例如大 O 表示法）而言，它们具有相同的运行时间。

数据本地化

暂时忽略任何优化...

b更大，因此更有可能被拆分为多个（或更多）页面。因此，第一个可能更快。

此处的差异可能相当小，除非并非所有这些页面都适合 RAM 并且需要写入磁盘（此处不太可能，因为b只有 10000000*4 = 40000000 字节 = 38 MB）。

优化

第一种方法涉及“执行a[i]++10000000 次”（对于固定的i），理论上可以很容易地a[i] += 10000000由优化器转换为。

可以对 进行类似的优化b，但仅限于b[i] += 1000，它仍然必须运行 10000000 次。

优化器可以自由地执行此操作或不执行此操作。据我所知，只要不改变最终结果，Java 语言规范并没有太多说明应该优化什么和不应该优化什么。

作为一个极端的结果，理论上优化器可以看到你没有在循环中a或b循环之后做任何事情，从而摆脱了两个循环。

于 2013-09-27T07:31:13.720 回答
1

第一个循环在我的系统上运行得更快（中位数：333 ms vs. 596 ms）
（编辑：我在第一个响应中对数组访问次数做出了错误的假设，请参阅评论）

对同一数组的后续增量（索引++）访问似乎比随机访问或减量（索引--）访问更快。我假设Java Hotspot 编译器可以优化数组绑定检查，如果它识别出数组将被增量遍历。

反转循环时，它实际上运行得更慢：

//incremental array index
for (int i = 0; i < 1000; i++) {
    for (int j = 0; j < 10000000; j++) {
        a[i]++;
    }
}

//decremental array index
for (int i = 1000 - 1; i >= 0; i--) {
    for (int j = 10000000 - 1; j >= 0; j--) {
        a[i]++;
    }
}

增量：349ms，减量：485ms。 如果没有边界检查，递减循环通常更快，尤其是在旧处理器上（与零相比）。

如果我的假设是正确的，这使得 1000 次优化边界检查与 10000000 次检查相比，所以第一种方法更快。

顺便说一句，在进行基准测试时：

  • 进行多轮并比较平均值/中间值而不是第一个样本
  • 在 Java 中：给你的基准测试一个预热阶段（在测量之前执行几次）。在第一次运行时，必须加载类，并且可能会在HotSpot VM 功能启动并执行本机编译之前解释代码
  • 用 测量时间增量System.nanoTime()。这提供了更准确的时间戳。System.currentTimeMillis()不是那么精确（取决于VM），并且通常在十几毫秒或更多毫秒的垃圾中“跳跃”，使您的结果比实际更不稳定。顺便说一句：1 毫秒 = 1'000'000 纳秒。
于 2013-09-27T07:58:37.840 回答
0

首先会更快。由于第一个a和i单元格的初始化次数要少得多。

于 2013-09-27T07:37:16.710 回答
0

我的猜测是它们几乎相同。其中一个有一个较小的数组要处理，但这不会有太大的区别，除了内存的初始分配，这无论如何都超出了你的测量范围。

执行每次迭代的时间应该相同（将值写入数组）。增加较大的数字不应该比增加较小的数字花费 JVM 更长的时间，也不应该处理更小或更大的数组索引。

但是，如果您已经知道如何衡量自己，为什么还要问这个问题呢？

于 2013-09-27T07:27:16.317 回答
0

查看大哦符号

嵌套的 for 循环是 O(n^2) - 它们在理论上运行相同。

数字 1000 或 100000 是常数 k O(n^2 + k)

由于各种其他因素在起作用，它们在实践中不会完全相同，但它会很接近。

于 2013-09-27T07:27:26.267 回答
0

时间应该相等，结果显然会有所不同，因为 a 将包含 1000 个值为 10000 的条目，而 b 将包含 10000000 个值为 1000 的条目。我真的不明白你的问题。结束开始的结果是什么？JVM 可能会优化 forloops，如果它知道数组中的最终结果是什么，那么最小的数组将更容易计算，因为它只需要 1000 次分配，而另一个需要 10000 倍以上.

于 2013-09-27T07:27:49.290 回答
0

现代架构很复杂，因此回答这类问题绝非易事。

运行时间可能相同，或者第一个可能更快。

在这种情况下要考虑的主要是内存访问和优化。

一个好的优化器会意识到这些值永远不会被读取，因此可以完全跳过循环，这两种情况下的运行时间都是 0。这种优化可以发生在编译时或运行时。

如果它没有被优化掉，那么就需要考虑内存访问。a[]比 小 得多b[], 所以 它 更 容易 适应 更快 的 缓存 内存 , 从而 减少缓存 未命中.

要考虑的另一件事是内存交错。

于 2013-09-27T08:39:57.110 回答