我有一个带有100_000条目和两个方法A和B的hashmap字段。
map.get()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
然后，我想做更多的实验，我用一个常量函数（总是返回整数hashCode()）覆盖了[[hashmap s键（TestKey）的5方法，从本质上说是将哈希表作为一个列表。然后只有我能看到我期望的结果。我没有运行整个测试，因为它需要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;
}
}
}
欢迎提出任何想法和解释。谢谢
map.get调用之间发生了一些Common-Subexpression-Elimination。例如至少可以为每个调用重用hashCode()上testKey方法的结果。或者也许什么都没有发生。
整个效果很容易用缓存位置来解释：第一次访问很昂贵，因为它可能会丢失缓存。以后的访问非常便宜：重新加载刚加载的内容可能会进入L1d缓存。而且乱序执行可以交错所有这些独立的工作，因此，对相同结果的“等待”通常会并行发生10次，具体取决于在JIT优化完成之前每个调用实际运行了多少本机代码。 。 （例如，一个Skylake CPU的重排序缓冲区大小为224微克。）
使用相同的键访问相同的哈希将访问相同的存储位置。
这还意味着您在链接列表上遍历了太多的内存，以至于到开始时它的开头在缓存中仍不很热。因此，以后的遍历并不会从已经获得好处“大放异彩”，并使数据在缓存中变热。
遍历缓存中不热门的链表对CPU来说非常非常糟糕。在知道正确的地址之前，它无法开始下一次加载，但这取决于它正在等待的加载。因此一次只能传输1个负载，没有内存级别的并行性。
（（不同于执行array[i++]的循环可以在数据仍在传输的同时廉价地计算下一个地址的数组。现代的x86（例如Skylake）具有12个“行填充缓冲区”；它可以跟踪12个未完成的请求。如果每次访问的代码+使用的时间足够短，则乱序的exec可以在第二天启动，而每次访问的代码都足够短，则可以使用不同的密钥对未退化的hashmap进行多次访问。第一个仍在运行中（分支预测+投机执行将使这项工作有效，即使代码因该存储桶发生哈希冲突的可能性而分支））计算没有固定的成本，您可以累加起来。在足够小的规模下，吞吐量与延迟对于流水线/无序执行很重要。高速缓存很重要：当高速缓存+分支预测输入图片时，重新-
。 （对于少量数据，例如，x86上通常有快速的每核32kiB L1d高速缓存和256kiB L2高速缓存。Skylake-Xeon每核具有1MiB L2高速缓存。）