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

Question

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

• 方法 A:使用随 secret 钥调用 map.get() 一次
• 方法 B:使用 a 随 secret 钥(每次相同的 key )调用 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

然后我想做更多的实验，我用一个常量函数覆盖了 hashmap 键 (TestKey) 的 hashCode() 方法(始终返回整数 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

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

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 调用中发生了一些 Common-Subexpression-Elimination。例如至少 testKey 上的 hashCode() 方法的结果可以在每次调用中重复使用。

或者也许这一切都没有发生。

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

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

---

使散列映射退化，使其变成链表搜索意味着每次访问都需要很长时间，超过乱序执行窗口大小，所以即使是现代高- 端 CPU 无法找到并利用指令级并行性和交错工作。

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

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

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

---

要点:

• 计算没有固定成本，您可以将其相加。在足够小的规模下，吞吐量与延迟对于流水线/无序执行很重要。

• 缓存很重要:当缓存 + 分支预测进入画面时，对相同数据重新运行相同代码第二次可以更快。 (对于少量数据，例如快速的每核 32kiB L1d 缓存和 256kiB L2 缓存在 x86 上很常见。Skylake-Xeon 每个核心有 1MiB L2 缓存。)

• 编译器(可能)很聪明，可以在过于简单的基准测试尝试中优化掉多余的工作。

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