Pourquoi mon processeur Intel Skylake / Kaby Lake subit-il un mystérieux ralentissement d'un facteur 3 dans une simple mise en œuvre de table de hachage ?

Question

En bref :

J'ai implémenté une simple table de hachage (à clés multiples) avec des buckets (contenant plusieurs éléments) qui correspondent exactement à une cacheline. L'insertion dans un seau de cacheline est très simple, et la partie critique de la boucle principale.

J'ai mis en place trois versions qui produisent le même résultat et devraient se comporter de la même manière.

Le mystère

Cependant, je constate des différences de performance importantes, d'un facteur 3, alors que toutes les versions ont exactement le même modèle d'accès à la ligne de cache et produisent des données de table de hachage identiques.

La meilleure mise en œuvre insert_ok subit un ralentissement d'environ un facteur 3 par rapport aux insert_bad & insert_alt sur mon CPU (i7-7700HQ). Une variante insert_bad est une simple modification de insert_ok qui ajoute une recherche linéaire supplémentaire inutile dans la ligne de cache pour trouver la position où écrire (qu'il connaît déjà) et ne subit pas ce ralentissement de x3.

Le même exécutable montre insert_ok un facteur 1,6 plus rapide par rapport à insert_bad & insert_alt sur d'autres CPU (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)

Le code

// 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;
    }
}

Mon analyse

J'ai essayé diverses modifications de la boucle C++, mais elle est intrinsèquement si simple que le compilateur produira le même assemblage. Il n'est pas vraiment évident, à partir de l'assemblage résultant, de savoir ce que la perte du facteur 3 pourrait causer. J'ai essayé de mesurer la performance, mais je n'arrive pas à trouver de différence significative.

En comparant l'assemblage des 3 versions qui ne sont que des boucles relativement petites, il n'y a rien qui suggère quelque chose de proche qui pourrait causer une perte de facteur 3 entre ces versions.

Par conséquent, je suppose que le ralentissement de 3x est un effet bizarre de la préextraction automatique, ou de la prédiction de branchement, ou de l'alignement des instructions/sauts ou peut-être une combinaison de ces éléments.

Quelqu'un a-t-il une meilleure idée ou de meilleurs moyens de mesurer les effets qui pourraient être en jeu ici ?

Détails

J'ai créé un petit exemple fonctionnel en C++11 qui démontre le problème. Le code est disponible à l'adresse https://github.com/cr-marcstevens/hashtable_mystery

Cela inclut également mes propres binaires statiques qui démontrent ce problème sur mon CPU, car des compilateurs différents peuvent produire un code différent. Ainsi que du code assembleur vidéo pour les trois versions de table de hachage.

mesures d'événements perf

Voici un grand nombre de mesures d'événements de perforation. Je me suis concentré sur celles qui incluent le mot miss y stall . Chaque événement comporte deux lignes :

• la première ligne correspond à insert_ok qui a le ralentissement

• la deuxième ligne correspond à insert_alt qui comporte une boucle supplémentaire et un travail supplémentaire, mais qui est finalement plus rapide

  === 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

Contexte

J'implémente une attaque cryptographique en C++11 et je dois trouver de nombreuses collisions entre deux grandes listes (toutes deux générées à la volée). Une partie cruciale de l'attaque consiste donc juste en deux boucles critiques :

1. en remplissant d'abord une table de hachage avec une liste
2. puis en comparant l'autre liste avec la table de hachage.

Les opérations de la table de hachage sont donc critiques en termes de performances, et un ralentissement de facteur 3 signifie que l'attaque est 3x plus lente.

En ce qui concerne la conception : En plus d'essayer de minimiser l'utilisation de la mémoire, j'essaie également de faire en sorte qu'une opération typique de table de hachage ne fonctionne que sur une seule ligne de cache. Je m'attends à ce que cela augmente les performances globales de l'attaque, en particulier lorsque l'attaque est exécutée sur tous les cœurs du processeur.

Answer 1

Résumé

Le TLDR est que les chargements qui manquent tous les niveaux de la TLB (et qui nécessitent donc une marche de page) et qui sont séparés par adresse inconnue Les magasins ne peuvent pas s'exécuter en parallèle, c'est-à-dire que les charges sont sérialisées et que les parallélisme au niveau de la mémoire (MLP) est plafonné à 1. En effet, les magasins clôture les charges, tout comme lfence serait.

La version lente de votre fonction d'insertion donne lieu à ce scénario, tandis que les deux autres ne le font pas (l'adresse du magasin est connue). Pour les régions de grande taille, le modèle d'accès à la mémoire domine, et les performances sont presque directement liées au MLP : les versions rapides peuvent chevaucher les load misses et obtenir un MLP d'environ 3, ce qui se traduit par un gain de vitesse de 3x (et le cas de reproduction plus étroit dont nous discutons ci-dessous peut montrer plus d'un 10x différence sur Skylake).

La raison sous-jacente semble être que le processeur Skylake essaie de maintenir cohérence page-tableau qui n'est pas requis par la spécification mais qui permet de contourner les bogues du logiciel.

Les détails

Pour ceux qui sont intéressés, nous allons entrer dans les détails de ce qui se passe.

J'ai pu reproduire le problème immédiatement sur ma machine Skylake i7-6700HQ, et en supprimant les parties superflues, nous pouvons réduire le benchmark original d'insertion de hachage à cette simple boucle, qui présente le même problème :

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

Cela équivaut à peu près à la B.size l'accès (la charge) et la B.values[B.size] = 1 l'accès (le magasin) de la boucle la plus interne de insert_ok 4 .

En nous concentrant sur la boucle, nous effectuons un chargement progressif et un stockage fixe. Ensuite, on avance l'emplacement de chargement d'un peu plus que la taille d'une page (4 KiB). Il est essentiel que l'adresse de stockage dépend de le résultat de la charge : comme l'expression d'adressage [rsi + rdx + 160] comprend rdx qui est le registre contenant la valeur chargée 1 . Le stockage s'effectue toujours à la même adresse, car aucun des composants de l'adresse ne change dans la boucle (nous nous attendons donc toujours à un hit du cache L1).

L'exemple original de hachage faisait beaucoup plus de travail, accédait à la mémoire de façon aléatoire, et avait le stockage sur la même ligne que le chargement, mais cette simple boucle capture le même effet.

Nous utilisons également une autre version du benchmark, qui est identique à l'exception du no-op xor rcx, rcx entre la charge et le magasin est remplacé par xor rdx, rdx . Ce site casse la dépendance entre l'adresse de la charge et celle du magasin.

Naïvement, nous ne nous attendons pas à ce que cette dépendance fasse grand-chose. Les magasins sont ici le feu et l'oubli : nous ne lisons pas à nouveau à partir de l'emplacement stocké (du moins pas avant de nombreuses itérations), de sorte qu'ils ne font pas partie de la chaîne de dépendance transportée. Pour les petites régions, nous nous attendons à ce que le goulot d'étranglement soit juste la mastication des ~8 uops et pour les grandes régions, nous nous attendons à ce que le temps pour gérer tous les manques de cache domine : de manière critique, nous nous attendons à ce que de nombreux manques soient gérés en parallèle puisque les adresses de chargement peuvent être calculées indépendamment à partir de simples uops non-mémoire.

Vous trouverez ci-dessous les performances en cycles pour des tailles de régions allant de 4 KiB à 256 MiB, avec les trois variations suivantes :

2M dép : La boucle présentée ci-dessus (avec l'adresse de stockage dépendant de la charge) avec 2 MiB pages énormes .

4K dép : La boucle présentée ci-dessus (avec l'adresse de stockage dépendant du chargement) avec des pages standard de 4 KiB.

4K indépendant : La variante de la boucle ci-dessus avec mais avec xor rdx, rdx remplacement de xor rcx, rcx pour briser la dépendance entre le résultat du chargement et l'adresse de stockage, en utilisant des pages de 4 KiB.

Le résultat :

Les performances de toutes les variantes sont fondamentalement identiques pour les petites tailles de régions. Tout ce qui est jusqu'à 256 KiB prend 2 cycles/itération, limités simplement par les 8 uops de la boucle et l'option Largeur du CPU de 4 uops/cycle . Un peu de maths montre que nous avons un parallélisme au niveau de la mémoire (MLP) décent : un accès au cache L2 a une latence de 12 cycles, mais nous en effectuons un tous les 2 cycles, donc en moyenne nous devons chevaucher la latence de 6 accès au cache L1 pour atteindre ce résultat.

Entre 256 KiB et 4096 KiB, les performances se dégradent quelque peu car les hits L3 commencent à se produire, mais les performances sont bonnes et le MLP élevé.

A 8196 KiB, les performances se dégradent de manière catastrophique pour uniquement le site 4K dep en passant au-dessus de 150 cycles et en se stabilisant finalement à environ 220 cycles. C'est plus que 10 fois plus lent que les deux autres cas 2 .

Nous pouvons déjà faire quelques observations clés :

• Les deux 2M dép et le 4K indépendant Les cas sont rapides : ce n'est donc pas juste sur la dépendance entre les magasins, mais aussi sur le comportement de pagination.
• En 2M dép est le plus rapide de tous, ce qui nous permet de savoir que la dépendance ne pose pas de problème fondamental, même en cas de perte de mémoire.
• La performance de la lenteur 4K dep est suspicieusement similaire à la latence de la mémoire de ma machine.

J'ai mentionné la MLP ci-dessus et calculé une limite inférieure de la MLP en fonction des performances observées, mais sur les CPU Intel, nous pouvons mesurer la MLP directement en utilisant deux compteurs de performances :

l1d_pend_miss.pending

Compte la durée des manques L1D en cours, c'est-à-dire le nombre de tampons de remplissage (FB) en cours à chaque cycle, requis par les lectures à la demande.

l1d_pend_miss.pending_cycles

Cycles avec charge L1D Manques en suspens

Le premier compte, à chaque cycle, combien de requêtes sont en attente de la part du L1D. Donc si 3 misses sont en cours, ce compteur s'incrémente de 3 à chaque cycle. Le deuxième compteur s'incrémente de 1 à chaque cycle, au minimum un miss est en cours. Vous pouvez le voir comme une version du premier compteur qui sature à 1 à chaque cycle. Le rapport l1d_pend_miss.pending / l1d_pend_miss.pending_cycles de ces compteurs sur une période de temps est le facteur MLP moyen alors que tout échec est en suspens. 3 .

Traçons ce rapport MLP pour le dep y indépendant des versions du benchmark 4K :

Le problème devient très clair. Jusqu'à des régions de 4096 KiB, les performances sont identiques, et le MLP est élevé (pour les régions de très petite taille, il n'y a "pas" de MLP puisqu'il n'y a pas du tout de ratés de L1D). Soudain, à 8192 KiB, le MLP pour le cas dépendant tombe à 1 et y reste, alors que dans le cas indépendant, le MLP passe à presque 10. Ce seul fait explique la différence de performance de 10x : le cas dépendant n'est pas capable de chevaucher les charges, du tout.

Pourquoi ? Le problème semble être les ratés de la TLB. Ce qui se passe à 8192 KiB est que le benchmark commence à manquer la TLB. Plus précisément, chaque cœur Skylake possède 1536 entrées STLB (TLB de second niveau) qui peuvent couvrir 1536 × 4096 = 6 MiB de pages 4K. Donc, juste entre les tailles de région de 4 et 8 MiB, les manques de TLB passent à 1 par itération sur la base de dtlb_load_misses.walk_completed ce qui conduit à cette intrigue presque trop parfaite :

C'est donc ce qui se passe : lorsque des magasins à adresse inconnue sont dans le tampon de stockage, les chargements qui prennent des misses STLB ne peuvent pas se chevaucher : ils vont un par un. Vous subissez donc toute la latence de la mémoire pour chaque accès. Cela explique également pourquoi le cas de la page de 2 Mo était rapide : les pages de 2 Mo peuvent couvrir 3 Go de mémoire, il n'y a donc pas de manquements STLB/trajets de page pour ces tailles de région.

Pourquoi

Ce comportement semble provenir du fait que Skylake et d'autres processeurs Intel plus anciens implémentent cohérence de la table des pages, même si la plate-forme x86 ne l'exige pas. La cohérence des tables de pages signifie que si un stockage qui modifie un mappage d'adresse (par exemple), un chargement ultérieur qui utilise une adresse virtuelle affectée par le remappage verra systématiquement le nouveau mappage sans aucun vidage explicite.

Cette idée vient d'Henry Wong qui rapporte dans sa excellent article sur la cohérence de la marche des pages que pour ce faire, les promenades de page sont terminées si un conflit ou une magasin à adresse inconnue est rencontrée au cours de la promenade :

De manière inattendue, les systèmes Intel Core 2 et plus récents se sont comportés comme si une erreur de cohérence de pagewalk s'était produite, même s'il n'y a pas eu de modification de la table des pages. Ces systèmes disposent d'une prédiction de la dépendance de la mémoire, de sorte que le chargement aurait dû s'exécuter de manière spéculative bien avant le stockage et rompre la chaîne de dépendance des données.

Il s'avère que c'est précisément la charge d'exécution précoce qui est responsable de la mauvaise détection de la spéculation. Cela donne un indice sur la façon dont les violations de cohérence peuvent être détectées : en comparant les pages aux adresses de magasins plus anciens connus (dans la file d'attente des magasins ?), et en supposant une violation de cohérence s'il y a un magasin plus ancien avec un conflit ou une adresse inconnue.

Ainsi, même si ces magasins sont totalement innocents dans la mesure où ils ne modifient aucune table de pages, ils sont pris dans le mécanisme de cohérence des tables de pages. Nous pouvons trouver d'autres preuves de cette théorie en regardant l'évènement dtlb_load_misses.miss_causes_a_walk . Contrairement à la walk_completed événement, cela compte toutes les marches qui a commencé même si elles n'aboutissent pas. Cela ressemble à ceci (encore une fois, 2M n'est pas montré parce qu'il ne démarre aucune marche de page du tout) :

Huh ! Le 4K dépendant montre deux ont commencé des marches, dont une seule s'achève avec succès. Cela fait deux promenades pour chaque chargement. Cela correspond à la théorie selon laquelle la marche des pages commence pour le chargement de l'itération N+1, mais trouve le magasin de l'itération N toujours dans le tampon du magasin (puisque le chargement de l'itération N fournit son adresse et qu'il est toujours en cours). Comme l'adresse est inconnue, le parcours de la page est annulé comme le décrit Henry. D'autres déplacements de page sont retardés jusqu'à ce que l'adresse du magasin soit résolue. Le résultat est que tous les chargements se terminent d'une manière sérialisée parce que le tour de page pour le chargement N+1 doit attendre le résultat du chargement N.

Pourquoi les méthodes "mauvaise" et "alt" sont rapides

Enfin, il reste un mystère. Ce qui précède explique pourquoi l'accès original au hachage était lent, mais pas pourquoi les deux autres étaient rapides. La clé est que les deux méthodes rapides n'ont pas de magasins à adresse inconnue, car la dépendance des données avec le chargement est remplacée par une dépendance de contrôle spéculative.

Jetez un coup d'œil à la boucle interne de la insert_bad approche :

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;
    }
}

Notez que les magasins utilisent l'indice de boucle i . Contrairement à la insert_ok cas, où l'indice [B.size] provient d'un magasin, i est simplement une valeur calculée dans un registre. Maintenant i es connexe à la valeur chargée B.size puisque sa valeur finale sera égal mais cela est établi via une comparaison qui est une dépendance de contrôle spéculée. Cela ne pose pas de problème avec l'annulation de la marche des pages. Ce scénario a beaucoup d'erreurs de prédiction (puisque la sortie de la boucle est imprévisible) mais pour le cas d'une grande région, elles ne sont pas trop nuisibles parce que le mauvais chemin fait habituellement les mêmes accès mémoire que le bon chemin (spécifiquement, la prochaine valeur insérée est toujours la même) et le comportement d'accès mémoire domine.

Il en va de même pour le alt cas : l'index à écrire est établi à l'aide d'une valeur calculée. i pour charger une valeur, vérifier s'il s'agit de la valeur du marqueur spécial, puis écrire à cet endroit en utilisant l'index i . Encore une fois, pas d'adresse de stockage différée, juste une valeur de registre rapidement calculée et une dépendance de contrôle spéculée.

Qu'en est-il des autres matériels ?

Comme l'auteur de la question, j'ai trouvé l'effet sur Skylake, mais j'ai aussi observé le même comportement sur Haswell. Sur Ice Lake, je n'arrive pas à le reproduire : tant les dep y indépendant ont des performances presque identiques.

L'utilisateur Noah, cependant, a déclaré qu'il pouvait se reproduire sur Tigerlake en utilisant le repère original pour certains alignements. Je pense que la cause la plus probable est que TGL n'est pas sujet à ce comportement de page walk, mais plutôt qu'à certains alignements, les prédicteurs de désambiguïsation de la mémoire entrent en collision, provoquant un effet très similaire : les chargements ne peuvent pas s'exécuter avant les stockages antérieurs à adresse inconnue parce que le processeur pense que les stockages pourraient faire suivre le chargement.

Exécutez-le vous-même

Vous pouvez exécuter vous-même le benchmark que je décris ci-dessus. C'est une partie de uarch-bench . Sous Linux (ou WSL, mais les compteurs de performance ne sont pas disponibles), vous pouvez exécuter la commande suivante pour collecter les résultats :

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

Certains systèmes peuvent ne pas avoir suffisamment de compteurs de performance disponibles (si vous avez activé l'hyperthreading), vous pouvez donc effectuer deux exécutions en utilisant des ensembles de compteurs différents à chaque fois.

---

1 Dans ce cas, rdx est toujours égal à zéro (la région est entièrement remplie de zéros). L'adresse de stockage est donc la même que si ce registre n'était pas inclus dans l'expression d'adressage, mais le CPU ne le sait pas !

2 Ici, le 2M dép commence également à montrer de meilleures performances que le cas 4K indépendant bien que l'écart soit modeste.

3 Notez la partie "tant qu'un échec est en cours" : vous pourriez aussi calculer MLP comme suit l1d_pend_miss.pending / cycles qui serait la MLP moyenne sur une période de temps, indépendamment de l'existence ou non d'échecs. Chacune est utile à sa manière, mais dans un cas comme celui-ci avec des ratés constamment en suspens, elles donnent des valeurs presque identiques.

4 Oui, il y a de nombreuses différences entre cet exemple et l'exemple original. Nous stockons à un seul emplacement fixe, alors que la boucle originale stockait près de l'emplacement de chargement, qui varie à chaque itération. Nous stockons 0 et non 1. Nous ne vérifions pas B.size pour voir si elle est trop grande. Dans notre test, la valeur chargée est toujours 0. Il n'y a pas de boucle de recherche pour savoir quand le seau est plein. Nous ne chargeons pas une valeur aléatoire à l'adresse, mais faisons simplement un pas linéaire. Cependant, ce ne sont pas des éléments matériels : le même effet se produit dans les deux cas et vous pouvez modifier progressivement l'exemple original en supprimant la complexité jusqu'à atteindre ce cas simple.