数组列表的速度是否比数组慢两倍以上?

2022-09-04 21:24:46

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

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

我对结果有点惊讶

  • 盒装数组(即 vs ) 并不比原始版本慢很多Integerint
  • 基础数组的大小并不重要
  • ArrayLists 的速度是相应数组的两倍多。

问题

  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 个单元格中的值相加(无论数组有多大),并将其添加到总值中。卡尺告诉我测试应该运行多少次,所以我循环了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]);
    }
}

答案 1

首先。。。

数组列表的速度是否比数组慢两倍以上?

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

对于其他操作,可能会较慢,尽管性能比很可能取决于操作和 JVM 实现。另请注意,您只测试了一个操作/模式。ArrayList

为什么ArrayList这么慢?

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

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

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

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

从技术上讲,这没有什么错。但这还不足以证明你的观点。首先,您只是在测量一种操作:数组元素获取及其等效项。而且您只是在测量基元类型。


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


答案 2

请记住,在使用 ArrayList 时,您实际上是在调用一个函数,而在实际调用其他两个函数的情况下,该函数实际上是在调用函数。(其中之一是范围检查,我怀疑这可能是延迟的一部分)。get()

ArrayList的重要之处不在于它与直数组相比快多少或多慢,而在于它的访问时间总是恒定的(如数组)。在现实世界中,您几乎总是会发现增加的延迟可以忽略不计。特别是如果你有一个应用程序,甚至考虑连接到数据库。:)

简而言之,我认为你的测试(和结果)是合法的。