为什么我的 Intel Skylake / Kaby Lake CPU 在简单的哈希 table 实现中会导致神秘的 3 倍减速？
Why does my Intel Skylake / Kaby Lake CPU incur a mysterious factor 3 slowdown in a simple hash table implementation?
简而言之：
我已经实现了一个简单的（多键）散列 table，它带有完全适合缓存行的存储桶（包含多个元素）。
插入cacheline bucket很简单，也是主循环的关键部分。
我已经实现了三个版本，它们产生相同的结果并且应该表现相同。
谜底
但是，尽管所有版本都具有完全相同的高速缓存行访问模式并导致相同的哈希 table 数据，但我发现性能差异惊人地大了 3。
与我的 CPU (i7-7700HQ) 上的 insert_bad 和 insert_alt 相比，最佳实施 insert_ok 的速度降低了大约 3 倍。
一个变体 insert_bad 是对 insert_ok 的简单修改，它在缓存行内添加了一个额外的不必要的线性搜索以找到要写入的位置（它已经知道）并且不会遭受 x3 的减速。
完全相同的 executable 显示 insert_ok 与其他 CPU 上的 insert_bad 和 insert_alt 相比快了 1.6 倍（AMD 5950X（Zen 3), Intel i7-11800H (Tiger Lake)).
# 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 倍的减速是自动预取或分支预测或 instruction/jump 对齐或它们的组合的奇怪效果。
是否有人有更好的见解或方法来衡量实际可能发挥的作用？
详情
我已经创建了一个小型工作 C++11 示例来演示该问题。
该代码可在 https://github.com/cr-marcstevens/hashtable_mystery
这还包括我自己的静态二进制文件，它们在我的 CPU 上演示了这个问题，因为不同的编译器可能会生成不同的代码。
以及所有三个散列 table 版本的转储汇编代码。
性能事件测量
这里有很多性能事件测量。我重点关注那些包含单词 miss 和 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_response.demand_code_rd.l3_hit.any_snoop ===
insert_ok : 19407
insert_alt: 29704
=== offcore_response.demand_code_rd.l3_hit.snoop_none ===
insert_ok : 12675
insert_alt: 11951
=== offcore_response.demand_code_rd.l3_miss.any_snoop ===
insert_ok : 34617
insert_alt: 40868
=== offcore_response.demand_code_rd.l3_miss.spl_hit ===
insert_ok : 0
insert_alt: 753
=== offcore_response.demand_data_rd.any_response ===
insert_ok : 131014821
insert_alt: 134813171
=== offcore_response.demand_data_rd.l3_hit.any_snoop ===
insert_ok : 59713328
insert_alt: 50254543
=== offcore_response.demand_data_rd.l3_miss.any_snoop ===
insert_ok : 71431585
insert_alt: 83916030
=== offcore_response.demand_data_rd.l3_miss.spl_hit ===
insert_ok : 244837
insert_alt: 6441992
=== offcore_response.demand_rfo.any_response ===
insert_ok : 16876557
insert_alt: 17619450
=== offcore_response.demand_rfo.l3_hit.any_snoop ===
insert_ok : 907432
insert_alt: 45127
=== offcore_response.demand_rfo.l3_hit.snoop_none ===
insert_ok : 787567
insert_alt: 794579
=== offcore_response.demand_rfo.l3_hit_e.any_snoop ===
insert_ok : 496938
insert_alt: 173658
=== offcore_response.demand_rfo.l3_hit_e.snoop_none ===
insert_ok : 779919
insert_alt: 50575
=== offcore_response.demand_rfo.l3_hit_m.any_snoop ===
insert_ok : 128627
insert_alt: 25483
=== offcore_response.demand_rfo.l3_miss.any_snoop ===
insert_ok : 16782186
insert_alt: 16847970
=== offcore_response.demand_rfo.l3_miss.snoop_none ===
insert_ok : 16782647
insert_alt: 16850104
=== offcore_response.demand_rfo.l3_miss.spl_hit ===
insert_ok : 0
insert_alt: 1364
=== offcore_response.other.any_response ===
insert_ok : 137231000
insert_alt: 189526494
=== offcore_response.other.l3_hit.any_snoop ===
insert_ok : 62695084
insert_alt: 51005882
=== offcore_response.other.l3_hit.snoop_none ===
insert_ok : 62975018
insert_alt: 50217349
=== offcore_response.other.l3_hit_e.any_snoop ===
insert_ok : 62770215
insert_alt: 50691817
=== offcore_response.other.l3_hit_e.snoop_none ===
insert_ok : 62602591
insert_alt: 50642954
=== offcore_response.other.l3_miss.any_snoop ===
insert_ok : 74247236
insert_alt: 139212975
=== offcore_response.other.l3_miss.snoop_none ===
insert_ok : 75911794
insert_alt: 141076520
=== other_assists.any ===
insert_ok : 1
insert_alt: 3
=== page-faults ===
insert_ok : 1048719
insert_alt: 1048718
=== partial_rat_stalls.scoreboard ===
insert_ok : 530950991
insert_alt: 539869553
=== ref-cycles ===
insert_ok : 32546980212
insert_alt: 12930921138
=== resource_stalls.any ===
insert_ok : 21923576648
insert_alt: 5205690082
=== resource_stalls.sb ===
insert_ok : 397908667
insert_alt: 402738367
=== rs_events.empty_cycles ===
insert_ok : 1173721723
insert_alt: 1880165720
=== rs_events.empty_end ===
insert_ok : 87752182
insert_alt: 160792701
=== sw_prefetch_access.t0 ===
insert_ok : 20835202
insert_alt: 20599176
=== task-clock ===
insert_ok : 10416.86 msec task-clock:u # 1.000 CPUs utilized
insert_alt: 4767.78 msec task-clock:u # 1.000 CPUs utilized
=== tlb_flush.stlb_any ===
insert_ok : 1835393
insert_alt: 1835396
=== topdown-fetch-bubbles ===
insert_ok : 1904143421
insert_alt: 6543146396
=== topdown-slots-issued ===
insert_ok : 7538371393
insert_alt: 14449966516
=== topdown-slots-retired ===
insert_ok : 5267325162
insert_alt: 5849706597
=== uops_dispatched_port.port_0 ===
insert_ok : 1252121297
insert_alt: 1489605354
=== uops_dispatched_port.port_1 ===
insert_ok : 1379316967
insert_alt: 1585037107
=== uops_dispatched_port.port_2 ===
insert_ok : 1140861153
insert_alt: 1785053149
=== uops_dispatched_port.port_3 ===
insert_ok : 1187151423
insert_alt: 1828975838
=== uops_dispatched_port.port_4 ===
insert_ok : 1577171758
insert_alt: 1557761857
=== uops_dispatched_port.port_5 ===
insert_ok : 1341370655
insert_alt: 1653599117
=== uops_dispatched_port.port_6 ===
insert_ok : 1856735970
insert_alt: 4387464794
=== uops_dispatched_port.port_7 ===
insert_ok : 508351498
insert_alt: 603583315
=== uops_executed.core ===
insert_ok : 7225522677
insert_alt: 12716368190
=== uops_executed.core_cycles_ge_1 ===
insert_ok : 3041586797
insert_alt: 5168421550
=== uops_executed.core_cycles_ge_2 ===
insert_ok : 2017794537
insert_alt: 3653591208
=== uops_executed.core_cycles_ge_3 ===
insert_ok : 1225785335
insert_alt: 2316014066
=== uops_executed.core_cycles_ge_4 ===
insert_ok : 657121809
insert_alt: 1143390519
=== uops_executed.core_cycles_none ===
insert_ok : 22191507320
insert_alt: 6563722081
=== uops_executed.cycles_ge_1_uop_exec ===
insert_ok : 3040999757
insert_alt: 5175668459
=== uops_executed.cycles_ge_2_uops_exec ===
insert_ok : 2015520940
insert_alt: 3659989196
=== uops_executed.cycles_ge_3_uops_exec ===
insert_ok : 1224025952
insert_alt: 2319025110
=== uops_executed.cycles_ge_4_uops_exec ===
insert_ok : 657094113
insert_alt: 1141381027
=== uops_executed.stall_cycles ===
insert_ok : 22350754164
insert_alt: 6590978048
=== uops_executed.thread ===
insert_ok : 7214521925
insert_alt: 12697219901
=== uops_executed.x87 ===
insert_ok : 2992
insert_alt: 3337
=== uops_issued.any ===
insert_ok : 7531354736
insert_alt: 14462113169
=== uops_issued.slow_lea ===
insert_ok : 2136241
insert_alt: 2115308
=== uops_issued.stall_cycles ===
insert_ok : 23244177475
insert_alt: 7416801878
=== uops_retired.macro_fused ===
insert_ok : 410461916
insert_alt: 735050350
=== uops_retired.retire_slots ===
insert_ok : 5265023980
insert_alt: 5855259326
=== uops_retired.stall_cycles ===
insert_ok : 23513958928
insert_alt: 9630258867
=== uops_retired.total_cycles ===
insert_ok : 25266688635
insert_alt: 11703285605
背景
我正在用 C++11 实施密码分析攻击，需要找到两个大列表（都是动态生成的）之间的许多冲突。
因此，攻击的关键部分仅包含两个关键循环：
- 首先用一个列表
填充散列table
- 然后将另一个列表与散列 table.
进行匹配
散列 table 操作因此对性能至关重要，3 倍的减速意味着攻击速度减慢 3 倍。
关于设计：
除了尽量减少内存使用，我还尝试让典型的散列 table 操作仅在单个高速缓存行上运行。正如我预期的那样，这将提高整体攻击性能，尤其是当 运行 攻击所有 CPU 个核心时。
总结
TLDR 是错过所有 TLB 级别（因此需要页面遍历）并且被 地址未知 存储分隔的负载无法并行执行，即，负载被序列化并且 内存级并行性 (MLP) 因子上限为 1。实际上，存储 fence 负载，就像lfence 会。
您的插入函数的慢速版本会导致这种情况，而其他两个则不会（存储地址已知）。对于大区域大小，内存访问模式占主导地位，性能几乎与 MLP 直接相关：快速版本可以重叠加载未命中并获得大约 3 的 MLP，导致 3 倍加速（以及我们在下面讨论的更窄的再现情况在 Skylake 上可以显示超过 10x 的差异）。
根本原因似乎是 Skylake 处理器试图保持 page-table 连贯性 ，这不是规范所要求的，但可以解决软件。
详情
对于那些感兴趣的人，我们将深入了解正在发生的事情的细节。
我可以立即在我的 Skylake i7-6700HQ 机器上重现该问题，并且通过剥离无关部分，我们可以将原始哈希插入基准测试减少到这个简单的循环，它表现出相同的问题：
tlb_fencing:
xor eax, eax ; the index pointer
mov r9 , [rsi + region.start]
mov r8 , [rsi + region.size]
sub r8 , 200 ; pointer to end of region (plus a bit of buffer)
mov r10, [rsi + region.size]
sub r10, 1 ; mask
mov rsi, r9 ; region start
.top:
mov rcx, rax
and rcx, r10 ; remap the index into the region via masking
add rcx, r9 ; make pointer p into the region
mov rdx, [rcx] ; load 8 bytes at p, always zero
xor rcx, rcx ; no-op
mov DWORD [rsi + rdx + 160], 0 ; store zero at p + 160
add rax, (64 * 67) ; advance a prime number of cache lines slightly larger than a page
dec rdi
jnz .top
ret
这大致相当于insert_ok4[最内层循环的B.size访问（加载）和B.values[B.size] = 1访问（存储） =206=].
专注于循环，我们做一个strided load和一个fixed store。然后将加载位置向前移动一点超过页面大小 (4 KiB)。至关重要的是，存储地址 取决于 加载的结果：因为寻址表达式 [rsi + rdx + 160] 包括 rdx 这是保存加载值的寄存器 1。存储总是发生在相同的地址，因为地址组件的 none 在循环中发生变化（所以我们期望 L1 缓存总是命中）。
原来的散列示例做了更多的工作，随机访问内存，并将存储与加载放在同一行，但这个简单的循环捕获了相同的效果。
我们还使用了另一个版本的基准测试，除了加载和存储之间的空操作 xor rcx, rcx 被 xor rdx, rdx 替换之外，它是相同的。这 打破了 加载和存储地址之间的依赖关系。
天真地，我们并不期望这种依赖性有多大作用。这里的存储是 fire-and-forget: 我们不会再次从存储的位置读取（至少不会多次迭代）所以它们不是任何携带的依赖链的一部分。对于小区域，我们预计瓶颈只是咀嚼 ~8 微指令，而对于大区域，我们预计处理所有缓存未命中的时间将占主导地位：关键是，我们预计许多未命中会被并行处理，因为加载地址可以是从简单的非内存 uops 独立计算。
在下面找到区域大小从 4 KiB 到 256 MiB 的循环性能，具有以下三种变化：
2M dep: 上面显示的循环（存储地址取决于负载）有 2 MiB 大页面.
4K dep: 上面显示的循环（存储地址取决于负载）具有标准的 4 KiB 页面。
4K indep: 上述循环的变体，但用 xor rdx, rdx 替换 xor rcx, rcx 以打破加载结果和存储地址之间的依赖关系，使用 4 KiB 页面。
结果：
对于小区域大小，所有变体的性能基本相同。所有高达 256 KiB 的东西都需要 2 cycles/iteration，仅受循环中的 8 微指令和 CPU width of 4 uops/cycle 限制。一些数学表明我们有不错的 MLP（内存级并行性）：L2 缓存命中有 12 个周期的延迟，但我们每 2 个周期完成一个，所以平均而言我们必须重叠 6 个 L1 未命中的延迟做到这一点。
在 256 KiB 和 4096 KiB 之间，随着 L3 命中开始发生，性能有所下降，但性能良好且 MLP 高。
在 8196 KiB 时，仅 4K dep 情况下，性能会发生灾难性下降，跨越 150 个周期并最终稳定在大约 220 个周期。比其他两种情况2.
慢10倍
我们已经可以做出一些关键观察：
- 2M dep 和 4K indep 情况都很快：所以这不是 just 关于商店之间的依赖关系，也关于分页行为。
- 2M dep 的情况是最快的，因此我们知道即使您忘记了记忆，依赖性也不会导致一些基本问题。
- 慢 4K dep 情况下的性能与我机器的内存延迟非常相似。
我在上面提到了 MLP，并根据观察到的性能计算了 MLP 的下限，但在英特尔 CPUs 上，我们可以使用两个性能计数器直接测量 MLP：
l1d_pend_miss.pending
Counts duration of L1D miss outstanding, that is each cycle number of Fill Buffers (FB) outstanding required by Demand Reads.
l1d_pend_miss.pending_cycles
Cycles with L1D load Misses outstanding
第一个计数，每个周期，有多少请求来自 L1D。因此，如果正在进行 3 次未命中，则此计数器每个周期递增 3。第二个计数器每个周期递增 1，至少有 one 未命中。您可以将其视为第一个计数器的一个版本，它在每个周期都饱和为 1。这些计数器在一段时间内的比率 l1d_pend_miss.pending / l1d_pend_miss.pending_cycles 是平均 MLP 因子，而任何未命中都是未完成的3.
让我们绘制 4K 基准测试的 dep 和 indep 版本的 MLP 比率：
问题就很清楚了。直到 4096 KiB 的区域，性能是相同的，并且 MLP 很高（对于非常小的区域大小，“没有”MLP，因为根本没有 L1D 未命中）。突然在 8192 KiB，从属案例的 MLP 下降到 1 并保持在那里，而在独立案例中，MLP 几乎达到 10。仅此一项就基本上解释了 10 倍的性能差异：从属案例无法重叠负载，在全部.
为什么？问题似乎是 TLB 未命中。在 8192 KiB 处发生的是基准测试开始缺少 TLB。具体来说，每个 Skylake 核心有 1536 个 STLB（二级 TLB）条目，可以覆盖 1536 × 4096 = 6 MiB 的 4K 页面。因此，在 4 和 8 MiB 区域大小之间，基于 dtlb_load_misses.walk_completed，TLB 未命中每次迭代变为 1，导致这个几乎太完美的假图：
这就是发生的事情：当地址未知的存储在存储缓冲区中时，发生 STLB 未命中的加载不能重叠：它们一次一个。因此，每次访问都会遭受完整的内存延迟。这也解释了为什么 2MB 页面的情况很快：2MB 页面可以覆盖 3GiB 内存，所以对于这些区域大小没有 STLB misses/page 遍历。
为什么
这种行为似乎源于这样一个事实，即 Skylake 和其他早期的 Intel 处理器实现了 page table 一致性， 即使 x86 平台不需要它。页面 table 一致性意味着如果修改地址映射的存储（例如）使用受重新映射影响的虚拟地址的后续加载将一致地看到新映射而无需任何显式刷新。
这一见解来自 Henry Wong，他在他的 excellent article on page walk coherence 中报告说，要做到这一点，如果遇到冲突或 地址未知的商店 ，页面遍历就会终止步行：
Unexpectedly, Intel Core 2 and newer systems behaved as though a pagewalk coherence misspeculation had occurred even though there were no page table modifications. These systems have memory dependence prediction, so the load should have speculatively executed much earlier than the store and broken the data dependence chain.
It turns out it is precisely the early-executing load that is responsible for the incorrectly-detected misspeculation. This gives a hint on how coherence violations may be detected: by comparing pagewalks to known older store addresses (in the store queue?), and assuming a coherence violation if there is an older store with a conflict or an unknown address.
因此，即使这些商店完全无辜，因为它们不修改任何页面 table，它们也会陷入页面 table 一致性机制中。通过查看事件 dtlb_load_misses.miss_causes_a_walk，我们可以找到该理论的进一步证据。与 walk_completed 事件不同，这会计算所有 开始 的行走，即使它们没有成功完成。那个看起来像这样（同样，没有显示 2M，因为它根本没有开始浏览页面）：
咦！ 4K 依赖项显示两次 开始步行，其中只有一次成功完成。每次负重都要走两次。这与页面遍历在迭代 N+1 中开始加载的理论一致，但它发现迭代 N 中的存储仍然位于存储缓冲区中（因为迭代 N 的加载提供了它的地址，并且它仍在进行中).由于地址未知，因此如 Henry 所述，页面遍历被取消。进一步的页面遍历被延迟，直到商店地址被解析。结果是以序列化的方式完成所有加载，因为加载 N+1 的页面遍历必须等待加载 N 的结果。
为什么“bad”和“alt”方法很快
最后，还有一个未解之谜。上面解释了为什么原来的哈希访问速度很慢，但没有解释为什么其他两个很快。关键是这两种快速方法都没有地址未知的存储，因为与负载的数据依赖被推测控制依赖所取代。
看一下 insert_bad 方法的内部循环：
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;
}
}
请注意，商店使用循环索引 i。与索引 [B.size] 来自存储的 insert_ok 情况不同，i 只是寄存器中的一个计算值。现在 i 与加载值 B.size 相关 因为它的最终值将 等于 ，但这是通过比较建立，这是一个推测的控制依赖。它不会导致页面遍历取消的任何问题。这种情况确实有很多错误预测（因为循环出口是不可预测的 table），但对于大区域情况，这些实际上并没有太大危害，因为坏路径通常与好路径进行相同的内存访问（具体来说，下一个插入的值总是相同的）并且内存访问行为占主导地位。
alt情况也是如此：写入的索引是通过计算值建立的 i加载一个值，检查是否是特殊标记值，然后使用索引 i 在该位置写入。同样，没有延迟存储地址，只有快速计算的寄存器值和推测的控制依赖性。
其他硬件呢
和问题作者一样，我在Skylake上发现了效果，但我在Haswell上也观察到了同样的行为。在 Ice Lake 上，我无法重现它：dep 和 indep 的性能几乎相同。
但是，用户 Noah 对某些比对使用原始基准。我认为最可能的原因是 TGL 不受此页面遍历行为的影响，而是在某些对齐方式下，内存消歧预测器发生冲突，导致非常相似的效果：加载无法在较早的地址未知存储之前执行，因为处理器认为存储可能会转发给负载。
运行自己做
你可以运行我上面描述的基准你自己。它是 uarch-bench 的一部分。在 Linux（或 WSL，但性能计数器不可用）上，您可以 运行 以下命令来收集结果：
for 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
某些系统可能没有足够的可用性能计数器（如果您启用了超线程），因此您可以每次使用不同的计数器集执行两次 运行。
1 在这种情况下，rdx 始终为零（该区域完全为零）因此存储地址恰好与此寄存器相同未包含在寻址表达式中，但 CPU 不知道！
2 此处，2M dep 案例也开始显示出比 4K indep[=211] 更好的性能=] 案例，尽管差距不大。
3 请注意“虽然任何未命中都是突出的”部分：您还可以将 MLP 计算为 l1d_pend_miss.pending / cycles，这将是一段时间内的平均 MLP ，无论是否有任何未命中。每个都有自己的用处，但在这种情况下，未命中的情况总是很突出，它们给出的值几乎相同。
4 是的，这个和原来的例子有很多不同。我们存储到一个固定位置，而原始循环存储在加载位置附近，每次迭代都会发生变化。我们存储 0 而不是 1。我们不检查 B.size 看它是否太大。在我们的测试中，加载值始终为 0。当桶已满时没有搜索循环。我们不加载一个随机值来寻址，而只是做一个线性步幅。但是，这些不是 material：在两种情况下都会出现相同的效果，您可以通过消除复杂性来逐步修改原始示例，直到达到这个简单的情况。
简而言之：
我已经实现了一个简单的（多键）散列 table，它带有完全适合缓存行的存储桶（包含多个元素）。 插入cacheline bucket很简单，也是主循环的关键部分。
我已经实现了三个版本，它们产生相同的结果并且应该表现相同。
谜底
但是，尽管所有版本都具有完全相同的高速缓存行访问模式并导致相同的哈希 table 数据，但我发现性能差异惊人地大了 3。
与我的 CPU (i7-7700HQ) 上的 insert_bad 和 insert_alt 相比，最佳实施 insert_ok 的速度降低了大约 3 倍。
一个变体 insert_bad 是对 insert_ok 的简单修改，它在缓存行内添加了一个额外的不必要的线性搜索以找到要写入的位置（它已经知道）并且不会遭受 x3 的减速。
完全相同的 executable 显示 insert_ok 与其他 CPU 上的 insert_bad 和 insert_alt 相比快了 1.6 倍（AMD 5950X（Zen 3), Intel i7-11800H (Tiger Lake)).
# 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 倍的减速是自动预取或分支预测或 instruction/jump 对齐或它们的组合的奇怪效果。
是否有人有更好的见解或方法来衡量实际可能发挥的作用？
详情
我已经创建了一个小型工作 C++11 示例来演示该问题。 该代码可在 https://github.com/cr-marcstevens/hashtable_mystery
这还包括我自己的静态二进制文件，它们在我的 CPU 上演示了这个问题，因为不同的编译器可能会生成不同的代码。 以及所有三个散列 table 版本的转储汇编代码。
性能事件测量
这里有很多性能事件测量。我重点关注那些包含单词 miss 和 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_response.demand_code_rd.l3_hit.any_snoop ===
insert_ok : 19407
insert_alt: 29704
=== offcore_response.demand_code_rd.l3_hit.snoop_none ===
insert_ok : 12675
insert_alt: 11951
=== offcore_response.demand_code_rd.l3_miss.any_snoop ===
insert_ok : 34617
insert_alt: 40868
=== offcore_response.demand_code_rd.l3_miss.spl_hit ===
insert_ok : 0
insert_alt: 753
=== offcore_response.demand_data_rd.any_response ===
insert_ok : 131014821
insert_alt: 134813171
=== offcore_response.demand_data_rd.l3_hit.any_snoop ===
insert_ok : 59713328
insert_alt: 50254543
=== offcore_response.demand_data_rd.l3_miss.any_snoop ===
insert_ok : 71431585
insert_alt: 83916030
=== offcore_response.demand_data_rd.l3_miss.spl_hit ===
insert_ok : 244837
insert_alt: 6441992
=== offcore_response.demand_rfo.any_response ===
insert_ok : 16876557
insert_alt: 17619450
=== offcore_response.demand_rfo.l3_hit.any_snoop ===
insert_ok : 907432
insert_alt: 45127
=== offcore_response.demand_rfo.l3_hit.snoop_none ===
insert_ok : 787567
insert_alt: 794579
=== offcore_response.demand_rfo.l3_hit_e.any_snoop ===
insert_ok : 496938
insert_alt: 173658
=== offcore_response.demand_rfo.l3_hit_e.snoop_none ===
insert_ok : 779919
insert_alt: 50575
=== offcore_response.demand_rfo.l3_hit_m.any_snoop ===
insert_ok : 128627
insert_alt: 25483
=== offcore_response.demand_rfo.l3_miss.any_snoop ===
insert_ok : 16782186
insert_alt: 16847970
=== offcore_response.demand_rfo.l3_miss.snoop_none ===
insert_ok : 16782647
insert_alt: 16850104
=== offcore_response.demand_rfo.l3_miss.spl_hit ===
insert_ok : 0
insert_alt: 1364
=== offcore_response.other.any_response ===
insert_ok : 137231000
insert_alt: 189526494
=== offcore_response.other.l3_hit.any_snoop ===
insert_ok : 62695084
insert_alt: 51005882
=== offcore_response.other.l3_hit.snoop_none ===
insert_ok : 62975018
insert_alt: 50217349
=== offcore_response.other.l3_hit_e.any_snoop ===
insert_ok : 62770215
insert_alt: 50691817
=== offcore_response.other.l3_hit_e.snoop_none ===
insert_ok : 62602591
insert_alt: 50642954
=== offcore_response.other.l3_miss.any_snoop ===
insert_ok : 74247236
insert_alt: 139212975
=== offcore_response.other.l3_miss.snoop_none ===
insert_ok : 75911794
insert_alt: 141076520
=== other_assists.any ===
insert_ok : 1
insert_alt: 3
=== page-faults ===
insert_ok : 1048719
insert_alt: 1048718
=== partial_rat_stalls.scoreboard ===
insert_ok : 530950991
insert_alt: 539869553
=== ref-cycles ===
insert_ok : 32546980212
insert_alt: 12930921138
=== resource_stalls.any ===
insert_ok : 21923576648
insert_alt: 5205690082
=== resource_stalls.sb ===
insert_ok : 397908667
insert_alt: 402738367
=== rs_events.empty_cycles ===
insert_ok : 1173721723
insert_alt: 1880165720
=== rs_events.empty_end ===
insert_ok : 87752182
insert_alt: 160792701
=== sw_prefetch_access.t0 ===
insert_ok : 20835202
insert_alt: 20599176
=== task-clock ===
insert_ok : 10416.86 msec task-clock:u # 1.000 CPUs utilized
insert_alt: 4767.78 msec task-clock:u # 1.000 CPUs utilized
=== tlb_flush.stlb_any ===
insert_ok : 1835393
insert_alt: 1835396
=== topdown-fetch-bubbles ===
insert_ok : 1904143421
insert_alt: 6543146396
=== topdown-slots-issued ===
insert_ok : 7538371393
insert_alt: 14449966516
=== topdown-slots-retired ===
insert_ok : 5267325162
insert_alt: 5849706597
=== uops_dispatched_port.port_0 ===
insert_ok : 1252121297
insert_alt: 1489605354
=== uops_dispatched_port.port_1 ===
insert_ok : 1379316967
insert_alt: 1585037107
=== uops_dispatched_port.port_2 ===
insert_ok : 1140861153
insert_alt: 1785053149
=== uops_dispatched_port.port_3 ===
insert_ok : 1187151423
insert_alt: 1828975838
=== uops_dispatched_port.port_4 ===
insert_ok : 1577171758
insert_alt: 1557761857
=== uops_dispatched_port.port_5 ===
insert_ok : 1341370655
insert_alt: 1653599117
=== uops_dispatched_port.port_6 ===
insert_ok : 1856735970
insert_alt: 4387464794
=== uops_dispatched_port.port_7 ===
insert_ok : 508351498
insert_alt: 603583315
=== uops_executed.core ===
insert_ok : 7225522677
insert_alt: 12716368190
=== uops_executed.core_cycles_ge_1 ===
insert_ok : 3041586797
insert_alt: 5168421550
=== uops_executed.core_cycles_ge_2 ===
insert_ok : 2017794537
insert_alt: 3653591208
=== uops_executed.core_cycles_ge_3 ===
insert_ok : 1225785335
insert_alt: 2316014066
=== uops_executed.core_cycles_ge_4 ===
insert_ok : 657121809
insert_alt: 1143390519
=== uops_executed.core_cycles_none ===
insert_ok : 22191507320
insert_alt: 6563722081
=== uops_executed.cycles_ge_1_uop_exec ===
insert_ok : 3040999757
insert_alt: 5175668459
=== uops_executed.cycles_ge_2_uops_exec ===
insert_ok : 2015520940
insert_alt: 3659989196
=== uops_executed.cycles_ge_3_uops_exec ===
insert_ok : 1224025952
insert_alt: 2319025110
=== uops_executed.cycles_ge_4_uops_exec ===
insert_ok : 657094113
insert_alt: 1141381027
=== uops_executed.stall_cycles ===
insert_ok : 22350754164
insert_alt: 6590978048
=== uops_executed.thread ===
insert_ok : 7214521925
insert_alt: 12697219901
=== uops_executed.x87 ===
insert_ok : 2992
insert_alt: 3337
=== uops_issued.any ===
insert_ok : 7531354736
insert_alt: 14462113169
=== uops_issued.slow_lea ===
insert_ok : 2136241
insert_alt: 2115308
=== uops_issued.stall_cycles ===
insert_ok : 23244177475
insert_alt: 7416801878
=== uops_retired.macro_fused ===
insert_ok : 410461916
insert_alt: 735050350
=== uops_retired.retire_slots ===
insert_ok : 5265023980
insert_alt: 5855259326
=== uops_retired.stall_cycles ===
insert_ok : 23513958928
insert_alt: 9630258867
=== uops_retired.total_cycles ===
insert_ok : 25266688635
insert_alt: 11703285605
背景
我正在用 C++11 实施密码分析攻击，需要找到两个大列表（都是动态生成的）之间的许多冲突。 因此，攻击的关键部分仅包含两个关键循环：
- 首先用一个列表 填充散列table
- 然后将另一个列表与散列 table. 进行匹配
散列 table 操作因此对性能至关重要，3 倍的减速意味着攻击速度减慢 3 倍。
关于设计： 除了尽量减少内存使用，我还尝试让典型的散列 table 操作仅在单个高速缓存行上运行。正如我预期的那样，这将提高整体攻击性能，尤其是当 运行 攻击所有 CPU 个核心时。
总结
TLDR 是错过所有 TLB 级别（因此需要页面遍历）并且被 地址未知 存储分隔的负载无法并行执行，即，负载被序列化并且 内存级并行性 (MLP) 因子上限为 1。实际上，存储 fence 负载，就像lfence 会。
您的插入函数的慢速版本会导致这种情况，而其他两个则不会（存储地址已知）。对于大区域大小，内存访问模式占主导地位，性能几乎与 MLP 直接相关：快速版本可以重叠加载未命中并获得大约 3 的 MLP，导致 3 倍加速（以及我们在下面讨论的更窄的再现情况在 Skylake 上可以显示超过 10x 的差异）。
根本原因似乎是 Skylake 处理器试图保持 page-table 连贯性 ，这不是规范所要求的，但可以解决软件。
详情
对于那些感兴趣的人，我们将深入了解正在发生的事情的细节。
我可以立即在我的 Skylake i7-6700HQ 机器上重现该问题，并且通过剥离无关部分，我们可以将原始哈希插入基准测试减少到这个简单的循环，它表现出相同的问题：
tlb_fencing:
xor eax, eax ; the index pointer
mov r9 , [rsi + region.start]
mov r8 , [rsi + region.size]
sub r8 , 200 ; pointer to end of region (plus a bit of buffer)
mov r10, [rsi + region.size]
sub r10, 1 ; mask
mov rsi, r9 ; region start
.top:
mov rcx, rax
and rcx, r10 ; remap the index into the region via masking
add rcx, r9 ; make pointer p into the region
mov rdx, [rcx] ; load 8 bytes at p, always zero
xor rcx, rcx ; no-op
mov DWORD [rsi + rdx + 160], 0 ; store zero at p + 160
add rax, (64 * 67) ; advance a prime number of cache lines slightly larger than a page
dec rdi
jnz .top
ret
这大致相当于insert_ok4[最内层循环的B.size访问（加载）和B.values[B.size] = 1访问（存储） =206=].
专注于循环，我们做一个strided load和一个fixed store。然后将加载位置向前移动一点超过页面大小 (4 KiB)。至关重要的是，存储地址 取决于 加载的结果：因为寻址表达式 [rsi + rdx + 160] 包括 rdx 这是保存加载值的寄存器 1。存储总是发生在相同的地址，因为地址组件的 none 在循环中发生变化（所以我们期望 L1 缓存总是命中）。
原来的散列示例做了更多的工作，随机访问内存，并将存储与加载放在同一行，但这个简单的循环捕获了相同的效果。
我们还使用了另一个版本的基准测试，除了加载和存储之间的空操作 xor rcx, rcx 被 xor rdx, rdx 替换之外，它是相同的。这 打破了 加载和存储地址之间的依赖关系。
天真地，我们并不期望这种依赖性有多大作用。这里的存储是 fire-and-forget: 我们不会再次从存储的位置读取（至少不会多次迭代）所以它们不是任何携带的依赖链的一部分。对于小区域，我们预计瓶颈只是咀嚼 ~8 微指令，而对于大区域，我们预计处理所有缓存未命中的时间将占主导地位：关键是，我们预计许多未命中会被并行处理，因为加载地址可以是从简单的非内存 uops 独立计算。
在下面找到区域大小从 4 KiB 到 256 MiB 的循环性能，具有以下三种变化：
2M dep: 上面显示的循环（存储地址取决于负载）有 2 MiB 大页面.
4K dep: 上面显示的循环（存储地址取决于负载）具有标准的 4 KiB 页面。
4K indep: 上述循环的变体，但用 xor rdx, rdx 替换 xor rcx, rcx 以打破加载结果和存储地址之间的依赖关系，使用 4 KiB 页面。
结果：
对于小区域大小，所有变体的性能基本相同。所有高达 256 KiB 的东西都需要 2 cycles/iteration，仅受循环中的 8 微指令和 CPU width of 4 uops/cycle 限制。一些数学表明我们有不错的 MLP（内存级并行性）：L2 缓存命中有 12 个周期的延迟，但我们每 2 个周期完成一个，所以平均而言我们必须重叠 6 个 L1 未命中的延迟做到这一点。
在 256 KiB 和 4096 KiB 之间，随着 L3 命中开始发生，性能有所下降，但性能良好且 MLP 高。
在 8196 KiB 时，仅 4K dep 情况下，性能会发生灾难性下降，跨越 150 个周期并最终稳定在大约 220 个周期。比其他两种情况2.
慢10倍我们已经可以做出一些关键观察：
- 2M dep 和 4K indep 情况都很快：所以这不是 just 关于商店之间的依赖关系，也关于分页行为。
- 2M dep 的情况是最快的，因此我们知道即使您忘记了记忆，依赖性也不会导致一些基本问题。
- 慢 4K dep 情况下的性能与我机器的内存延迟非常相似。
我在上面提到了 MLP，并根据观察到的性能计算了 MLP 的下限，但在英特尔 CPUs 上，我们可以使用两个性能计数器直接测量 MLP：
l1d_pend_miss.pendingCounts duration of L1D miss outstanding, that is each cycle number of Fill Buffers (FB) outstanding required by Demand Reads.
l1d_pend_miss.pending_cyclesCycles with L1D load Misses outstanding
第一个计数，每个周期，有多少请求来自 L1D。因此，如果正在进行 3 次未命中，则此计数器每个周期递增 3。第二个计数器每个周期递增 1，至少有 one 未命中。您可以将其视为第一个计数器的一个版本，它在每个周期都饱和为 1。这些计数器在一段时间内的比率 l1d_pend_miss.pending / l1d_pend_miss.pending_cycles 是平均 MLP 因子，而任何未命中都是未完成的3.
让我们绘制 4K 基准测试的 dep 和 indep 版本的 MLP 比率：
问题就很清楚了。直到 4096 KiB 的区域，性能是相同的，并且 MLP 很高（对于非常小的区域大小，“没有”MLP，因为根本没有 L1D 未命中）。突然在 8192 KiB，从属案例的 MLP 下降到 1 并保持在那里，而在独立案例中，MLP 几乎达到 10。仅此一项就基本上解释了 10 倍的性能差异：从属案例无法重叠负载，在全部.
为什么？问题似乎是 TLB 未命中。在 8192 KiB 处发生的是基准测试开始缺少 TLB。具体来说，每个 Skylake 核心有 1536 个 STLB（二级 TLB）条目，可以覆盖 1536 × 4096 = 6 MiB 的 4K 页面。因此，在 4 和 8 MiB 区域大小之间，基于 dtlb_load_misses.walk_completed，TLB 未命中每次迭代变为 1，导致这个几乎太完美的假图：
这就是发生的事情：当地址未知的存储在存储缓冲区中时，发生 STLB 未命中的加载不能重叠：它们一次一个。因此，每次访问都会遭受完整的内存延迟。这也解释了为什么 2MB 页面的情况很快：2MB 页面可以覆盖 3GiB 内存，所以对于这些区域大小没有 STLB misses/page 遍历。
为什么
这种行为似乎源于这样一个事实，即 Skylake 和其他早期的 Intel 处理器实现了 page table 一致性， 即使 x86 平台不需要它。页面 table 一致性意味着如果修改地址映射的存储（例如）使用受重新映射影响的虚拟地址的后续加载将一致地看到新映射而无需任何显式刷新。
这一见解来自 Henry Wong，他在他的 excellent article on page walk coherence 中报告说，要做到这一点，如果遇到冲突或 地址未知的商店 ，页面遍历就会终止步行：
Unexpectedly, Intel Core 2 and newer systems behaved as though a pagewalk coherence misspeculation had occurred even though there were no page table modifications. These systems have memory dependence prediction, so the load should have speculatively executed much earlier than the store and broken the data dependence chain.
It turns out it is precisely the early-executing load that is responsible for the incorrectly-detected misspeculation. This gives a hint on how coherence violations may be detected: by comparing pagewalks to known older store addresses (in the store queue?), and assuming a coherence violation if there is an older store with a conflict or an unknown address.
因此，即使这些商店完全无辜，因为它们不修改任何页面 table，它们也会陷入页面 table 一致性机制中。通过查看事件 dtlb_load_misses.miss_causes_a_walk，我们可以找到该理论的进一步证据。与 walk_completed 事件不同，这会计算所有 开始 的行走，即使它们没有成功完成。那个看起来像这样（同样，没有显示 2M，因为它根本没有开始浏览页面）：
咦！ 4K 依赖项显示两次 开始步行，其中只有一次成功完成。每次负重都要走两次。这与页面遍历在迭代 N+1 中开始加载的理论一致，但它发现迭代 N 中的存储仍然位于存储缓冲区中（因为迭代 N 的加载提供了它的地址，并且它仍在进行中).由于地址未知，因此如 Henry 所述，页面遍历被取消。进一步的页面遍历被延迟，直到商店地址被解析。结果是以序列化的方式完成所有加载，因为加载 N+1 的页面遍历必须等待加载 N 的结果。
为什么“bad”和“alt”方法很快
最后，还有一个未解之谜。上面解释了为什么原来的哈希访问速度很慢，但没有解释为什么其他两个很快。关键是这两种快速方法都没有地址未知的存储，因为与负载的数据依赖被推测控制依赖所取代。
看一下 insert_bad 方法的内部循环：
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;
}
}
请注意，商店使用循环索引 i。与索引 [B.size] 来自存储的 insert_ok 情况不同，i 只是寄存器中的一个计算值。现在 i 与加载值 B.size 相关 因为它的最终值将 等于 ，但这是通过比较建立，这是一个推测的控制依赖。它不会导致页面遍历取消的任何问题。这种情况确实有很多错误预测（因为循环出口是不可预测的 table），但对于大区域情况，这些实际上并没有太大危害，因为坏路径通常与好路径进行相同的内存访问（具体来说，下一个插入的值总是相同的）并且内存访问行为占主导地位。
alt情况也是如此：写入的索引是通过计算值建立的 i加载一个值，检查是否是特殊标记值，然后使用索引 i 在该位置写入。同样，没有延迟存储地址，只有快速计算的寄存器值和推测的控制依赖性。
其他硬件呢
和问题作者一样，我在Skylake上发现了效果，但我在Haswell上也观察到了同样的行为。在 Ice Lake 上，我无法重现它：dep 和 indep 的性能几乎相同。
但是，用户 Noah
运行自己做
你可以运行我上面描述的基准你自己。它是 uarch-bench 的一部分。在 Linux（或 WSL，但性能计数器不可用）上，您可以 运行 以下命令来收集结果：
for 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
某些系统可能没有足够的可用性能计数器（如果您启用了超线程），因此您可以每次使用不同的计数器集执行两次 运行。
1 在这种情况下，rdx 始终为零（该区域完全为零）因此存储地址恰好与此寄存器相同未包含在寻址表达式中，但 CPU 不知道！
2 此处，2M dep 案例也开始显示出比 4K indep[=211] 更好的性能=] 案例，尽管差距不大。
3 请注意“虽然任何未命中都是突出的”部分：您还可以将 MLP 计算为 l1d_pend_miss.pending / cycles，这将是一段时间内的平均 MLP ，无论是否有任何未命中。每个都有自己的用处，但在这种情况下，未命中的情况总是很突出，它们给出的值几乎相同。
4 是的，这个和原来的例子有很多不同。我们存储到一个固定位置，而原始循环存储在加载位置附近，每次迭代都会发生变化。我们存储 0 而不是 1。我们不检查 B.size 看它是否太大。在我们的测试中，加载值始终为 0。当桶已满时没有搜索循环。我们不加载一个随机值来寻址，而只是做一个线性步幅。但是，这些不是 material：在两种情况下都会出现相同的效果，您可以通过消除复杂性来逐步修改原始示例，直到达到这个简单的情况。