为什么HashMaps 10 get()调用性能笔记比单个get()性能差10倍

Question

我有一个 hashmap 字段，其中包含 100_000 个条目和两个方法 A 和 B。

方法 A：使用随机密钥

map.get()

方法 B : 使用 a 随机密钥调用 map.get() 十次（每次都使用相同的密钥）

我多次使用 JMH 到运行配置这两种方法（整个测试在我的 Macbook pro 上花费了 1 个多小时）并测量了吞吐量，结果是 方法A 只比 方法 B 快两倍左右。我希望有 10 倍的差异。

我无法解释这种行为，这是结果

# Run complete. Total time: 01:08:36

Benchmark                           Mode  Throughput           Units
TestClass.benchmark_with_one_get   thrpt   23819.007   operations/ms
TestClass.benchmark_with_ten_gets  thrpt   12021.025   operations/ms

然后我想做更多的实验，我用一个常量函数（总是return integer 5) 本质上使 hashmap 成为一个列表。然后只有我能看到我期待的结果。我没有运行整个测试，因为它需要 6 个多小时才能完成，但这是粗略的结果（仅来自前 2 次迭代）

Benchmark                           Mode   Throughput             Units
TestClass.benchmark_with_one_get   thrpt      244.266      operations/s
TestClass.benchmark_with_ten_gets  thrpt       24.981      operations/s

这是我用来进行基准测试的原始 class。

package test.benchmark;

import org.openjdk.jmh.annotations.*;

import java.util.*;
import java.util.concurrent.TimeUnit;

@State(Scope.Benchmark)
public class TestClass {

    private Map<TestKey, Integer> map = new HashMap<>();
    private List<TestKey> keyList = new ArrayList<>();
    private int test1 = 0;
    private int test2 = 0;

    public TestClass() {
        Random random = new Random();
        for (int i = 0; i < 100_000; i++) {
            TestKey testKey = new TestKey(i);
            map.put(testKey, i);
            keyList.add(new TestKey(random.nextInt(100_001)));
        }
    }

    @Setup
    public void setup() {
        Random random = new Random();
        int tmp = random.nextInt(100_001);
        test1 = tmp;
        test2 = tmp;
    }

    @Benchmark
    @BenchmarkMode(Mode.Throughput)
    @Measurement(iterations = 20, time = 10)
    @OutputTimeUnit(TimeUnit.MILLISECONDS)
    @Warmup(iterations = 5)
    public boolean benchmark_with_one_get() {

        TestKey testKey = keyList.get(test1);
        map.get(testKey);
        test1++;
        if (test1 >= 100_000) {
            test1 = 0;
        }
        return true;
    }

    @Benchmark
    @OutputTimeUnit(TimeUnit.MILLISECONDS)
    @Measurement(iterations = 20, time = 10)
    @BenchmarkMode(Mode.Throughput)
    @Warmup(iterations = 5)
    public boolean benchmark_with_ten_gets() {

        TestKey testKey = keyList.get(test2);
        map.get(testKey);
        map.get(testKey);
        map.get(testKey);
        map.get(testKey);
        map.get(testKey);
        map.get(testKey);
        map.get(testKey);
        map.get(testKey);
        map.get(testKey);
        map.get(testKey);
        test2++;
        if (test2 >= 100_000) {
            test2 = 0;
        }

        return true;
    }


    public class TestKey {
        private int key;

        public TestKey(int key) {
            this.key = key;
        }

        public int getKey() {
            return key;
        }

        @Override
        public boolean equals(Object obj) {
            return obj instanceof TestKey && ((TestKey) obj).key == this.key;
        }

        @Override
        public int hashCode() {
            return 31 * 17 + key;
        }

    }
}

欢迎任何想法和解释。谢谢

Answer 1

有点令人失望的是 JVM 没有完全优化访问，因为您没有使用 map.get(testKey);

的结果

或至少 CSE 多次调用同一函数。也许一些公共子表达式消除在单独的 map.get 调用中发生了。例如至少你的 testKey 上的 hashCode() 方法的结果可以在每次调用中重复使用。

或者可能会发生 none。

缓存局部性很容易解释整个效果：第一次访问很昂贵，因为它可能未命中缓存。以后的访问非常便宜：重新加载你刚刚加载的东西可以在 L1d 缓存中命中。并且乱序执行可以交错所有这些独立的工作，因此“等待”相同结果 10 次基本上是并行发生的，具体取决于 JIT 时每次调用实际运行s 的本机机器代码数量优化是用它完成的。（例如，Skylake CPU 的重新排序缓冲区大小为 224 uops。）

使用相同的密钥访问相同的散列将访问相同的内存位置。

让hash map退化变成链表搜索意味着每次访问都需要很长时间，比乱序执行的时间还长window 大小，因此即使是现代高端 CPU 也无法找到并利用指令级并行性和交错工作。

这也意味着您在遍历该链表时接触了太多内存，以至于当您到达末尾时它的开头在缓存中还不是很热。 所以以后的遍历不会受益于已经“开辟了道路”并在缓存中获取热数据。

遍历缓存中不热的链表对于 CPU 来说非常非常糟糕。在知道正确的地址之前，它无法开始下一次加载，但这取决于它正在等待的加载。所以一次只能运行 1 个负载，没有内存级并行性。

（与数组不同，在数组中，执行 array[i++] 的循环可以在数据仍在传输时廉价地计算下一个地址。像 Skylake 这样的现代 x86 有类似 12 个“行填充缓冲区”的东西；它可以并行跟踪对不同缓存行 in/out 的 12 个未完成请求。如果每次访问和使用的代码足够短以至于乱序执行，则使用不同键多次访问非退化哈希图可以利用这一点可以在第 2 天开始，而第一个还在飞行中。（分支预测 + 推测性执行将让这个工作，即使代码分支关于该桶的哈希冲突的可能性））

要点：

计算没有固定成本，您可以将其相加。在足够小的规模下，吞吐量与延迟对于流水线/无序执行很重要。
缓存很重要：当缓存+分支预测进入画面时，在相同数据上重新运行第二次运行速度更快。（对于少量数据，例如快速的每核 32kiB L1d 缓存和 256kiB L2 缓存在 x86 上很常见。Skylake-Xeon 每个核心有 1MiB L2 缓存。）
编译器（可能）很聪明，可以在过于简单的基准测试尝试中优化掉多余的工作。

像 Java 这样的 JIT 编译语言也有这样的效果，即代码在运行多次之前甚至没有得到完全优化，但这与上述效果不同甚至适用于机器代码。

为什么HashMaps 10 get()调用性能笔记比单个get()性能差10倍

Why HashMaps 10 get() call performance not 10 times worst than a single get() performance

java

performance

benchmarking

jvm

hashmap