На 33% меньше инструкций, на 17% меньше доступа к памяти, но в 4 раза быстрее?

Резюме

У меня есть два фрагмента кода на C ++, которые выполняют одинаковые вычисления. Код B действительно дает примерно на 33% меньше инструкций, примерно на 17% меньше доступа к памяти, чем код A, но выполняется в четыре раза быстрее (вместо двух). В чем будет причина? Более того, как мы сможем подтвердить утверждения, представленные вашими ответами?

В обоих кодах

• howmany is 20 000 000
• testees имеет 20000000 элементов, генерируемых случайным образом (mt19937) при запуске (перед этими фрагментами) для каждого из кода A и кода B.
• умножение обрабатывается одним доступом к памяти (как будет показано в ассемблерном коде позже)
• Оба кода были скомпилированы с флагом оптимизации -O1.

Какой-то код

код A — выполняется прибл. 95–110 мс

    GF2 sum {GF2(1)};
    auto a = system_clock::now();
    for(size_t i=0;i<howmany;i++){
        sum *= testees[i]; 
    }
    auto b = system_clock::now();

код B — выполняется прибл. От 25 до 30 мс

    GF2 sum1 {GF2(1)};
    GF2 sum2 {GF2(1)};
    GF2 sum3 {GF2(1)};
    GF2 sum4 {GF2(1)};
    auto aa = system_clock::now();
    for(size_t i=0;i<howmany;i+=4){
        sum1 *= testees[i];   // runs sum1.rep = multTable[sum1.rep][testees[i].rep]
        sum2 *= testees[i+1]; // GF2::rep is of type std::uint8_t
        sum3 *= testees[i+2]; // multTable is a std::uint8_t array of size 256 * 256; 64KB in total.
        sum4 *= testees[i+3];
    }
    sum1 = sum1*sum2*sum3*sum4;
    auto bb = system_clock::now();

testees — это std :: vector, заполненный 20 миллионами случайных экземпляров GF2. 5_3_betterbenchmark.cpp генерирует их случайным образом во время выполнения, поэтому коды A и B выполняются с идентичными testees.

код A, основной цикл (который выполняется 20M раз, что составляет 20M * 9 = 180M инструкций)

01 .L170:
02     movzbl  15(%rsp), %eax  # on 15(%rsp) is sum.rep -> mem access #1
03     salq    $8, %rax        # left shift sum.rep(in %rax) by 8 bits
04     addq    %rsi, %rax      # on %rsi is the address for multTable
05     movzbl  (%rdx), %ecx    # on (%rdx) is testees[i].rep -> mem access #2
06     movzbl  (%rax,%rcx), %eax  # (%rax,%rcx) is multTable[sum.rep][testees[i].rep] -> mem access #3
07     movb    %al, 15(%rsp)   # moves this to sum.rep -> mem access #4
08     addq    $1, %rdx        # i+=1 but in pointers
09     cmpq    %rdi, %rdx      # loop condition check
10     jne .L170  

код B, основной цикл (который выполняется 5 млн раз, что составляет всего 5 млн * 24 = 120 млн инструкций)

01 .L171:
02     movzbl  14(%rsp), %r8d   # sum1, -> mem access #1
03     salq    $8, %r8 
04     addq    %rdi, %r8  
05     movzbl  (%rsi), %r10d    # -> mem access #2
06     movzbl  (%r8,%r10), %r8d # -> mem access #3  
07     movb    %r8b, 14(%rsp)   # -> mem access #4
08     movzbl  %cl, %ecx        # sum2 is already in register for some reason
09     salq    $8, %rcx    
10     addq    %rdi, %rcx  
11     movzbl  1(%rsi), %r10d   # -> mem access #5
12     movzbl  (%rcx,%r10), %ecx# -> mem access #6  
13     movzbl  %dl, %edx        # sum3 is also already in register for some reason
14     salq    $8, %rdx    
15     addq    %rdi, %rdx  
16     movzbl  2(%rsi), %r10d   # -> mem access #7
17     movzbl  (%rdx,%r10), %edx# -> mem access #8   
18     movzbl  %al, %eax        # sum4 is also already in register for some reason
19     salq    $8, %rax    
20     addq    %rdi, %rax  
21     movzbl  3(%rsi), %r10d   # -> mem access #9
22     movzbl  (%rax,%r10), %eax# -> mem access #10  
23     addq    $4, %rsi    # i+=4 (in pointers)
24     cmpq    %r9, %rsi   # decide if we should terminate loop
25     jne .L171   

Гипотезы

Вот несколько гипотез, которые выдвинули я и мои коллеги после того, как погуглили и много раздумывали: однако я вряд ли в этом уверен.

• Claim: calls to std::chrono::system_clock() were misplaced by compiler optimizations
  • After a look at the whole assembly code we confirmed this was not the case
• Claim : code A is more prone to TLB misses when process switches happen and the TLB is wiped out (according to how Linux kernels are implemented)
  • However, the number of context switches during both runs were virtually the same, around only 6 in most cases (checked with sudo perf stat for both), and the number of context switches had little to no effect in measured time.
• Claim: Code B results in less cache misses
  • However, testees is accessed in an exactly identical order in both codes, and multTable is accessed 20M times in random order in both — which means the amount of cache misses in both codes should be about the same
  • Более того, поскольку к _16 _ / _ 17_ обращаются очень часто, любая разумная политика кеширования оставит их в кеше L1, что приведет к очень небольшому количеству промахов кеша при доступе к sum.rep.

Отредактировано после того, как вопрос был закрыт

Это в основном отчет после проверки того, что было предложено в комментариях.

некоторые пояснения

Пользователь Аки Суйконен в комментариях указал, что этот тест изначально предвзят, так как я, возможно, не предотвратил вмешательство GF2(0). На самом деле я предотвращал это с самого начала (более подробную информацию см. В моем комментарии ниже ). Я считаю, что мой вопрос был совершенно правильным, возможно, не считая того факта, что на него были ответы в другом месте на сайте.

Последствия

На самом деле мои вопросы были двумя вопросами в одном.

• Почему код B (в 4 раза) быстрее, чем код A
• Как я могу проверить ваше утверждение?

Единственный комментарий, касающийся второго вопроса, — это комментарий пользователя mattlangford. Мэттлангфорд посоветовал мне попробовать llvm-mca, отличный инструмент, который также позволяет я визуализирую исполнение (от отправки до выхода на пенсию) в виде временной шкалы. Однако только после того, как мне были представлены некоторые неудовлетворительные результаты, я заметил следующие предложения в руководстве:

• LSUnit не знает, когда может произойти пересылка от магазина к загрузке.
• LSUnit ничего не знает об иерархии кэша и типах памяти.
• LSUnit не знает, как идентифицировать операции сериализации и ограничения памяти.

Кроме того, результаты llvm-mca для кода A выглядят примерно так (используется команда llvm-mca (input) -iterations=200 -timeline -o 630_llvmmca.txt):

Timeline view:
                    0123456789          012345
Index     0123456789          0123456789

[0,0]     DeeeeeER  .    .    .    .    .    .   movzbl 14(%rsp), %eax
[0,1]     D=====eER .    .    .    .    .    .   shlq   $8, %rax
[0,2]     D======eER.    .    .    .    .    .   addq   %rsi, %rax
[0,3]     DeeeeeE--R.    .    .    .    .    .   movzbl (%rdx), %ecx
[0,4]     .D======eeeeeER.    .    .    .    .   movzbl (%rax,%rcx), %eax
[0,5]     .D===========eER    .    .    .    .   movb   %al, 14(%rsp)
[0,6]     .DeE-----------R    .    .    .    .   addq   $1, %rdx
[0,7]     .D=eE----------R    .    .    .    .   cmpq   %rdi, %rdx
[0,8]     . D=eE---------R    .    .    .    .   jne    .L171
[1,0]     . DeeeeeE------R    .    .    .    .   movzbl 14(%rsp), %eax
[1,1]     . D=====eE-----R    .    .    .    .   shlq   $8, %rax
[1,2]     . D======eE----R    .    .    .    .   addq   %rsi, %rax
[1,3]     .  DeeeeeE-----R    .    .    .    .   movzbl (%rdx), %ecx
[1,4]     .  D======eeeeeER   .    .    .    .   movzbl (%rax,%rcx), %eax
[1,5]     .  D===========eER  .    .    .    .   movb   %al, 14(%rsp)
[1,6]     .  DeE-----------R  .    .    .    .   addq   $1, %rdx
[1,7]     .   DeE----------R  .    .    .    .   cmpq   %rdi, %rdx
[1,8]     .   D=eE---------R  .    .    .    .   jne    .L171
[2,0]     .   DeeeeeE------R  .    .    .    .   movzbl 14(%rsp), %eax
[2,1]     .   D=====eE-----R  .    .    .    .   shlq   $8, %rax
[2,2]     .    D=====eE----R  .    .    .    .   addq   %rsi, %rax
[2,3]     .    DeeeeeE-----R  .    .    .    .   movzbl (%rdx), %ecx

и так далее. По крайней мере, согласно этой диаграмме, четыре инструкции уже отправляются параллельно. Я также проверил вывод llvm-mca для кода B:

[0,0]     DeeeeeER  .    .    .    .    .    .    .    .    .    .    .    .    .    .   .   movzbl     14(%rsp), %r8d
[0,1]     D=====eER .    .    .    .    .    .    .    .    .    .    .    .    .    .   .   shlq       $8, %r8
[0,2]     D======eER.    .    .    .    .    .    .    .    .    .    .    .    .    .   .   addq       %rdi, %r8
[0,3]     DeeeeeE--R.    .    .    .    .    .    .    .    .    .    .    .    .    .   .   movzbl     (%rsi), %r10d
[0,4]     .D======eeeeeER.    .    .    .    .    .    .    .    .    .    .    .    .   .   movzbl     (%r8,%r10), %r8d
[0,5]     .D===========eER    .    .    .    .    .    .    .    .    .    .    .    .   .   movb       %r8b, 14(%rsp)
[0,6]     .DeE-----------R    .    .    .    .    .    .    .    .    .    .    .    .   .   movzbl     %cl, %ecx
[0,7]     .D=eE----------R    .    .    .    .    .    .    .    .    .    .    .    .   .   shlq       $8, %rcx
[0,8]     . D=eE---------R    .    .    .    .    .    .    .    .    .    .    .    .   .   addq       %rdi, %rcx
[0,9]     . DeeeeeE------R    .    .    .    .    .    .    .    .    .    .    .    .   .   movzbl     1(%rsi), %r10d
[0,10]    . D=====eeeeeE-R    .    .    .    .    .    .    .    .    .    .    .    .   .   movzbl     (%rcx,%r10), %ecx
[0,11]    . DeE----------R    .    .    .    .    .    .    .    .    .    .    .    .   .   movzbl     %dl, %edx
[0,12]    .  DeE---------R    .    .    .    .    .    .    .    .    .    .    .    .   .   shlq       $8, %rdx
[0,13]    .  D=eE--------R    .    .    .    .    .    .    .    .    .    .    .    .   .   addq       %rdi, %rdx
[0,14]    .  DeeeeeE-----R    .    .    .    .    .    .    .    .    .    .    .    .   .   movzbl     2(%rsi), %r10d
[0,15]    .  D=====eeeeeER    .    .    .    .    .    .    .    .    .    .    .    .   .   movzbl     (%rdx,%r10), %edx
[0,16]    .   DeE--------R    .    .    .    .    .    .    .    .    .    .    .    .   .   movzbl     %al, %eax
[0,17]    .   D=eE-------R    .    .    .    .    .    .    .    .    .    .    .    .   .   shlq       $8, %rax
[0,18]    .   D==eE------R    .    .    .    .    .    .    .    .    .    .    .    .   .   addq       %rdi, %rax
[0,19]    .   DeeeeeE----R    .    .    .    .    .    .    .    .    .    .    .    .   .   movzbl     3(%rsi), %r10d
[0,20]    .    D====eeeeeER   .    .    .    .    .    .    .    .    .    .    .    .   .   movzbl     (%rax,%r10), %eax
[0,21]    .    DeE--------R   .    .    .    .    .    .    .    .    .    .    .    .   .   addq       $4, %rsi
[0,22]    .    D=eE-------R   .    .    .    .    .    .    .    .    .    .    .    .   .   cmpq       %r9, %rsi
[0,23]    .    D==eE------R   .    .    .    .    .    .    .    .    .    .    .    .   .   jne        .L171
[1,0]     .    .DeeeeeE---R   .    .    .    .    .    .    .    .    .    .    .    .   .   movzbl     14(%rsp), %r8d
[1,1]     .    .D=====eE--R   .    .    .    .    .    .    .    .    .    .    .    .   .   shlq       $8, %r8
[1,2]     .    .D======eE-R   .    .    .    .    .    .    .    .    .    .    .    .   .   addq       %rdi, %r8
[1,3]     .    .DeeeeeE---R   .    .    .    .    .    .    .    .    .    .    .    .   .   movzbl     (%rsi), %r10d
[1,4]     .    . D======eeeeeER    .    .    .    .    .    .    .    .    .    .    .   .   movzbl     (%r8,%r10), %r8d
[1,5]     .    . D===========eER   .    .    .    .    .    .    .    .    .    .    .   .   movb       %r8b, 14(%rsp)
[1,6]     .    . D=====eE------R   .    .    .    .    .    .    .    .    .    .    .   .   movzbl     %cl, %ecx

Откровенно говоря, ничем не отличается от кода A, за исключением того, что теперь количество операций записи в память в 4 раза меньше, что на самом деле не имеет значения, потому что любая разумная политика кеширования должна оставлять все, что находится в 14(%rbx), в кеше L1. (насколько мне известно, все Intel-совместимые процессоры за последние несколько десятилетий использовали кеши обратной записи)

Больше тестов

Пользователь Маргарет Блум утверждала, что

Если вы будете разворачивать все больше и больше, вы будете видеть все меньше и меньше прироста производительности.

Это утверждение подтвердилось. Я развернул код B еще в 2 раза и увидел еще 2-кратное увеличение скорости. И после этого у меня не получилось прибавить в ускорении.

Код C

GF2 sum1 {GF2(1)};
    GF2 sum2 {GF2(1)};
    GF2 sum3 {GF2(1)};
    GF2 sum4 {GF2(1)};
    GF2 sum5 {GF2(1)};
    GF2 sum6 {GF2(1)};
    GF2 sum7 {GF2(1)};
    GF2 sum8 {GF2(1)};


    auto aa = system_clock::now();
    for(size_t i=0;i<howmany;i+=8){
        sum1 *= testees[i];
        sum2 *= testees[i+1];
        sum3 *= testees[i+2];
        sum4 *= testees[i+3];
        sum5 *= testees[i+4];
        sum6 *= testees[i+5];
        sum7 *= testees[i+6];
        sum8 *= testees[i+7];

    }

Код C — сборки для основного цикла

  1532     movzbl  14(%rsp), %ebp
  1533     salq    $8, %rbp
  1534     addq    %r11, %rbp
  1535     movzbl  (%rax), %r13d
  1536     movzbl  0(%rbp,%r13), %ebp
  1537     movb    %bpl, 14(%rsp)
  1538     movzbl  %r10b, %r10d
  1539     salq    $8, %r10
  1540     addq    %r11, %r10
  1541     movzbl  1(%rax), %r13d
  1542     movzbl  (%r10,%r13), %r10d
  1543     movzbl  %r9b, %r9d
  1544     salq    $8, %r9
  1545     addq    %r11, %r9
  1546     movzbl  2(%rax), %r13d
  1547     movzbl  (%r9,%r13), %r9d
  1548     movzbl  %r8b, %r8d
  1549     salq    $8, %r8
  1550     addq    %r11, %r8
  1551     movzbl  3(%rax), %r13d
  1552     movzbl  (%r8,%r13), %r8d
  1553     movzbl  %dil, %edi
  1554     salq    $8, %rdi
  1555     addq    %r11, %rdi
  1556     movzbl  4(%rax), %r13d
  1557     movzbl  (%rdi,%r13), %edi
  1558     movzbl  %sil, %esi
  1559     salq    $8, %rsi
  1560     addq    %r11, %rsi
  1561     movzbl  5(%rax), %r13d
  1562     movzbl  (%rsi,%r13), %esi
  1563     movzbl  %cl, %ecx
  1564     salq    $8, %rcx
  1565     addq    %r11, %rcx
  1566     movzbl  6(%rax), %r13d
  1567     movzbl  (%rcx,%r13), %ecx
  1568     movzbl  %dl, %edx
  1569     salq    $8, %rdx
  1570     addq    %r11, %rdx
  1571     movzbl  7(%rax), %r13d
  1572     movzbl  (%rdx,%r13), %edx
  1573     addq    $8, %rax
  1574     cmpq    %r12, %rax
  1575     jne .L171

Предварительное заключение и некоторые проблемы, которые у меня есть с ним

Собрав всю информацию в одном месте, я могу сделать такой вывод.

• Согласно llvm-mca, можно отправлять четыре инструкции в каждом цикле, даже для кода A — при условии, что задержка памяти на самом деле такая же, как показано на диаграммах выше.
• Однако любая информация о задержке памяти, предоставленная llvm-mca, может быть в высшей степени неверной, поскольку он не знает структуры кеша или типов памяти, как указано выше.
• Теперь, когда на самом деле рассматривается иерархия памяти, прогнозы задержки, сделанные llvm-mca, будут серьезно неверными для movzbl, которые извлекаются из multTable[sum.rep][other.rep] — все остальные должны быть в кеше, если мой кеш в порядке. Эти movzbls во многих случаях приводят к пропуску кэша — и могут потребоваться сотни циклов.
• code B удаляет некоторые зависимости — иначе говоря, опасности, записывая цикл сборки code A четыре раза и переименовывая некоторые регистры / памяти.
• Если я попытаюсь нарисовать диаграмму, подобную диаграммам, созданным llvm-mca выше, но на этот раз с учетом промахов в кеше, я должен получить приблизительную оценку общего времени работы …?

Я все еще озадачен

• Если бы мой процессор мог отправлять только четыре инструкции за раз, что могло бы объяснить 8-кратное ускорение кода C по сравнению с кодом A?

Планы на будущее

• Теперь это явно становится вопросом, непригодным для stackoverflow — я задам другой вопрос в другом месте — или поищу его подробнее.

Большое спасибо за ценные советы!

Вероятно, это связано с нарушением порядка выполнения. В вашем варианте B четыре дополнения в цикле могут оцениваться четырьмя исполнительными модулями параллельно (в качестве альтернативы может использоваться векторизация). В варианте А это невозможно. Таким образом, как вы заметили, общая задержка уменьшилась в 4 раза.   —  person Jayeon Yi    schedule 13.05.2021

Вы компилируете с оптимизацией или без нее?   —  person Jayeon Yi    schedule 13.05.2021

@SamVarshavchik: Как указано в вопросе, OP использует -O1 в обоих случаях.   —  person Jayeon Yi    schedule 13.05.2021

@fuz Насколько мне известно, опция -O3 поддерживает развертывание циклов, как вы и предложили, но даже с O3 нет заметного снижения скорости выполнения для кода A.   —  person Jayeon Yi    schedule 13.05.2021

Развертывая цикл, вы получаете девять (если я правильно оценил) цепочек зависимостей, и ЦП может использовать больше исполнительных единиц через отправку OoO. Он по-прежнему может выполнять только две загрузки и одно (или два) сохранения за цикл, но существует множество цепочек зависимостей, которые поглощают любой пузырь. Нет причин ожидать, что код будет только вдвое быстрее (обратите внимание, что вы не можете сделать 33% + 17%, поскольку эти наборы не пересекаются). Если вы будете разворачивать все больше и больше, вы будете видеть все меньше и меньше прироста производительности.   —  person Jayeon Yi    schedule 13.05.2021

Изменяются ли числа, когда вы сначала запускаете A, а затем B, или сначала B, а затем A? Это отдельные исполняемые файлы или оба работают одновременно?   —  person Jayeon Yi    schedule 13.05.2021

@Olaf Dietsche Я пробовал все три из того, что вы сказали — отдельные исполняемые файлы, A, затем B (те же числа), B, затем A (те же числа)   —  person Jayeon Yi    schedule 13.05.2021

@JayeonYi Я не уверен, насколько важна развёртка.   —  person Jayeon Yi    schedule 13.05.2021

Этот тест является необъективным — он не измеряет общую скорость умножения GF2, поскольку 0 * A = 0. Как только обнаруживается случайное значение 0, весь доступ к памяти для этой конкретной цепочки зависимостей концентрируется в области размером 256 байт. (И есть более эффективные способы вычислить произведение 20000000 элементов в GF2 — начиная с гистограммы …)   —  person Jayeon Yi    schedule 13.05.2021

@AkiSuihkonen Вы правы: однако я хотел бы отметить, что я сделал все возможное, чтобы не включать 0 в 20 000 000 чисел. Вы правы насчет гистограммы, но я просто хотел проверить, насколько быстро будет работать оператор * =. Полный код доступен здесь: github.com/stet -stet / many-gf2n-cpp / blob / main /   —  person Jayeon Yi    schedule 13.05.2021

@fuz Моя ошибка — я перепутал переименование реестра с кодом B.   —  person Jayeon Yi    schedule 13.05.2021

В LLVM есть отличный инструмент, который позволяет вам видеть выполнение в виде временной шкалы, на которую стоит обратить внимание: llvm.org/docs/CommandGuide/llvm-mca.html Разница почти наверняка связана с тем, что вы можете делать 4 умножения параллельно и делать 1/4 числа прыжков. Кроме того, вот микробенчмарк, подтверждающий ваши выводы: quick-bench.com/q/1aevPJXBLrZ3JJ77aMJa   —  person Jayeon Yi    schedule 13.05.2021

Почему Mulss занимает всего 3 цикла на Haswell, в отличие от таблиц инструкций Агнера? (Развертывание циклов FP с несколькими аккумуляторами) — развертывание циклов FP с несколькими аккумуляторами, чтобы скрыть задержку и ограничить пропускную способность. В вашем случае это store / reload (store forwarding) ~ 5 циклов задержки, потому что что-то (возможно, псевдоним) мешает компилятору хранить sum в регистре. Или, возможно, потому, что вы использовали только -O1   —  person Jayeon Yi    schedule 13.05.2021

Re: задержка пересылки магазина: Добавление избыточного назначения ускоряет код при компиляции без оптимизации   —  person Jayeon Yi    schedule 13.05.2021

Также: Развертывание цикла для достижения максимальной пропускной способности с Ivy Bridge и Haswell по-прежнему связано с задержкой FP, но применимы те же концепции.   —  person Jayeon Yi    schedule 13.05.2021

в общем, меньше инструкций не означает быстрее, равно как и меньшее количество обращений к памяти, можно было бы надеяться, что если у вас будет меньше и того, и другого, это будет быстрее, но это небезопасно предполагать. Я мог бы иметь на 100 инструкций меньше и один дополнительный доступ к памяти, и производительность была бы минимальной, если бы для этого доступа пришлось потратить слишком много времени.   —  person Jayeon Yi    schedule 16.05.2021

Фактическая критическая проблема с использованием LLVM-MCA для этого заключается в том, что не знает, когда может произойти переадресация от магазина к загрузке. — когда сохранение / перезагрузка является частью цепочки зависимостей с переносом цикла (как в вашем case), LLVM-MCA считает, что нагрузка на самом деле независима! Таким образом, он имитирует гораздо больший параллелизм на уровне инструкций, чем это реально возможно. Как указывает Сколько циклов ЦП требуется для каждой инструкции сборки? (и одного из связанных дубликатов), анализируя цепочки зависимостей ( вручную или с помощью таких инструментов, как LLVM-MCA) является отправной точкой для статического анализа производительности.   —  person Jayeon Yi    schedule 18.05.2021

Ваши переменные sum1..8 будут оставаться горячими в кэше L1d; моделирование иерархии кеша — не проблема. Важное значение имеет моделирование переадресации магазина (и обнаружение зависимости). Некоторые циклы делают a[i] += 1; или что-то в этом роде, поэтому инструкции загрузки / сохранения в одной итерации используют адрес, отличный от адреса предыдущей итерации. Если бы вы могли убедить компилятор не проливать / не перезагружать ваши переменные, это сократило бы задержку, которую вы должны скрывать, поэтому вам нужно было бы меньше разворачивать.   —  person Jayeon Yi    schedule 18.05.2021