Java ArrayList与OpenArrayList性能
Java应用程序经常将对象保存在包含" java.util.ArrayList"实例的数据结构中。当迭代那些数据结构中的对象时，我们还必须迭代存储在ArrayList实例中的对象。在此Java ArrayList性能教程中，我将仔细研究迭代" ArrayList"的不同方法的性能。本教程还将研究" OpenArrayList"类的性能，该类模仿" java.util.ArrayList"，但在设计时会考虑性能。
迭代ArrayList的三种方法
基本上有三种不同的方法可以迭代" ArrayList"中包含的对象：
- 使用for循环。
- 使用for-each循环。
- 使用迭代器。
这三种迭代ArrayList的方式之间并没有很大的性能差异，但是有一点，而且足够大，如果代码对性能至关重要，那么我们可能希望获得这种几乎免费的性能增益。但是首先，让我向我们展示迭代" ArrayList"的三种方法。
for循环
使用标准的Javafor循环迭代ArrayList看起来像这样：
ArrayList arrayList = ...//get ArrayList from somewhere
long sum = 0;
for(int i=0, n=arrayList.size(); i < n; i++){
Object element = arrayList.get(i);
}
如我们所见，" for"循环使用标准计数器来对存储在" ArrayList"中的所有元素进行计数。每个元素都是使用get()方法从ArrayList实例获得的。
每个循环
for-each循环使用Java 5中添加的for构造。这是使用for-each循环迭代ArrayList的样子：
ArrayList arrayList = ...//get ArrayList from somewhere
long sum = 0;
for(Object obj : arrayList){
}
迭代器
迭代" ArrayList"的第三种方法是使用从" ArrayList"获得的" java.util.Iterator"。这是使用Iterator迭代ArrayList的样子：
ArrayList arrayList = ...//get ArrayList from somewhere
long sum = 0;
Iterator iterator = arrayList.iterator();
while(iterator.hasNext()) {
Object element = iterator.next();
}
ArrayList迭代基准
为了测量三种不同的迭代" ArrayList"的迭代性能差异，我使用Java Microbenchmark Harness实现了三种不同的基准测试方法。这些基准测试的代码包含在本文的结尾。
为了更准确地了解每种技术的迭代速度，我测量了迭代包含10个元素和100个元素的" ArrayList"的速度。这样，我相信我会对性能有更细致的了解。
ArrayList中的元素是Long元素，它们相加。因此，基准测试实际上测量了存储在" ArrayList"中的10个和100个" Long"元素的迭代和求和。
基准测试是在Intel Core i7-4770 Haswell服务器上使用JDK 1.8.0_u60执行的，该服务器仅执行基准测试。使用JMH默认值执行基准测试，这意味着20次预热迭代，20次迭代和10次fork。以下是基准测试结果(JMH的输出)：
Benchmark Mode Cnt Score Error Units OpenArrayListBenchmark.jdkArrayList100SumUsingGet thrpt 200 15838998.503 ± 1017.752 ops/s OpenArrayListBenchmark.jdkArrayList100SumUsingForEach thrpt 200 14068898.854 ± 946.976 ops/s OpenArrayListBenchmark.jdkArrayList100SumUsingIterator thrpt 200 14069990.330 ± 512.600 ops/s OpenArrayListBenchmark.jdkArrayList10SumUsingGet thrpt 200 77320532.538 ± 7421.267 ops/s OpenArrayListBenchmark.jdkArrayList10SumUsingForEach thrpt 200 69926532.927 ± 732112.779 ops/s OpenArrayListBenchmark.jdkArrayList10SumUsingIterator thrpt 200 69879781.630 ± 727551.844 ops/s
如我们所见，使用for-each循环和Iterator迭代ArrayList产生的性能几乎相同。这是预料之中的，因为Java编译器可能使用Iterator将for-each循环编译成一个迭代。
我们还可以看到，使用带有计数器的标准Javafor循环来迭代" ArrayList"，并通过调用" ArrayList"的get()方法获取每个元素，对于具有10的" ArrayList"而言，速度要快大约10％。元素，当ArrayList包含100个元素时，速度提高约12,5％。
究竟为什么会有这样的性能差异是很难说出来的。部分差异可能是由于每次迭代创建一个"迭代器"对象引起的。但是，我们希望当" ArrayList"包含更多元素时，开销会被平分(不太明显)。但是，相反，性能差异似乎有所增加(从10个元素的10％增长到100个元素的12.5％)。这可能是由于CPU对for循环版本进行了更优化的循环执行而引起的，但是我不能肯定地说。
OpenArrayList
OpenArrayList类是对ArrayList的非常简单的模仿，我已经实现了它，以查看它是否可以比ArrayList更快地迭代元素集合。这是OpenArrayList实现的抓取版本：
public Object[] elements = null;
public int capacity = 0;
public int size = 0;
public OpenArrayList(){
}
public OpenArrayList(int capacity){
this.capacity = capacity;
this.elements = new Object[capacity];
}
public OpenArrayList(Object[] elements){
this.elements = elements;
this.capacity = elements.length;
}
public void add(Object element){
this.elements[this.size++] = element;
}
public boolean addIfCapacity(Object element){
if(this.size < this.capacity){
this.elements[this.size++] = element;
return true;
}
return false;
}
}
首先要注意的是，所有" OpenArrayList"成员变量都是公共的。这就是为什么我称其为"开放"。它的成员变量对外界开放。我已经公开了成员变量，以便在迭代OpenArrayList中的元素时可以直接访问elements数组。这应该比调用ArrayListget()方法要快一点，尽管JVM可以优化掉get()方法的调用。
公开元素数组的另一个好处是，我们可以使用System.arraycopy()对其进行写入或者复制，这非常快。
OpenArrayList迭代基准
与" ArrayList"一样，我测量了存储在" OpenArrayList"中的10个对象和100个"长"对象的总和。使用与" ArrayList"基准相同的设置执行基准。
以下是OpenArrayList迭代基准测试(下面带有ArrayList基准测试以便于比较)：
Benchmark Mode Cnt Score Error Units OpenArrayListBenchmark.openArrayList100Sum thrpt 200 16040305.970 ± 1490.153 ops/s OpenArrayListBenchmark.openArrayList10Sum thrpt 200 81301297.431 ± 15104.301 ops/s OpenArrayListBenchmark.jdkArrayList100SumUsingGet thrpt 200 15838998.503 ± 1017.752 ops/s OpenArrayListBenchmark.jdkArrayList100SumUsingForEach thrpt 200 14068898.854 ± 946.976 ops/s OpenArrayListBenchmark.jdkArrayList100SumUsingIterator thrpt 200 14069990.330 ± 512.600 ops/s OpenArrayListBenchmark.jdkArrayList10SumUsingGet thrpt 200 77320532.538 ± 7421.267 ops/s OpenArrayListBenchmark.jdkArrayList10SumUsingForEach thrpt 200 69926532.927 ± 732112.779 ops/s OpenArrayListBenchmark.jdkArrayList10SumUsingIterator thrpt 200 69879781.630 ± 727551.844 ops/s
如我们所见，当" ArrayList"包含100个元素时，" OpenArrayList"迭代速度快约1％，而包含10个元素的迭代速度快约5％。确切地说，为什么存在性能差异，我不能肯定地说。性能如此接近的事实可能表明JVM优化了get()调用。但是，仍然有趣的是，对于较少数量的元素，似乎存在较大的性能差异。
迭代基准代码
这是用于测量ArrayList和OpenArrayList的不同迭代技术的迭代速度的基准代码。
public class OpenArrayListBenchmark {
@State(Scope.Thread)
public static class BenchmarkState {
public ArrayList<Long> jdkArrayList10 = new ArrayList<>();
public ArrayList<Long> jdkArrayList100 = new ArrayList<>();
public OpenArrayList openArrayList10 = new OpenArrayList(10);
public OpenArrayList openArrayList100 = new OpenArrayList(100);
@Setup(Level.Trial)
public void toSetup() {
Object[] elements = openArrayList10.elements;
for(int i=0; i < openArrayList10.capacity; i++){
elements[i] = new Long(i);
jdkArrayList10.add(new Long(i));
}
openArrayList10.size = openArrayList10.capacity;
elements = openArrayList100.elements;
for(int i=0; i < openArrayList100.capacity; i++){
elements[i] = new Long(i);
jdkArrayList100.add(new Long(i));
}
openArrayList100.size = openArrayList100.capacity;
}
}
@Benchmark
@BenchmarkMode(Mode.Throughput)
public long openArrayList10Sum(BenchmarkState state, Blackhole blackhole) {
long sum = 0;
Object[] elements = state.openArrayList10.elements;
for(int i=0; i<state.openArrayList10.size; i++){
sum += ((Long) elements[i]).longValue();
}
blackhole.consume(sum);
return sum;
}
@Benchmark
@BenchmarkMode(Mode.Throughput)
public long openArrayList100Sum(BenchmarkState state, Blackhole blackhole) {
long sum = 0;
Object[] elements = state.openArrayList100.elements;
for(int i=0; i<state.openArrayList100.size; i++){
sum += ((Long) elements[i]).longValue();
}
blackhole.consume(sum);
return sum;
}
@Benchmark
@BenchmarkMode(Mode.Throughput)
public long jdkArrayList10SumUsingGet(BenchmarkState state, Blackhole blackhole) {
long sum = 0;
ArrayList arrayList = state.jdkArrayList10;
for(int i=0, n=state.jdkArrayList10.size(); i < n; i++){
sum += ((Long) arrayList.get(i)).longValue();
}
blackhole.consume(sum);
return sum;
}
@Benchmark
@BenchmarkMode(Mode.Throughput)
public long jdkArrayList100SumUsingGet(BenchmarkState state, Blackhole blackhole) {
long sum = 0;
ArrayList arrayList = state.jdkArrayList100;
for(int i=0, n=state.jdkArrayList100.size(); i < n; i++){
sum += ((Long) arrayList.get(i)).longValue();
}
blackhole.consume(sum);
return sum;
}
@Benchmark
@BenchmarkMode(Mode.Throughput)
public long jdkArrayList10SumUsingForEach(BenchmarkState state, Blackhole blackhole) {
long sum = 0;
for(Long element : state.jdkArrayList10){
sum += element.longValue();
}
blackhole.consume(sum);
return sum;
}
@Benchmark
@BenchmarkMode(Mode.Throughput)
public long jdkArrayList100SumUsingForEach(BenchmarkState state, Blackhole blackhole) {
long sum = 0;
for(Long element : state.jdkArrayList100){
sum += element.longValue();
}
blackhole.consume(sum);
return sum;
}
@Benchmark
@BenchmarkMode(Mode.Throughput)
public long jdkArrayList10SumUsingIterator(BenchmarkState state, Blackhole blackhole) {
long sum = 0;
Iterator<Long> iterator = state.jdkArrayList10.iterator();
while(iterator.hasNext()){
sum += iterator.next().longValue();
}
blackhole.consume(sum);
return sum;
}
@Benchmark
@BenchmarkMode(Mode.Throughput)
public long jdkArrayList100SumUsingIterator(BenchmarkState state, Blackhole blackhole) {
long sum = 0;
Iterator<Long> iterator = state.jdkArrayList100.iterator();
while(iterator.hasNext()){
sum += iterator.next().longValue();
}
blackhole.consume(sum);
return sum;
}
}
