java - ArrayList 的速度是数组的两倍多吗？

Question

我写了一个测试来测试两件事:

• 缓冲区数组的大小是否会影响其性能，即使您不使用整个缓冲区也是如此
• 数组和 ArrayList 的相对性能

我对结果感到有点惊讶

• 盒装数组(即 Integer 与 int )并不比原始版本慢多少
• 底层数组的大小并不重要
• ArrayList s 比相应的数组慢两倍以上。

问题

1. 为什么是ArrayList这么慢？
2. 我的基准测试写得好吗？换句话说，我的结果准确吗？

结果

 0% Scenario{vm=java, trial=0, benchmark=SmallArray} 34.57 ns; ?=0.79 ns @ 10 trials
17% Scenario{vm=java, trial=0, benchmark=SmallBoxed} 40.40 ns; ?=0.21 ns @ 3 trials
33% Scenario{vm=java, trial=0, benchmark=SmallList} 105.78 ns; ?=0.09 ns @ 3 trials
50% Scenario{vm=java, trial=0, benchmark=BigArray} 34.53 ns; ?=0.05 ns @ 3 trials
67% Scenario{vm=java, trial=0, benchmark=BigBoxed} 40.09 ns; ?=0.23 ns @ 3 trials
83% Scenario{vm=java, trial=0, benchmark=BigList} 105.91 ns; ?=0.14 ns @ 3 trials

 benchmark    ns linear runtime
SmallArray  34.6 =========
SmallBoxed  40.4 ===========
 SmallList 105.8 =============================
  BigArray  34.5 =========
  BigBoxed  40.1 ===========
   BigList 105.9 ==============================

vm: java
trial: 0

代码

此代码是使用 Java 7 和 Google caliper 0.5-rc1 在 Windows 中编写的(因为我上次检查 1.0 还不能在 Windows 中运行)。

简要概述:在所有 6 个测试中，在循环的每次迭代中，它会将数组的前 128 个单元格中的值相加(无论数组有多大)并将其加到总值中。 Caliper 告诉我测试应该运行多少次，所以我循环执行该加法 128 次。

这 6 个测试有一个大版本 (131072) 和一个小版本 (128) int[] , Integer[] , 和 ArrayList<Integer> .您可能可以从名称中找出哪个是哪个。

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import com.google.caliper.Runner;
import com.google.caliper.SimpleBenchmark;

public class SpeedTest {    
    public static class TestBenchmark extends SimpleBenchmark {
        int[] bigArray = new int[131072];
        int[] smallArray = new int[128];
        Integer[] bigBoxed = new Integer[131072];
        Integer[] smallBoxed = new Integer[128];
        List<Integer> bigList = new ArrayList<>(131072);
        List<Integer> smallList = new ArrayList<>(128);

        @Override
        protected void setUp() {
            Random r = new Random();
            for(int i = 0; i < 128; i++) {
                smallArray[i] = Math.abs(r.nextInt(100));
                bigArray[i] = smallArray[i];
                smallBoxed[i] = smallArray[i];
                bigBoxed[i] = smallArray[i];
                smallList.add(smallArray[i]);
                bigList.add(smallArray[i]);
            }
        }

        public long timeBigArray(int reps) {
            long result = 0;
            for(int i = 0; i < reps; i++) {
                for(int j = 0; j < 128; j++) {
                    result += bigArray[j];
                }
            }
            return result;
        }

        public long timeSmallArray(int reps) {
            long result = 0;
            for(int i = 0; i < reps; i++) {
                for(int j = 0; j < 128; j++) {
                    result += smallArray[j];
                }
            }
            return result;
        }

        public long timeBigBoxed(int reps) {
            long result = 0;
            for(int i = 0; i < reps; i++) {
                for(int j = 0; j < 128; j++) {
                    result += bigBoxed[j];
                }
            }
            return result;
        }

        public long timeSmallBoxed(int reps) {
            long result = 0;
            for(int i = 0; i < reps; i++) {
                for(int j = 0; j < 128; j++) {
                    result += smallBoxed[j];
                }
            }
            return result;
        }

        public long timeBigList(int reps) {
            long result = 0;
            for(int i = 0; i < reps; i++) {
                for(int j = 0; j < 128; j++) {
                    result += bigList.get(j);
                }
            }
            return result;
        }

        public long timeSmallList(int reps) {
            long result = 0;
            for(int i = 0; i < reps; i++) {
                for(int j = 0; j < 128; j++) {
                    result += smallList.get(j);
                }
            }
            return result;
        }
    }

    public static void main(String[] args) {
        Runner.main(TestBenchmark.class, new String[0]);
    }
}

Answer 1

首先...

Are ArrayLists more than twice as slow as arrays?

作为概括，没有。对于可能涉及“更改”列表/数组长度的操作，ArrayList 将比数组更快......除非您使用单独的变量来表示数组的逻辑大小。

对于其他操作，ArrayList 可能会更慢，但性能比很可能取决于操作和 JVM 实现。另请注意，您只测试了一种操作/模式。

Why is ArrayList so much slower?

因为 ArrayList 内部有一个不同的数组对象。

• 操作通常涉及额外的间接寻址(例如获取列表的大小和内部数组)以及额外的边界检查(例如检查列表的大小 和数组的长度)。典型的 JIT 编译器(显然)无法优化这些。 (事实上​​，您不想优化内部数组，因为它允许 ArrayList 增长。)

• 对于原语数组，相应的列表类型涉及包装的原语类型/对象，这会增加开销。例如，在“列表”情况下，您的 result += ... 涉及拆箱。

Is my benchmark written well? In other words, are my results accurate?

这在技术上没有任何问题。但不足以证明你的观点。首先，您只测量一种操作:数组元素获取及其等效操作。而且您只测量原始类型。

---

最后，这在很大程度上忽略了使用 List 类型的要点。我们使用它们是因为它们几乎总是比普通数组更易于使用。 (比如)2 的性能差异通常对整体应用程序性能并不重要。