时间戳

首页 > 解决方案 > 为什么循环从 Uop Cache 提供的 uops 过渡到 LSD 会导致分支未命中率激增？

x86-64 - 为什么循环从 Uop Cache 提供的 uops 过渡到 LSD 会导致分支未命中率激增？

问题描述

所有基准测试均在 Icelake 或Whiskey Lake（在 Skylake Family 中）上运行。

概括

我看到一个奇怪的现象，当循环从耗尽Uop 缓存过渡到耗尽LSD（循环流检测器）时，分支未命中会出现峰值，这可能会导致严重的性能下降。我在 Icelake 和 Whiskey Lake 上测试了一个嵌套循环，其中外部循环具有足够大的主体 st 整个东西不适合LSD本身，但内部循环足够小以适合 LSD。

基本上一旦内部循环达到一些迭代计数解码似乎切换为idq.dsb_uops (Uop Cache)到lsd.uops (LSD) 并且此时分支未命中 （没有相应的分支跳转）导致严重的性能下降。注意：这似乎只发生在嵌套循环中。例如， Travis Down 的循环测试不会显示分支未命中的任何有意义的变化。AFAICT 这与循环从用尽 Uop Cache过渡到用尽LSD时有关。

问题

  1. 当循环从用尽 Uop 缓存转换为用尽LSD时会发生什么，从而导致 Branch Misses出现这种峰值？

  2. 有没有办法避免这种情况？

基准

这是我能想出的最小可重现示例：

注意：如果.p2align删除语句，则两个循环都将适合 LSD，并且不会有转换。

#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BENCH_ATTR __attribute__((noinline, noclone, aligned(4096)))

static const uint64_t outer_N = (1UL << 24);


static void BENCH_ATTR
bench(uint64_t inner_N) {
    uint64_t inner_loop_cnt, outer_loop_cnt;
    asm volatile(
        ".p2align 12\n"
        "movl   %k[outer_N], %k[outer_loop_cnt]\n"
        ".p2align   6\n"
        "1:\n"
        "movl   %k[inner_N], %k[inner_loop_cnt]\n"
        // Extra align surrounding inner loop so that the entire thing
        // doesn't execute out of LSD.
        ".p2align   10\n"
        "2:\n"
        "decl   %k[inner_loop_cnt]\n"
        "jnz    2b\n"
        ".p2align   10\n"
        "decl   %k[outer_loop_cnt]\n"
        "jnz    1b\n"
        : [ inner_loop_cnt ] "=&r"(inner_loop_cnt),
          [ outer_loop_cnt ] "=&r"(outer_loop_cnt)
        : [ inner_N ] "ri"(inner_N), [ outer_N ] "i"(outer_N)
        :);
}
int
main(int argc, char ** argv) {
    assert(argc > 1);
    uint64_t inner_N = atoi(argv[1]);
    bench(inner_N);
}

编译：gcc -O3 -march=native -mtune=native <filename>.c -o <filename>

运行 Icelake：sudo perf stat -C 0 --all-user -e cycles -e branches -e branch-misses -x, -e idq.ms_uops -e idq.dsb_uops -e lsd.uops taskset -c 0 ./<filename> <N inner loop iterations>

运行威士忌湖：sudo perf stat -C 0 -e cycles -e branches -e branch-misses -x, -e idq.ms_uops -e idq.dsb_uops -e lsd.uops taskset -c 0 ./<filename> <N inner loop iterations>

图表

编辑：x 标签是内循环的 N 次迭代。

下面是Branch Misses、Branches和LSD Uops的图表。

一般可以看到 1) Branches中没有对应的跳转。2）增加的Branch Misses数量稳定在一个常数。3) Branch Misses和LSD Uops之间有很强的关系。

冰湖图：

icl-分支

威士忌湖图：

skl-分支

下面是 Icelake 的Branch Misses、Cycles和LSD Uops的图表 ，因为性能几乎没有受到以下影响：

icl-循环

分析

下面的硬数字。

对于Icelake，从LSD开始和N = 22结束于_ _ _ _ 在此期间 ， Cycles也增加了2倍。对于所有分支未命中保持在1.67 x 10^7左右（大约）。对于分支继续仅线性增加。N = 27N > 27 outer_loop_NN = [17, 40]

Whiskey Lake的结果看起来不同，因为 1)N开始波动N = 35并持续波动直到N = 49。2) 对性能的影响较小，数据波动较大。话虽如此，与从由Uop Cache提供的 uops到由LSD提供的转换相对应的Branch-Misses的增加仍然存在。

结果

数据是 25 次运行的平均结果。

冰湖结果：

ñ 循环 分支机构 分支未命中 idq.ms_uops idq.dsb_uops lsd.uops
1 33893260 67129521 1590 43163 115243 83908732
2 42540891 83908928 1762 49023 142909 100690381
3 50725933 100686143 1782 47656 142506 117440256
4 67533597 117461172 1655 52538 186123 134158311
5 68022910 134238387 1711 53405 204481 150954035
6 85543126 151018722 1924年 62445 141397 167633971
7 84847823 167799220 1935年 60248 160146 184563523
8 101532158 184570060 1709 60064 361208 201100179
9 101864898 201347253 1773 63827 459873 217780207
10 118024033 218124499 1698 59480 177223 234834304
11 118644416 234908571 2201 62514 422977 251503052
12 134627567 251678909 1679 57262 133462 268435650
13 285607942 268456135 1770 74070 285032524 315423
14 302717754 285233352 1731 74663 302101097 15953
15 321627434 302010569 81796 77831 319192830 1520819
16 337876736 318787786 71638 77056 335904260 1265766
17 353054773 335565563 1798 79839 352434780 15879
18 369800279 352344970 1978年 79863 369229396 16790
19 386921048 369119438 1972年 84075 385984022 16115
20 404248461 385896655 29454 85348 402790977 510176
21 421100725 402673872 37598 83400 419537730 729397
22 519623794 419451095 4447767 91209 431865775 97827331
23 702206338 436228323 12603617 109064 427880075 327661987
24 710626194 453005538 12316933 106929 432926173 344838509
25 863214037 469782765 14641887 121776 428085132 614871430
26 761037251 486559974 13067814 113011 438093034 418124984
27 832686921 503337195 16381350 113953 421924080 556915419
28 854713119 520114412 16642396 124448 420515666 598907353
29 869873144 536891629 16572581 119280 421188631 629696780
30 889642335 553668847 16717446 120116 420086570 668628871
31 906912275 570446064 16735759 126094 419970933 702822733
32 923023862 587223281 16706519 132498 420332680 735003892
33 940308170 604000498 16744992 124365 419945191 770185745
34 957075000 620777716 16726856 133675 420215897 802779119
35 974557538 637554932 16763071 134871 419764866 838012637
36 991110971 654332149 16772560 130903 419641144 872037131
37 1008489575 671109367 16757219 138788 419900997 904638287
38 1024971256 687886583 16772585 139782 419663863 938988917
39 1041404669 704669411 16776722 137681 419617131 972896126
40 1058594326 721441018 16773492 142959 419662133 1006109192
41 1075179100 738218235 16776636 141185 419601996 1039892900
42 1092093726 754995452 16776233 142793 419611902 1073373451
43 1108706464 771773224 16776359 139500 419610885 1106976114
44 1125413652 788549886 16764637 143717 419889127 1139628280
45 1142023614 805327103 16778640 144397 419558217 1174329696
46 1158833317 822104321 16765518 148045 419889914 1206833484
47 1175665684 838881537 16778437 148347 419562885 1241397845
48 1192454164 855658755 16778865 153651 419552747 1275006511
49 1210199084 872436025 16778287 152468 419599314 1307945613
50 1226321832 889213188 16778464 155552 419572344 1341893668
51 1242886388 905990406 16778745 155401 419559249 1375589883
52 1259559053 922767623 16778809 154847 419554082 1409206082
53 1276875799 939544839 16778460 162521 419576455 1442424993
54 1293113199 956322057 16778931 154913 419550955 1476316161
55 1310449232 973099274 16778534 157364 419578102 1509485876
56 1327022109 989876491 16778794 162881 419562403 1543193559
57 1344097516 1006653708 16778906 157486 419567545 1576414302
58 1362935064 1023430928 16778959 315120 419583132 1609691339
59 1381567560 1040208143 16778564 179997 419661259 1640660745
60 1394829416 1056985359 16778779 167613 419575969 1677034188
61 1411847237 1073762626 16778071 166332 419613028 1710194702
62 1428918439 1090539795 16778409 168073 419610487 1743644637
63 1445223241 1107317011 16778486 172446 419591254 1777573503
64 1461530579 1124094228 16769606 169559 419970612 1810351736

威士忌湖结果：

ñ 循环 分支机构 分支未命中 idq.dsb_uops lsd.uops
1 8332553879 35005847 37925 1799462 6019
2 8329926329 51163346 34338 1114352 5919
3 8357233041 67925775 32270 9241935 5555
4 8379609449 85364250 35667 18215077 5712
5 8394301337 101563554 33177 26392216 2159
6 8409830612 118918934 35007 35318763 5295
7 8435794672 135162597 35592 43033739 4478
8 8445843118 152636271 37802 52154850 5629
9 8459141676 168577876 30766 59245754 1543
10 8475484632 185354280 30825 68059212 4672
11 8493529857 202489273 31703 77386249 5556
12 8509281533 218912407 32133 84390084 4399
13 8528605921 236303681 33056 93995496 2093
14 8553971099 252439989 572416 99700289 2477
15 8558526147 269148605 29912 109772044 6121
16 8576658106 286414453 29839 118504526 5850
17 8591545887 302698593 28993 126409458 4865
18 8611628234 319960954 32568 136298306 5066
19 8627289083 336312187 30094 143759724 6598
20 8644741581 353730396 49458 152217853 9275
21 8685908403 369886284 1175195 161313923 7958903
22 8694494654 387336207 354008 169541244 2553802
23 8702920906 403389097 29315 176524452 12932
24 8711458401 420211718 31924 184984842 11574
25 8729941722 437299615 32472 194553843 12002
26 8743658904 453739403 28809 202074676 13279
27 8763317458 470902005 32298 211321630 15377
28 8788189716 487432842 37105 218972477 27666
29 8796580152 504414945 36756 228334744 79954
30 8821174857 520930989 39550 235849655 140461
31 8818857058 537611096 34142 648080 79191
32 8855038758 555138781 37680 18414880 70489
33 8870680446 571194669 37541 34596108 131455
34 8888946679 588222521 33724 52553756 80009
35 9256640352 604791887 16658672 132185723 41881719
36 9189040776 621918353 12296238 257921026 235389707
37 8962737456 638241888 1086663 109613368 35222987
38 9005853511 655453884 2059624 131945369 73389550
39 9005576553 671845678 1434478 143002441 51959363
40 9284680907 688991063 12776341 349762585 347998221
41 9049931865 705399210 1778532 174597773 72566933
42 9314836359 722226758 12743442 365270833 380415682
43 9072200927 739449289 1344663 205181163 61284843
44 9346737669 75576​​6179 12681859 383580355 409359111
45 9117099955 773167996 1801713 235583664 88985013
46 9108062783 789247474 860680 250992592 43508069
47 9129892784 806871038 984804 268229102 51249366
48 9146468279 822765997 1018387 282312588 58278399
49 9476835578 840085058 13985421 241172394 809315446
50 9495578​​885 856579327 14155046 241909464 847629148
51 9537115189 873483093 15057500 238735335 932663942
52 9556102594 890026435 15322279 238194482 982429654
53 9589094741 907142375 15899251 234845868 1052080437
54 9609053333 923477989 16049518 233890599 1092323040
55 9628950166 940997348 16172619 235383688 1131146866
56 9650657175 957049360 16445697 231276680 1183699383
57 9666446210 973785857 16330748 233203869 1205098118
58 9687274222 990692518 16523542 230842647 1254624242
59 9706652879 1007946602 16576268 231502185 1288374980
60 9720091630 1024044005 16547047 230966608 1321807705
61 9741079017 1041285110 16635400 230873663 1362929599
62 9761596587 1057847755 16683756 230289842 1399235989
63 9782104875 1075055403 16299138 237386812 1397167324
64 9790122724 1091147494 16650471 229928585 1463076072

编辑：值得注意的两件事：

  1. 如果我在内部循环中添加填充，使其不适合 uop 缓存，我直到 150 次迭代才会看到这种行为。

  2. lfence在外循环中添加一个带有填充的 on 会将 N 阈值更改为 31。

edit2：清除分支历史的基准条件被颠倒了。应该cmove不是cmovne。对于固定版本，任何迭代计数都会以与上述相同的速率 (1.67 * 10^9)看到升高的分支未命中率。这意味着LSD本身不会导致Branch Misses，但留下了LSD以某种方式击败Branch Predictor的可能性（我认为是这种情况）。

static void BENCH_ATTR
bench(uint64_t inner_N) {
    uint64_t inner_loop_cnt, outer_loop_cnt;
    asm volatile(
        ".p2align 12\n"
        "movl   %k[outer_N], %k[outer_loop_cnt]\n"
        ".p2align   6\n"
        "1:\n"
        "testl  $3, %k[outer_loop_cnt]\n"
        "movl   $1000, %k[inner_loop_cnt]\n"
        THIS NEEDS TO BE CMOVE
        "cmovne   %k[inner_N], %k[inner_loop_cnt]\n"
        // Extra align surrounding inner loop so that the entire thing
        // doesn't execute out of LSD.
        ".p2align   10\n"
        "2:\n"
        "decl   %k[inner_loop_cnt]\n"
        "jnz    2b\n"
        ".p2align   10\n"
        "decl   %k[outer_loop_cnt]\n"
        "jnz    1b\n"
        : [ inner_loop_cnt ] "=&r"(inner_loop_cnt),
          [ outer_loop_cnt ] "=&r"(outer_loop_cnt)
        : [ inner_N ] "ri"(inner_N), [ outer_N ] "i"(outer_N)
        :);
}

标签： x86-64cpu-architecturemicro-optimizationbranch-predictionmicro-architecture

解决方案

原因

  • Branch Misses峰值的原因是内部循环耗尽LSD引起的。

  • LSD导致低迭代次数的额外分支未命中的原因是LSD上的“停止”条件是分支未命中。

来自英特尔优化手册第 86 页。

每个周期将循环发送到分配 5 µops。在发送了 46 个微操作中的 45 个后，在下一个周期中仅发送一个微操作，这意味着在该周期中，浪费了 4 个分配槽。这种模式会不断重复，直到因错误预测而退出循环。硬件循环展开可最大限度地减少 LSD 期间浪费的插槽数。

本质上发生的事情是，当足够低的迭代计数耗尽Uop 缓存时，它们是完全可以预测的。但是当它们用完LSD时，因为LSD的内置停止条件是一个分支错误预测，我们会看到外部循环的每次迭代都有一个额外的分支未命中。我想要点是不要让嵌套循环在LSD之外执行。请注意，LSD仅在 ~[20, 25] 次迭代后才会启动，因此具有 < 20 次迭代的内循环将运行最佳。

基准

所有基准测试都在Icelake上运行

新基准与原始帖子中的基准基本相同，但在@PeterCordes 的建议下，我在内部循环中添加了固定字节大小但数量不同的 nop。这个想法是固定长度的，因此分支在BHT（分支历史表）中的别名方式没有变化，但会改变 nop 的数量以有时会击败LSD。

我使用了 124 字节的 nop 填充，因此 nop 填充 + 的大小decl; jcc总计为 128 字节。

基准代码如下：

#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#ifndef INNER_NOPS
#error "INNER_NOPS must be defined"
#endif

         
#define BENCH_ATTR __attribute__((noinline, noclone, aligned(4096)))

static const uint64_t outer_N   = (1UL << 24);
static const uint64_t bht_shift = 4;
static const uint64_t bht_mask  = (1023 << bht_shift);

#define NOP1   ".byte 0x90\n"
#define NOP2   ".byte 0x66,0x90\n"
#define NOP3   ".byte 0x0f,0x1f,0x00\n"
#define NOP4   ".byte 0x0f,0x1f,0x40,0x00\n"
#define NOP5   ".byte 0x0f,0x1f,0x44,0x00,0x00\n"
#define NOP6   ".byte 0x66,0x0f,0x1f,0x44,0x00,0x00\n"
#define NOP7   ".byte 0x0f,0x1f,0x80,0x00,0x00,0x00,0x00\n"
#define NOP8   ".byte 0x0f,0x1f,0x84,0x00,0x00,0x00,0x00,0x00\n"
#define NOP9   ".byte 0x66,0x0f,0x1f,0x84,0x00,0x00,0x00,0x00,0x00\n"
#define NOP10  ".byte 0x66,0x66,0x0f,0x1f,0x84,0x00,0x00,0x00,0x00,0x00\n"
#define NOP11  ".byte 0x66,0x66,0x66,0x0f,0x1f,0x84,0x00,0x00,0x00,0x00,0x00\n"


static void BENCH_ATTR
bench(uint64_t inner_N) {
    uint64_t inner_loop_cnt, outer_loop_cnt, tmp;
    asm volatile(
        ".p2align 12\n"
        "movl   %k[outer_N], %k[outer_loop_cnt]\n"
        ".p2align   6\n"
        "1:\n"
        "movl   %k[inner_N], %k[inner_loop_cnt]\n"
        ".p2align   10\n"
        "2:\n"
        // This is defined in "inner_nops.h" with the necessary padding.
        INNER_NOPS
        "decl   %k[inner_loop_cnt]\n"
        "jnz    2b\n"
        ".p2align   10\n"
        "decl   %k[outer_loop_cnt]\n"
        "jnz    1b\n"
        : [ inner_loop_cnt ] "=&r"(inner_loop_cnt),
          [ outer_loop_cnt ] "=&r"(outer_loop_cnt), [ tmp ] "=&r"(tmp)
        : [ inner_N ] "ri"(inner_N), [ outer_N ] "i"(outer_N),
          [ bht_mask ] "i"(bht_mask), [ bht_shift ] "i"(bht_shift)
        :);
}
// gcc -O3 -march=native -mtune=native lsd-branchmiss.c -o lsd-branchmiss
int
main(int argc, char ** argv) {
    assert(argc > 1);
    uint64_t inner_N = atoi(argv[1]);
    bench(inner_N);
    return 0;
}

测试

我测试了nop count = [0, 39]。

请注意，nop count = 1内部循环中不仅是 1 nop，而且实际上是以下内容：

#define INNER_NOPS NOP10 NOP10 NOP10 NOP10 NOP10 NOP10 NOP10 NOP10 NOP10 NOP10 NOP10 NOP10 NOP3 NOP1

达到完整的 128 字节填充。

结果

  • 在nop count <= 32内部循环能够用完LSD ，并且当它足够大时，我们始终会看到 elevant Branch Misses 。Iterations请注意，提升的Branch Misses编号对应于 1-1 的编号outer loop iterations。对于这些数字outer loop iterations = 2^24

  • 在nop count > 32循环中，LSD有许多 uops并且用完了Uop Cache。在这里，我们看不到持续升高的 分支未命中，直到它的BHTIterations条目变得很大以存储其整个历史。

nop 计数 > 32（无 LSD）

一旦LSD的nop 太多，分支未命中的数量就会保持相对较低，并出现一些一致的峰值，直到Iterations = 146分支未命中的数量达到outer loop iterations（在这种情况下为 2 ^ 24）并保持不变。我的猜测是，这是BHT能够存储的历史上限。

下面是分支未命中 (Y)与迭代 (X)的关系图nop count = [33, 39]：

高音

所有的线都遵循相同的模式并具有相同的尖峰。outer loop iterations到146 之前的大峰值位于Iterations = [42, 70, 79, 86, 88]. 这是始终可重复的。我不确定这些值有什么特别之处。

然而，关键点是，对于大多数人来说，Iterations = [20, 145] 分支未命中率相对较低，这表明整个内部循环都被正确预测了。

nop 计数 <= 32 (LSD)

这个数据有点噪音，所有不同的数据都nop count遵循大致相同的尖峰趋势，在 lsd.oups 尖峰outer loop iterations 的同时（Iterations = [21, 25]请注意，这是 2-3 个数量级）4-5个数量级。

在皮尔逊相关系数为. nop count_ _ _ 因为稳定点在范围内。iterationouter loop iterations0.81nop count = [0, 32]iterations = [15, 34]

下面是分支未命中 (Y)与迭代 (X)的关系图nops = [0, 32]：

肺组织

一般来说，有一些噪音，所有不同的都nop count遵循相同的趋势。与lsd.uops相比，它们也遵循相同的趋势。

下面是一个带有nop和分支未命中与lsd.uop和idq.dsb_uops之间的Pearson 相关性的表。

无 迷幻药 微指令缓存
0 0.961 -0.041
1 0.955 -0.081
2 0.919 -0.122
3 0.918 -0.299
4 0.947 -0.117
5 0.934 -0.298
6 0.894 -0.329
7 0.907 -0.308
8 0.91 -0.322
9 0.915 -0.316
10 0.877 -0.342
11 0.908 -0.28
12 0.874 -0.281
13 0.875 -0.523
14 0.87 -0.513
15 0.889 -0.522
16 0.858 -0.569
17 0.89 -0.507
18 0.858 -0.537
19 0.844 -0.565
20 0.816 -0.459
21 0.862 -0.537
22 0.848 -0.556
23 0.852 -0.552
24 0.85 -0.561
25 0.828 -0.573
26 0.857 -0.559
27 0.802 -0.372
28 0.762 -0.425
29 0.721 -0.112
30 0.736 -0.047
31 0.768 -0.174
32 0.847 -0.129

这通常应该表明LSD和分支未命中之间存在很强的相关性，而Uop 缓存和分支未命中之间没有有意义的关系。

全面的

一般来说，我认为很明显，当在LSD之外执行的内部循环是导致分支未命中的原因，直到对于BHT条目的历史Iterations而言变得太大。为了保存解释的尖峰，我们看不到Branch Misses升高，但我们这样做了，我能说的唯一区别是LSD。N = [33, 39]N = [0, 32]

推荐阅读