为什么我的 Intel Skylake / Kaby Lake CPU 在简单的哈希表实现中会出现神秘的 3 倍速度下降？
Mar*_*ens 79 c++ performance gcc hashtable x86-64
简而言之：
我已经实现了一个简单的（多键）哈希表，其中包含完全适合缓存行的存储桶（包含多个元素）。插入缓存行存储桶非常简单，也是主循环的关键部分。
我已经实现了三个版本，它们产生相同的结果并且行为应该相同。
谜
然而，尽管所有版本都具有完全相同的缓存行访问模式并产生相同的哈希表数据，但我发现性能差异惊人地大到了 3 倍。
与我的 CPU (i7-7700HQ)相比，最佳实现insert_ok速度慢了大约 3 倍。一个变体 insert_bad 是一种简单的修改，它在缓存行中添加了额外的不必要的线性搜索，以找到要写入的位置（它已经知道），并且不会遭受 3 倍的减速。insert_badinsert_altinsert_ok
与其他 CPU（AMD 5950X (Zen 3)、Intel i7-11800H (Tiger Lake)）相比，完全相同的可执行文件显示insert_ok速度快 1.6 倍。insert_badinsert_alt
# see https://github.com/cr-marcstevens/hashtable_mystery
$ ./test.sh
model name : Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
==============================
CXX=g++ CXXFLAGS=-std=c++11 -O2 -march=native -falign-functions=64
tablesize: 117440512 elements: 67108864 loadfactor=0.571429
- test insert_ok : 11200ms
- test insert_bad: 3164ms
(outcome identical to insert_ok: true)
- test insert_alt: 3366ms
(outcome identical to insert_ok: true)
tablesize: 117440813 elements: 67108864 loadfactor=0.571427
- test insert_ok : 10840ms
- test insert_bad: 3301ms
(outcome identical to insert_ok: true)
- test insert_alt: 3579ms
(outcome identical to insert_ok: true)
代码
// insert element in hash_table
inline void insert_ok(uint64_t k)
{
// compute target bucket
uint64_t b = mod(k);
// bounded linear search for first non-full bucket
for (size_t c = 0; c < 1024; ++c)
{
bucket_t& B = table_ok[b];
// if bucket non-full then store element and return
if (B.size != bucket_size)
{
B.keys[B.size] = k;
B.values[B.size] = 1;
++B.size;
++table_count;
return;
}
// increase b w/ wrap around
if (++b == table_size)
b = 0;
}
}
// equivalent to insert_ok
// but uses a stupid linear search to store the element at the target position
inline void insert_bad(uint64_t k)
{
// compute target bucket
uint64_t b = mod(k);
// bounded linear search for first non-full bucket
for (size_t c = 0; c < 1024; ++c)
{
bucket_t& B = table_bad[b];
// if bucket non-full then store element and return
if (B.size != bucket_size)
{
for (size_t i = 0; i < bucket_size; ++i)
{
if (i == B.size)
{
B.keys[i] = k;
B.values[i] = 1;
++B.size;
++table_count;
return;
}
}
}
// increase b w/ wrap around
if (++b == table_size)
b = 0;
}
}
// instead of using bucket_t.size, empty elements are marked by special empty_key value
// a bucket is filled first to last, so bucket is full if last element key != empty_key
uint64_t empty_key = ~uint64_t(0);
inline void insert_alt(uint64_t k)
{
// compute target bucket
uint64_t b = mod(k);
// bounded linear search for first non-full bucket
for (size_t c = 0; c < 1024; ++c)
{
bucket_t& B = table_alt[b];
// if bucket non-full then store element and return
if (B.keys[bucket_size-1] == empty_key)
{
for (size_t i = 0; i < bucket_size; ++i)
{
if (B.keys[i] == empty_key)
{
B.keys[i] = k;
B.values[i] = 1;
++table_count;
return;
}
}
}
// increase b w/ wrap around
if (++b == table_size)
b = 0;
}
}
我的分析
我尝试了对循环 C++ 的各种修改，但本质上它非常简单，编译器将生成相同的程序集。从最终的组装结果来看，因子 3 损失可能会导致什么，这一点并不明显。我尝试过用 perf 进行测量，但我似乎无法指出任何有意义的差异。
比较 3 个版本的汇编，这 3 个版本都只是相对较小的循环，没有任何迹象表明任何接近的情况可能会导致这些版本之间的因子 3 损失。
因此，我认为 3 倍的减慢是自动预取、分支预测、指令/跳转对齐或可能是这些的组合的奇怪效果。
有没有人有更好的见解或方法来衡量这里实际可能产生的影响？
细节
我创建了一个小型的 C++11 工作示例来演示该问题。代码可在https://github.com/cr-marcstevens/hashtable_mystery获取
这还包括我自己的静态二进制文件，它们在我的 CPU 上演示了这个问题，因为不同的编译器可能会生成不同的代码。以及所有三个哈希表版本的转储汇编代码。
性能事件测量
这里有很多性能事件测量。我重点关注那些包含单词missand的内容stall。每个事件有两行：
- 第一行对应于
insert_ok减速的行 - 第二行对应
insert_alt有一个额外的循环和额外的工作，但最终速度更快
=== L1-dcache-load-misses ===
insert_ok : 171411476
insert_alt: 244244027
=== L1-dcache-loads ===
insert_ok : 775468123
insert_alt: 1038574743
=== L1-dcache-stores ===
insert_ok : 621353009
insert_alt: 554244145
=== L1-icache-load-misses ===
insert_ok : 69666
insert_alt: 259102
=== LLC-load-misses ===
insert_ok : 70519701
insert_alt: 71399242
=== LLC-loads ===
insert_ok : 130909270
insert_alt: 134776189
=== LLC-store-misses ===
insert_ok : 16782747
insert_alt: 16851787
=== LLC-stores ===
insert_ok : 17072141
insert_alt: 17534866
=== arith.divider_active ===
insert_ok : 26810
insert_alt: 26611
=== baclears.any ===
insert_ok : 2038060
insert_alt: 7648128
=== br_inst_retired.all_branches ===
insert_ok : 546479449
insert_alt: 938434022
=== br_inst_retired.all_branches_pebs ===
insert_ok : 546480454
insert_alt: 938412921
=== br_inst_retired.cond_ntaken ===
insert_ok : 237470651
insert_alt: 433439086
=== br_inst_retired.conditional ===
insert_ok : 477604946
insert_alt: 802468807
=== br_inst_retired.far_branch ===
insert_ok : 1058138
insert_alt: 1052510
=== br_inst_retired.near_call ===
insert_ok : 227076
insert_alt: 227074
=== br_inst_retired.near_return ===
insert_ok : 227072
insert_alt: 227070
=== br_inst_retired.near_taken ===
insert_ok : 307946256
insert_alt: 503926433
=== br_inst_retired.not_taken ===
insert_ok : 237458763
insert_alt: 433429466
=== br_misp_retired.all_branches ===
insert_ok : 36443541
insert_alt: 90626754
=== br_misp_retired.all_branches_pebs ===
insert_ok : 36441027
insert_alt: 90622375
=== br_misp_retired.conditional ===
insert_ok : 36454196
insert_alt: 90591031
=== br_misp_retired.near_call ===
insert_ok : 173
insert_alt: 169
=== br_misp_retired.near_taken ===
insert_ok : 19032467
insert_alt: 40361420
=== branch-instructions ===
insert_ok : 546476228
insert_alt: 938447476
=== branch-load-misses ===
insert_ok : 36441314
insert_alt: 90611299
=== branch-loads ===
insert_ok : 546472151
insert_alt: 938435143
=== branch-misses ===
insert_ok : 36436325
insert_alt: 90597372
=== bus-cycles ===
insert_ok : 222283508
insert_alt: 88243938
=== cache-misses ===
insert_ok : 257067753
insert_alt: 475091979
=== cache-references ===
insert_ok : 445465943
insert_alt: 590770464
=== cpu-clock ===
insert_ok : 10333.94 msec cpu-clock:u # 1.000 CPUs utilized
insert_alt: 4766.53 msec cpu-clock:u # 1.000 CPUs utilized
=== cpu-cycles ===
insert_ok : 25273361574
insert_alt: 11675804743
=== cpu_clk_thread_unhalted.one_thread_active ===
insert_ok : 223196489
insert_alt: 88616919
=== cpu_clk_thread_unhalted.ref_xclk ===
insert_ok : 222719013
insert_alt: 88467292
=== cpu_clk_unhalted.one_thread_active ===
insert_ok : 223380608
insert_alt: 88212476
=== cpu_clk_unhalted.ref_tsc ===
insert_ok : 32663820508
insert_alt: 12901195392
=== cpu_clk_unhalted.ref_xclk ===
insert_ok : 221957996
insert_alt: 88390991
insert_alt: === cpu_clk_unhalted.ring0_trans ===
insert_ok : 374
insert_alt: 373
=== cpu_clk_unhalted.thread ===
insert_ok : 25286801620
insert_alt: 11714137483
=== cycle_activity.cycles_l1d_miss ===
insert_ok : 16278956219
insert_alt: 7417877493
=== cycle_activity.cycles_l2_miss ===
insert_ok : 15607833569
insert_alt: 7054717199
=== cycle_activity.cycles_l3_miss ===
insert_ok : 12987627072
insert_alt: 6745771672
=== cycle_activity.cycles_mem_any ===
insert_ok : 23440206343
insert_alt: 9027220495
=== cycle_activity.stalls_l1d_miss ===
insert_ok : 16194872307
insert_alt: 4718344050
=== cycle_activity.stalls_l2_miss ===
insert_ok : 15350067722
insert_alt: 4578933898
=== cycle_activity.stalls_l3_miss ===
insert_ok : 12697354271
insert_alt: 4457980047
=== cycle_activity.stalls_mem_any ===
insert_ok : 20930005455
insert_alt: 4555461595
=== cycle_activity.stalls_total ===
insert_ok : 22243173394
insert_alt: 6561416461
=== dTLB-load-misses ===
insert_ok : 67817362
insert_alt: 63603879
=== dTLB-loads ===
insert_ok : 775467642
insert_alt: 1038562488
=== dTLB-store-misses ===
insert_ok : 8823481
insert_alt: 13050341
=== dTLB-stores ===
insert_ok : 621353007
insert_alt: 554244145
=== dsb2mite_switches.count ===
insert_ok : 93894397
insert_alt: 315793354
=== dsb2mite_switches.penalty_cycles ===
insert_ok : 9216240937
insert_alt: 206393788
=== dtlb_load_misses.miss_causes_a_walk ===
insert_ok : 177266866
insert_alt: 101439773
=== dtlb_load_misses.stlb_hit ===
insert_ok : 2994329
insert_alt: 35601646
=== dtlb_load_misses.walk_active ===
insert_ok : 4747616986
insert_alt: 3893609232
=== dtlb_load_misses.walk_completed ===
insert_ok : 67817832
insert_alt: 63591832
=== dtlb_load_misses.walk_completed_4k ===
insert_ok : 67817841
insert_alt: 63596148
=== dtlb_load_misses.walk_pending ===
insert_ok : 6495600072
insert_alt: 5987182579
=== dtlb_store_misses.miss_causes_a_walk ===
insert_ok : 89895924
insert_alt: 21841494
=== dtlb_store_misses.stlb_hit ===
insert_ok : 4940907
insert_alt: 21970231
=== dtlb_store_misses.walk_active ===
insert_ok : 1784142210
insert_alt: 903334856
=== dtlb_store_misses.walk_completed ===
insert_ok : 8845884
insert_alt: 13071262
=== dtlb_store_misses.walk_completed_4k ===
insert_ok : 8822993
insert_alt: 12936414
=== dtlb_store_misses.walk_pending ===
insert_ok : 1842905733
insert_alt: 933039119
=== exe_activity.1_ports_util ===
insert_ok : 991400575
insert_alt: 1433908710
=== exe_activity.2_ports_util ===
insert_ok : 782270731
insert_alt: 1314443071
=== exe_activity.3_ports_util ===
insert_ok : 556847358
insert_alt: 1158115803
=== exe_activity.4_ports_util ===
insert_ok : 427323800
insert_alt: 783571280
=== exe_activity.bound_on_stores ===
insert_ok : 299732094
insert_alt: 303475333
=== exe_activity.exe_bound_0_ports ===
insert_ok : 227569792
insert_alt: 348959512
=== frontend_retired.dsb_miss ===
insert_ok : 6771584
insert_alt: 93700643
=== frontend_retired.itlb_miss ===
insert_ok : 1115
insert_alt: 1689
=== frontend_retired.l1i_miss ===
insert_ok : 3639
insert_alt: 3857
=== frontend_retired.l2_miss ===
insert_ok : 2826
insert_alt: 2830
=== frontend_retired.latency_ge_1 ===
insert_ok : 9206268
insert_alt: 178345368
=== frontend_retired.latency_ge_128 ===
insert_ok : 2708
insert_alt: 2703
=== frontend_retired.latency_ge_16 ===
insert_ok : 403492
insert_alt: 820950
=== frontend_retired.latency_ge_2 ===
insert_ok : 4981263
insert_alt: 85781924
=== frontend_retired.latency_ge_256 ===
insert_ok : 802
insert_alt: 970
=== frontend_retired.latency_ge_2_bubbles_ge_1 ===
insert_ok : 56936702
insert_alt: 225712704
=== frontend_retired.latency_ge_2_bubbles_ge_2 ===
insert_ok : 10312026
insert_alt: 163227996
=== frontend_retired.latency_ge_2_bubbles_ge_3 ===
insert_ok : 7599252
insert_alt: 122841752
=== frontend_retired.latency_ge_32 ===
insert_ok : 3599
insert_alt: 3317
=== frontend_retired.latency_ge_4 ===
insert_ok : 2627373
insert_alt: 42287077
=== frontend_retired.latency_ge_512 ===
insert_ok : 418
insert_alt: 241
=== frontend_retired.latency_ge_64 ===
insert_ok : 2474
insert_alt: 2802
=== frontend_retired.latency_ge_8 ===
insert_ok : 528748
insert_alt: 951836
=== frontend_retired.stlb_miss ===
insert_ok : 769
insert_alt: 562
=== hw_interrupts.received ===
insert_ok : 9330
insert_alt: 3738
=== iTLB-load-misses ===
insert_ok : 456094
insert_alt: 90739
=== iTLB-loads ===
insert_ok : 949
insert_alt: 1031
=== icache_16b.ifdata_stall ===
insert_ok : 1145821
insert_alt: 862403
=== icache_64b.iftag_hit ===
insert_ok : 1378406022
insert_alt: 4459469241
=== icache_64b.iftag_miss ===
insert_ok : 61812
insert_alt: 57204
=== icache_64b.iftag_stall ===
insert_ok : 56551468
insert_alt: 82354039
=== idq.all_dsb_cycles_4_uops ===
insert_ok : 896374829
insert_alt: 1610100578
=== idq.all_dsb_cycles_any_uops ===
insert_ok : 1217878089
insert_alt: 2739912727
=== idq.all_mite_cycles_4_uops ===
insert_ok : 315979501
insert_alt: 480165021
=== idq.all_mite_cycles_any_uops ===
insert_ok : 1053703958
insert_alt: 2251382760
=== idq.dsb_cycles ===
insert_ok : 1218891711
insert_alt: 2744099964
=== idq.dsb_uops ===
insert_ok : 5828442701
insert_alt: 10445095004
=== idq.mite_cycles ===
insert_ok : 470409312
insert_alt: 1664892371
=== idq.mite_uops ===
insert_ok : 1407396065
insert_alt: 4515396737
=== idq.ms_cycles ===
insert_ok : 583601361
insert_alt: 587996351
=== idq.ms_dsb_cycles ===
insert_ok : 218346
insert_alt: 74155
=== idq.ms_mite_uops ===
insert_ok : 1266443204
insert_alt: 1277980465
=== idq.ms_switches ===
insert_ok : 149106449
insert_alt: 150392336
=== idq.ms_uops ===
insert_ok : 1266950097
insert_alt: 1277330690
=== idq_uops_not_delivered.core ===
insert_ok : 1871959581
insert_alt: 6531069387
=== idq_uops_not_delivered.cycles_0_uops_deliv.core ===
insert_ok : 289301660
insert_alt: 946930713
=== idq_uops_not_delivered.cycles_fe_was_ok ===
insert_ok : 24668869613
insert_alt: 9335642949
=== idq_uops_not_delivered.cycles_le_1_uop_deliv.core ===
insert_ok : 393750384
insert_alt: 1344106460
=== idq_uops_not_delivered.cycles_le_2_uop_deliv.core ===
insert_ok : 506090534
insert_alt: 1824690188
=== idq_uops_not_delivered.cycles_le_3_uop_deliv.core ===
insert_ok : 688462029
insert_alt: 2416339045
=== ild_stall.lcp ===
insert_ok : 380
insert_alt: 480
=== inst_retired.any ===
insert_ok : 4760842560
insert_alt: 5470438932
=== inst_retired.any_p ===
insert_ok : 4760919037
insert_alt: 5470404264
=== inst_retired.prec_dist ===
insert_ok : 4760801654
insert_alt: 5470649220
=== inst_retired.total_cycles_ps ===
insert_ok : 25175372339
insert_alt: 11718929626
=== instructions ===
insert_ok : 4760805219
insert_alt: 5470497783
=== int_misc.clear_resteer_cycles ===
insert_ok : 199623562
insert_alt: 671083279
=== int_misc.recovery_cycles ===
insert_ok : 314434729
insert_alt: 704406698
=== itlb.itlb_flush ===
insert_ok : 303
insert_alt: 248
=== itlb_misses.miss_causes_a_walk ===
insert_ok : 19537
insert_alt: 116729
=== itlb_misses.stlb_hit ===
insert_ok : 11323
insert_alt: 5557
=== itlb_misses.walk_active ===
insert_ok : 2809766
insert_alt: 4070194
=== itlb_misses.walk_completed ===
insert_ok : 24298
insert_alt: 45251
=== itlb_misses.walk_completed_4k ===
insert_ok : 34084
insert_alt: 29759
=== itlb_misses.walk_pending ===
insert_ok : 853764
insert_alt: 2817933
=== l1d.replacement ===
insert_ok : 171135334
insert_alt: 244967326
=== l1d_pend_miss.fb_full ===
insert_ok : 354631656
insert_alt: 382309583
=== l1d_pend_miss.pending ===
insert_ok : 16792436441
insert_alt: 22979721104
=== l1d_pend_miss.pending_cycles ===
insert_ok : 16377420892
insert_alt: 7349245429
=== l1d_pend_miss.pending_cycles_any ===
insert_ok : insert_alt: === l2_lines_in.all ===
insert_ok : 303009088
insert_alt: 411750486
=== l2_lines_out.non_silent ===
insert_ok : 157208112
insert_alt: 309484666
=== l2_lines_out.silent ===
insert_ok : 127379047
insert_alt: 84169481
=== l2_lines_out.useless_hwpf ===
insert_ok : 70374658
insert_alt: 144359127
=== l2_lines_out.useless_pref ===
insert_ok : 70747103
insert_alt: 142931540
=== l2_rqsts.all_code_rd ===
insert_ok : 71254
insert_alt: 242327
=== l2_rqsts.all_demand_data_rd ===
insert_ok : 137366274
insert_alt: 143507049
=== l2_rqsts.all_demand_miss ===
insert_ok : 150071420
insert_alt: 150820168
=== l2_rqsts.all_demand_references ===
insert_ok : 154854022
insert_alt: 160487082
=== l2_rqsts.all_pf ===
insert_ok : 170261458
insert_alt: 282476184
=== l2_rqsts.all_rfo ===
insert_ok : 17575896
insert_alt: 16938897
=== l2_rqsts.code_rd_hit ===
insert_ok : 79800
insert_alt: 381566
=== l2_rqsts.code_rd_miss ===
insert_ok : 25800
insert_alt: 33755
=== l2_rqsts.demand_data_rd_hit ===
insert_ok : 5191029
insert_alt: 9831101
=== l2_rqsts.demand_data_rd_miss ===
insert_ok : 132253891
insert_alt: 133965310
=== l2_rqsts.miss ===
insert_ok : 305347974
insert_alt: 414758839
=== l2_rqsts.pf_hit ===
insert_ok : 14639778
insert_alt: 19484420
=== l2_rqsts.pf_miss ===
insert_ok : 156092998
insert_alt: 263293430
=== l2_rqsts.references ===
insert_ok : 326549998
insert_alt: 443460029
=== l2_rqsts.rfo_hit ===
insert_ok : 11650
insert_alt: 21474
=== l2_rqsts.rfo_miss ===
insert_ok : 17544467
insert_alt: 16835137
=== l2_trans.l2_wb ===
insert_ok : 157044674
insert_alt: 308107712
=== ld_blocks.no_sr ===
insert_ok : 14
insert_alt: 13
=== ld_blocks.store_forward ===
insert_ok : 158
insert_alt: 128
=== ld_blocks_partial.address_alias ===
insert_ok : 5155853
insert_alt: 17867414
=== load_hit_pre.sw_pf ===
insert_ok : 10840795
insert_alt: 11072297
=== longest_lat_cache.miss ===
insert_ok : 257061118
insert_alt: 471152073
=== longest_lat_cache.reference ===
insert_ok : 445701577
insert_alt: 583870610
=== machine_clears.count ===
insert_ok : 3926377
insert_alt: 4280080
=== machine_clears.memory_ordering ===
insert_ok : 97177
insert_alt: 25407
=== machine_clears.smc ===
insert_ok : 138579
insert_alt: 305423
=== mem-stores ===
insert_ok : 621353009
insert_alt: 554244143
=== mem_inst_retired.all_loads ===
insert_ok : 775473590
insert_alt: 1038559807
=== mem_inst_retired.all_stores ===
insert_ok : 621353013
insert_alt: 554244145
=== mem_inst_retired.lock_loads ===
insert_ok : 85
insert_alt: 85
=== mem_inst_retired.split_loads ===
insert_ok : 171
insert_alt: 174
=== mem_inst_retired.split_stores ===
insert_ok : 53
insert_alt: 49
=== mem_inst_retired.stlb_miss_loads ===
insert_ok : 68308539
insert_alt: 18088047
=== mem_inst_retired.stlb_miss_stores ===
insert_ok : 264054
insert_alt: 819551
=== mem_load_l3_hit_retired.xsnp_none ===
insert_ok : 231116
insert_alt: 175217
=== mem_load_retired.fb_hit ===
insert_ok : 6510722
insert_alt: 95952490
=== mem_load_retired.l1_hit ===
insert_ok : 698271530
insert_alt: 920982402
=== mem_load_retired.l1_miss ===
insert_ok : 69525335
insert_alt: 20089897
=== mem_load_retired.l2_hit ===
insert_ok : 1451905
insert_alt: 773356
=== mem_load_retired.l2_miss ===
insert_ok : 68085186
insert_alt: 19474303
=== mem_load_retired.l3_hit ===
insert_ok : 222829
insert_alt: 155958
=== mem_load_retired.l3_miss ===
insert_ok : 67879593
insert_alt: 19244746
=== memory_disambiguation.history_reset ===
insert_ok : 97621
insert_alt: 25831
=== minor-faults ===
insert_ok : 1048716
insert_alt: 1048718
=== node-loads ===
insert_ok : 71473780
insert_alt: 71377840
=== node-stores ===
insert_ok : 16781161
insert_alt: 16842666
=== offcore_requests.all_data_rd ===
insert_ok : 284186682
insert_alt: 392110677
=== offcore_requests.all_requests ===
insert_ok : 530876505
insert_alt: 777784382
=== offcore_requests.demand_code_rd ===
insert_ok : 34252
insert_alt: 45896
=== offcore_requests.demand_data_rd ===
insert_ok : 133468710
insert_alt: 134288893
=== offcore_requests.demand_rfo ===
insert_ok : 17612516
insert_alt: 17062276
=== offcore_requests.l3_miss_demand_data_rd ===
insert_ok : 71616594
insert_alt: 82917520
=== offcore_requests_buffer.sq_full ===
insert_ok : 2001445
insert_alt: 3113287
=== offcore_requests_outstanding.all_data_rd ===
insert_ok : 35577129549
insert_alt: 78698308135
=== offcore_requests_outstanding.cycles_with_data_rd ===
insert_ok : 17518017620
insert_alt: 7940272202
=== offcore_requests_outstanding.demand_code_rd ===
insert_ok : 11085819
insert_alt: 9390881
=== offcore_requests_outstanding.demand_data_rd ===
insert_ok : 15902243707
insert_alt: 21097348926
=== offcore_requests_outstanding.demand_data_rd_ge_6 ===
insert_ok : 1225437
insert_alt: 317436422
=== offcore_requests_outstanding.demand_rfo ===
insert_ok : 1074492442
insert_alt: 1157902315
=== offcore_response.demand_code_rd.any_response ===
insert_ok : 53675
insert_alt: 69683
=== offcore_
Bee*_*ope 89
\n
概括
\nTLDR 是指未命中 TLB 的所有级别（因此需要页面遍历）并且由地址未知存储分隔的加载无法并行执行，即加载是串行化的，并且内存级并行性(MLP)系数的上限为 1。实际上，商店隔离了负载，就像lfence本来的那样。
插入函数的慢速版本会导致这种情况，而其他两个则不会（存储地址已知）。对于大区域大小，内存访问模式占主导地位，并且性能几乎与 MLP 直接相关：快速版本可以重叠加载缺失并获得大约 3 的 MLP，从而实现 3 倍的加速（以及我们下面讨论的更窄的再现情况）在 Skylake 上可以显示出超过10 倍的差异）。
\n根本原因似乎是 Skylake 处理器试图保持页表一致性，这不是规范所要求的，但可以解决软件中的错误。
\n细节
\n对于那些感兴趣的人，我们将深入了解正在发生的事情的细节。
\n我可以立即在我的 Skylake i7-6700HQ 机器上重现该问题，并且通过去除无关部分，我们可以将原始哈希插入基准减少到这个简单的循环，该循环表现出相同的问题：
\ntlb_fencing:\n\n xor eax, eax ; the index pointer\n mov r9 , [rsi + region.start]\n\n mov r8 , [rsi + region.size] \n sub r8 , 200 ; pointer to end of region (plus a bit of buffer)\n\n mov r10, [rsi + region.size]\n sub r10, 1 ; mask\n\n mov rsi, r9 ; region start\n\n.top:\n mov rcx, rax\n and rcx, r10 ; remap the index into the region via masking\n add rcx, r9 ; make pointer p into the region\n mov rdx, [rcx] ; load 8 bytes at p, always zero\n xor rcx, rcx ; no-op\n mov DWORD [rsi + rdx + 160], 0 ; store zero at p + 160 \n add rax, (64 * 67) ; advance a prime number of cache lines slightly larger than a page\n\n dec rdi\n jnz .top\n\n ret\n这大致相当于4B.size最内层循环的访问（加载）和B.values[B.size] = 1访问（存储）。insert_ok
专注于循环，我们进行跨步加载和固定存储。然后将加载位置向前移动一点，超出页面大小 (4 KiB)。至关重要的是，存储地址取决于加载的结果：因为寻址表达式[rsi + rdx + 160]包括保存加载值1rdx的寄存器。存储始终发生在同一地址，因为循环中没有任何地址组件发生变化（因此我们期望 L1 缓存始终命中）。
原始的哈希示例做了更多的工作，随机访问内存，并将存储存储到与加载相同的行，但这个简单的循环捕获了相同的效果。
\nxor rcx, rcx我们还使用基准测试的另一个版本，它是相同的，只是加载和存储之间的无操作被替换为xor rdx, rdx。这打破了加载和存储地址之间的依赖性。
天真地，我们并不期望这种依赖有多大作用。这里的存储是即发即忘的：我们不会再次从存储的位置读取（至少不会多次迭代），因此它们不是任何携带的依赖链的一部分。对于小区域，我们预计瓶颈只是消耗约 8 个微指令，而对于大区域，我们预计处理所有缓存未命中的时间将占主导地位：关键的是，我们预计许多未命中将被并行处理，因为加载地址可以是从简单的非内存微指令独立计算。
\n下面是区域大小从 4 KiB 到 256 MiB 的周期性能，具有以下三种变化：
\n2M dep：上面显示的循环（存储地址取决于加载），具有2 MiB 大页面。
\n4K dep：上面显示的循环（存储地址取决于加载），具有标准 4 KiB 页。
\n4K indep：上述循环的变体，使用 but withxor rdx, rdx替换xor rcx, rcx来打破加载结果和存储地址之间的依赖关系，使用 4 KiB 页。
结果：
\n
对于小区域大小，所有变体的性能基本相同。高达 256 KiB 的所有内容都需要 2 个周期/迭代，仅受循环中的 8 uops 和4 uops/周期的 CPU 宽度限制。一点数学表明我们有不错的 MLP（内存级并行性）：L2 缓存命中有 12 个周期的延迟，但我们每 2 个周期完成一次，因此平均而言，我们必须重叠 6 个 L1 未命中的延迟实现这一目标。
\n在 256 KiB 和 4096 KiB 之间，随着 L3 命中开始发生，性能会有所下降，但性能良好且 MLP 高。
\n仅在4K dep情况下，在 8196 KiB 时，性能会发生灾难性下降，跨越 150 个周期，最终稳定在约 220 个周期。它比其他两种情况2慢10 倍以上。
\n我们已经可以做出一些关键的观察：
\n- \n
- 2M dep和4K indep情况都很快：因此这不仅与存储之间的依赖关系有关，还与分页行为有关。 \n
- 2M dep 的情况是最快的，因此我们知道即使您错过了内存，依赖性也不会导致一些基本问题。 \n
- 缓慢的4K dep情况的性能与我机器的内存延迟非常相似。 \n
我在上面提到了 MLP，并根据观察到的性能计算了 MLP 的下限，但在 Intel CPU 上，我们可以使用两个性能计数器直接测量 MLP：
\n\n\n\n
l1d_pend_miss.pending计算未完成 L1D 未命中的持续时间，即需求读取所需的未完成填充缓冲区 (FB) 的每个周期数。
\n
\n\n\n
l1d_pend_miss.pending_cyclesL1D 负载循环未完成
\n
第一个计算每个周期有多少个来自 L1D 的未完成请求。因此，如果发生 3 次未命中，则该计数器每个周期都会增加 3。当至少有一次未命中时，第二个计数器在每个周期增加 1。您可以将其视为第一个计数器的一个版本，每个周期都会饱和到 1。l1d_pend_miss.pending / l1d_pend_miss.pending_cycles这些计数器在一段时间内的比率是平均 MLP 因子，而任何未命中的情况都是突出的3。
让我们绘制4K 基准测试的dep和indep版本的 MLP 比率：
\n
问题就变得非常清楚了。直到 4096 KiB 的区域，性能都是相同的，并且 MLP 很高（对于非常小的区域大小，“没有”MLP，因为根本不存在 L1D 缺失）。突然在 8192 KiB 时，从属情况的 MLP 下降到 1 并保持在那里，而在独立情况下，MLP 几乎达到 10。仅此一点就基本上解释了 10 倍的性能差异：从属情况无法重叠负载，在全部。
\n为什么？问题似乎是 TLB 未命中。在 8192 KiB 处发生的情况是基准测试开始缺少 TLB。具体来说，每个 Skylake 核心有 1536 个 STLB（二级 TLB）条目，可以覆盖 1536 \xc3\x97 4096 = 6 MiB 的 4K 页。因此，在 4 到 8 MiB 区域大小之间，基于 的每次迭代，TLB 丢失次数达到 1 dtlb_load_misses.walk_completed，从而导致了这个几乎太完美的“是假的”图：
这就是发生的情况：当地址未知的存储位于存储缓冲区中时，发生 STLB 未命中的加载不能重叠：它们一次一个。因此，每次访问都会遭受完整的内存延迟。这也解释了为什么 2MB 页面情况很快：2 MB 页面可以覆盖 3 GiB 内存，因此这些区域大小没有 STLB 未命中/页面遍历。
\n为什么
\n这种行为似乎源于 Skylake 和其他早期 Intel 处理器实现页表一致性的事实，尽管 x86 平台并不需要它。页表一致性意味着，如果存储修改了地址映射（例如），则使用受重新映射影响的虚拟地址的后续加载将一致地看到新映射，而无需任何显式刷新。
\n这一见解来自 Henry Wong，他在关于页面行走一致性的优秀文章中报告说，要做到这一点，如果在行走过程中遇到冲突或地址未知的商店，页面行走就会终止：
\n\n\n出乎意料的是，即使没有页表修改，Intel Core 2 和更新的系统也会表现得好像发生了页行走一致性错误推测。这些系统具有内存依赖性预测，因此加载应该比存储更早地推测执行，并打破数据依赖性链。
\n事实证明，正是早期执行的负载导致了错误检测的错误推测。这给出了如何检测一致性违规的提示：通过将寻呼与已知的旧存储地址（在存储队列中？）进行比较，并在存在冲突或未知地址的旧存储时假设一致性违规。
\n
因此，即使这些存储完全无辜，因为它们不修改任何页表，它们也会陷入页表一致性机制中。通过观察这个事件，我们可以找到这一理论的进一步证据dtlb_load_misses.miss_causes_a_walk。与事件不同的是，这会计算所有开始的walk_completed步行，即使它们没有成功完成。这个看起来像这样（同样，2M 没有显示，因为它根本不启动页面遍历）：
哈！4K 依赖项显示了两次已开始的步行，其中只有一次成功完成。每个负载需要步行两次。这与页面遍历在迭代 N+1 中开始加载的理论一致，但它发现迭代 N 中的存储仍然位于存储缓冲区中（因为迭代 N 的加载提供了其地址，并且仍在进行中） ）。由于地址未知，因此页面遍历被取消，正如亨利所描述的那样。进一步的页面遍历将被延迟，直到商店地址被解析。结果是所有加载都以序列化方式完成，因为加载 N+1 的页面遍历必须等待加载 N 的结果。
\n为什么“坏”和“替代”方法很快
\n最后，还有一个未解之谜。上面解释了为什么原始哈希访问慢，但没有解释为什么其他两个访问快。关键是这两种快速方法都没有地址未知的存储，因为与负载的数据依赖性被推测性控制依赖性所取代。
\n看一下该insert_bad方法的内部循环：
for (size_t i = 0; i < bucket_size; ++i)\n{\n if (i == B.size)\n {\n B.keys[i] = k;\n B.values[i] = 1;\n ++B.size;\n ++table_count;\n return;\n }\n}\n请注意，存储使用循环索引i。insert_ok与索引[B.size]来自存储的情况不同，i索引只是寄存器中的计算值。Now与加载的值i相关，因为它的最终值将等于它，但这是通过比较确定的，这是推测的控制依赖性。它不会导致页面行走取消出现任何问题。这种情况确实有很多错误预测（因为循环退出是不可预测的），但对于大区域的情况，这些实际上并没有太大的危害，因为坏路径通常会进行与好路径相同的内存访问（具体来说，插入的下一个值始终相同）并且内存访问行为占主导地位。B.size
对于这种情况也是如此alt：通过使用计算值加载值来建立要写入的索引i，检查它是否是特殊标记值，然后使用索引写入该位置i。同样，没有延迟的存储地址，只有快速计算的寄存器值和推测的控制依赖性。
其他硬件怎么样
\n与问题作者一样，我发现了 Skylake 上的效果，但我也在 Haswell 上观察到了相同的行为。在 Ice Lake 上，我无法重现它：dep和indep具有几乎相同的性能。
\n然而，用户 Noah报告说，他可以使用某些对齐的原始基准在 Tigerlake 上进行复制。我认为最可能的原因是 TGL 不受此页面行走行为的影响，而是在某些对齐中内存消歧预测器发生冲突，导致非常相似的效果：加载无法在早期地址未知存储之前执行因为处理器认为存储可能会转发给负载。
\n自己运行
\n您可以自己运行我上面描述的基准测试。它是uarch-bench的一部分。在 Linux（或 WSL，但性能计数器不可用）上，您可以运行以下命令来收集结果：
\nfor s in 2M-dep 4K-dep 4K-indep; do ./uarch-bench --timer=perf --test-name="studies/memory/tlb-fencing/*$s" --extra-events=dtlb_load_misses.miss_causes_a_walk#walk_s,dtlb_load_misses.walk_completed#walk_c,l1d_pend_miss.pending#l1d_p,l1d_pend_miss.pending_cycles#l1d_pc; done\n某些系统可能没有足够的可用性能计数器（如果您启用了超线程），因此您可以每次使用不同的计数器集进行两次运行。
\n\n
1在这种情况下，rdx始终为零（该区域完全充满零），因此存储地址恰好相同，就好像该寄存器未包含在寻址表达式中一样，但 CPU 不知道这一点！
2在此，2M dep情况也开始显示出比4K indep情况更好的性能，尽管差距不大。
\n3请注意“当任何未命中”部分：您还可以将 MLP 计算为l1d_pend_miss.pending / cycles，这将是一段时间内的平均 MLP，无论是否有任何未命中。每个都以自己的方式有用，但在这种情况下，如果失误不断突出，它们会给出几乎相同的值。
4是的，这个例子和原来的例子有很多不同。我们存储到单个固定位置，而原始循环存储在加载位置附近，每次迭代都会变化。我们存储 0 而不是 1。我们不检查B.size它是否太大。在我们的测试中，加载的值始终为 0。当桶已满时，没有搜索循环。我们不加载随机值来寻址，而只是进行线性步幅。然而，这些并不重要：在两种情况下都会出现相同的效果，您可以通过消除复杂性来逐步修改原始示例，直到达到这个简单的情况。
- 因此该机制无法判断存储是否实际上是页表，因为存储的地址未知。因此，保守一点，它会取消页面遍历。 (2认同)