ArrayLists 比数组慢两倍多吗? [英] Are ArrayLists more than twice as slow as arrays?

问题描述

我写了一个测试，试图测试两件事:

I wrote a test that attempts to test two things:

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

我对结果有点惊讶

• 盒装数组(即Integer vs int)并不比原始版本慢很多
• 底层数组的大小无关紧要
• ArrayLists 的速度是对应数组的两倍多.

• Boxed arrays (i.e. Integer vs int) are not very much slower than the primitive version
• The size of the underlying array doesn't matter very much
• ArrayLists are more than twice as slow as the corresponding array.

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

代码

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

The Code

This code was written in Windows using Java 7 and Google caliper 0.5-rc1 (because last I checked 1.0 doesn't work in Windows yet).

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

Quick outline: in all 6 tests, in each iteration of the loop, it adds the values in the first 128 cells of the array (no matter how big the array is) and adds that to a total value. Caliper tells me how many times the test should run, so I loop through that addition 128 times.

这 6 个测试有一个大 (131072) 和一个小 (128) 版本的 int[]、Integer[] 和 ArrayList;.你大概可以从名字中找出哪个是哪个.

The 6 tests have a big (131072) and a small (128) version of int[], Integer[], and ArrayList<Integer>. You can probably figure out which is which from the names.

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]);
    }
}

推荐答案

首先...

ArrayList 是否比数组慢两倍多?

Are ArrayLists more than twice as slow as arrays?

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

As a generalization, no. For operations that potentially involve "changing" the length of the list / array, an ArrayList will be faster than an array ... unless you use a separate variable to represent the array's logical size.

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

For other operations, the ArrayList is likely to be slower, though the performance ratio will most likely depend on the operation and the JVM implementation. Also note that you have only tested one operation / pattern.

为什么 ArrayList 这么慢?

Why is ArrayList so much slower?

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

Because an ArrayList has a distinct array object inside of it.

• 操作通常涉及额外的间接访问(例如获取列表的大小和内部数组)，并且还有额外的边界检查(例如检查列表的 size 和数组的长度).典型的 JIT 编译器(显然)无法优化这些.(事实上​​，您不会想要优化掉内部数组，因为那是允许 ArrayList 增长的原因.)

• Operations typically involve extra indirections (e.g. to fetch the list's size and inner array) and there are extra bounds checks (e.g. checking the list's size and the array's length). A typical JIT compiler is (apparently) not able to optimize these away. (And in fact, you would NOT want to optimize away the inner array because that's what allows an ArrayList to grow.)

对于基元数组，相应的列表类型涉及包装基元类型/对象，这增加了开销.例如，在列表"情况下，您的 result += ... 涉及拆箱.

For array's of primitives, the corresponding list types involve wrapped primitive types / objects, and that adds an overhead. For example your result += ... involves unboxing, in the "list" cases.

我的基准测试写得好吗?换句话说，我的结果准确吗?

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

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

There's nothing wrong with it technically. But it is not sufficient to demonstrate your point. For a start, you are only measuring one kind of operation: array element fetching and its equivalent. And you are only measuring for primitive types.

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

Finally, this largely misses the point of using List types. We use them because they are almost always easier to use than plain arrays. A difference in performance of (say) 2 is typically not important to overall application performance.

这篇关于ArrayLists 比数组慢两倍多吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！