JMH ArrayList LinkedList 性能测试

Question

下面的性能测试是错误的

直接对列表添加操作，测试结果不正确

@BenchmarkMode(Mode.Throughput)
@State(Scope.Thread)
@OutputTimeUnit(TimeUnit.SECONDS)
@Warmup(iterations = 1, time = 1)
@Measurement(iterations = 1, time = 1)
@Fork(1)
public class ListBenchmark1 {
    public List<String> array  = new ArrayList<>();
    public List<String> linked = new LinkedList<>();

    @Benchmark
    public void testArray(Blackhole bh) {
        array.add("1");
        bh.consume(array);
    }

    @Benchmark
    public void testLinked(Blackhole bh) {
        linked.add("1");
        bh.consume(linked);
    }
}

Benchmark                   Mode  Cnt         Score   Error  Units
ListBenchmark1.testArray   thrpt       49775951.966          ops/s
ListBenchmark1.testLinked  thrpt        2711816.352          ops/s

数组 > 链表

这是一个正确的性能测试

一个中间的class用于存储属性，添加了class中的列表，测试结果正确

@BenchmarkMode(Mode.Throughput)
@OutputTimeUnit(TimeUnit.SECONDS)
@Warmup(iterations = 1, time = 1)
@Measurement(iterations = 1, time = 1)
@Fork(1)
public class ListBenchmark {

    @State(Scope.Thread)
    public static class ArrayClass {
        public List<String> list;

        @Setup(Level.Invocation)
        public void setup() {
            list = new ArrayList<>();
        }
    }

    @State(Scope.Thread)
    public static class LinkedClass {
        public List<String> list;

        @Setup(Level.Invocation)
        public void setup() {
            list = new LinkedList<>();
        }
    }

    @Benchmark
    public List<String> testArray(ArrayClass array) {
        array.list.add("1");
        return array.list;
    }

    @Benchmark
    public List<String> testLinked(LinkedClass linked) {
        linked.list.add("1");
        return linked.list;
    }
}

Benchmark                   Mode  Cnt         Score   Error  Units
ListBenchmark.testArray    thrpt       23828227.679          ops/s
ListBenchmark.testLinked   thrpt       28603947.913          ops/s

数组列表<链表

为什么这两种不同的测试方法结果不正确

都是加操作。为什么会有这样的反差？

Answer 1

现在有了JMH给的数字好多了。

第一个运行

首先运行你将列表增加到一个巨大的大小（因为你不会每次都重新创建它们）所以你主要衡量向一个已经很大的列表添加一个元素的性能。有趣的是，这个测试是不公平的，因为更快的列表（ArrayList 正如预期的那样）增长到更大的大小并且必须管理这个更大的大小。

无论如何，这是我们所期望的。

第二个运行

在第二个运行上，您在每个运行之间重新初始化列表，并且在运行中执行非常简单的操作。这迫使 JMH 在每次调用之间执行测量，而不是进行多次调用并获得整体测量。

这意味着您的结果将远不那么精确，并且您根本不会测量相同的东西。您测量列表从大小 0 增长到 1。

最重要的是，如果您查看 ArrayList 的源代码，数组的分配仅在您添加第一个元素时完成。创建列表时，没有分配。

因此 ArrayList 在第二次测试中表现不佳，因为您分配了 10 个元素的数组 (https://hg.openjdk.java.net/jdk8/jdk8/jdk/file/tip/src/share/classes/java/util/ArrayList.java)。

您是否会在 init 中向每个列表添加一个元素，然后再对添加的元素进行基准测试，ArrayList 将再次变得比 LinkedList 快得多。

还是

要获得准确的结果，请进行更多迭代并延长预热时间。对我而言，每秒操作至少要快一个数量级。

另外请确保您的列表不要太大，否则会导致 OutOfMemory 错误。

Answer 2

如果你真的想知道如果你向这两个列表添加元素时有对比，你可能想先写一个正确的测试。例如：

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.SECONDS)
@Warmup(iterations = 5, time = 5)
@Measurement(iterations = 5, time = 5)
@Fork(1)
public class LinkedVsArrayList {

    public static void main(String[] args) throws Exception {
        Options opt = new OptionsBuilder()
            .include(LinkedVsArrayList.class.getSimpleName())
            .build();

        new Runner(opt).run();
    }

    @Param({"1", "10", "100", "1000", "10000"})
    public int howMany;

    @Benchmark
    public List<String> testArray() {
        List<String> list = new ArrayList<>();
        for (int i = 0; i < howMany; ++i) {
            list.add("" + i);
        }
        return list;
    }

    @Benchmark
    public List<String> testLinked() {
        List<String> list = new LinkedList<>();
        for (int i = 0; i < howMany; ++i) {
            list.add("" + i);
        }
        return list;
    }
}

这会将 1、10、100... 元素添加到某些 List。我将向您展示 100 和 1000:

的结果

LinkedVsArrayList.testArray         100  thrpt    5  840.171 ± 111.088  ops/ms
LinkedVsArrayList.testLinked        100  thrpt    5  847.743 ± 111.039  ops/ms

LinkedVsArrayList.testArray        1000  thrpt    5   72.675 ±   5.367  ops/ms
LinkedVsArrayList.testLinked       1000  thrpt    5   69.218 ±   6.093  ops/ms

结果非常接近，这表明即使 ArrayList 在幕后有一个 array（相对于 LinkedList），这也没有区别。

JMH ArrayList LinkedList 性能测试

JMH ArrayList LinkedList Performance test

java

jmh