Умножение с константой - imul или shl-add-combination

Этот вопрос о том, как мы умножаем целое число на константу. Итак, давайте рассмотрим простую функцию:

int f(int x) {
    return 10*x;
}

Как лучше всего оптимизировать эту функцию, особенно когда она встроена в вызывающую программу?

Подход 1 (разрабатывается большинством оптимизирующих компиляторов (например, на Godbolt))

    lea    (%rdi,%rdi,4), %eax
    add    %eax, %eax

Подход 2 (созданный с clang3.6 и более ранними версиями, с -O3)

    imul   $10, %edi, %eax

Подход 3 (созданный с помощью g++6.2 без оптимизации, без сохранения/перезагрузки)

    mov    %edi, %eax
    sal    $2, %eax
    add    %edi, %eax
    add    %eax, %eax

Какая версия самая быстрая и почему? В первую очередь интересует Intel Haswell.


x86 assembly micro-optimization
person overseas    schedule 12.11.2016    source источник
comment
Производительность неоптимизированных сборок C++ (и, следовательно, производительность произведенной сборки) совершенно бессмысленна. Скомпилируйте с -O2 или -O3, чтобы получить осмысленный вывод.   -  person Some programmer dude    schedule 12.11.2016
comment
Для downvoters я добавил комментарий.   -  person Baum mit Augen    schedule 12.11.2016
comment
Я знаю математику и алгоритмы, а не чипы. Логично, что сдвиг и сложение будут быстрее, чем любое умножение, но пробовали ли вы синхронизировать их?   -  person overseas    schedule 12.11.2016
comment
@KennyOstrom Смотрите мой ответ ниже   -  person Kenny Ostrom    schedule 12.11.2016
comment
вывод clang все еще от _1_. И вместо _2_ просто напишите функцию, которая принимает аргумент и возвращает значение, чтобы нечего было оптимизировать. _3_: godbolt.org/g/uThcu7. Затем gcc, clang и icc (с _4_) выбирают версию ADD+LEA с задержкой 2 мкп и задержкой 2c вместо версии _5_ с задержкой 1 мкп и 3c. (clang3.6 и более ранние версии используют только один IMUL, но позже clang был изменен на версию с меньшей задержкой, которая требует больше мопов, по крайней мере, в этом случае. Я сомневаюсь, что clang моделирует интерфейс ЦП для выбора lat против tput).   -  person overseas    schedule 12.11.2016
comment
Как оказалось, этот код даже намного менее эффективен, чем использование imul, Вы имеете в виду, что при компиляции с -O0 переменные сохраняются/перезагружаются в память после каждого оператора? Да поди разберись. Здесь есть реальный вопрос, но он похоронен под кучей ложной чепухи из-за использования неоптимизированного вывода компилятора.   -  person Peter Cordes    schedule 13.11.2016
comment
Да, верно, но вы неправильно поняли мой второй вопрос. Дело не в производительности. У нас есть три версии: imul, плохо работающая сложная смена, и быстрая и не очень легкая для чтения версия lea. Я понимаю, когда компилятор использует первую версию, и я понимаю, когда компилятор будет использовать третью версию. Но почему они должны выбирать версию, которая медленная и трудная для чтения?   -  person Peter Cordes    schedule 13.11.2016
comment
И да, вывод clang связан с O0, потому что он находится в разделе, где я говорю об O0. Использую ли я volatile или другую функцию, не должно иметь значения, потому что в моем реальном тесте я вычисляю тысячи раз, и наконец (и только тогда) я присваиваю ее volatile переменной. Так что вообще не важно, лишь бы я получал тот эффект, который хочу (а я всегда смотрел на сборку). Позже посмотрю другие комментарии ниже.   -  person overseas    schedule 13.11.2016
comment
Ваше обновление было улучшением, но по-прежнему имело некоторые потраченные впустую инструкции MOV, что наиболее важно в версии LEA, но gcc6.2 не имеет больше инструкций MOV, чем необходимо в версии -O0. Если мы говорим о кандидате на звание самого быстрого, очевидно, нам не нужны дополнительные потраченные впустую MOV. Исправил это для вас и связал с Godbolt, откуда взялся ассемблер. Теперь все это допустимые функции с аргументом в EDI и результатом в EAX, просто без инструкции RET, потому что мы говорим о встраивании без накладных расходов на вызов функции.   -  person overseas    schedule 13.11.2016
comment
Спасибо. Я добавил версии ниже с новыми данными. Добавлю ссылку на godbolt через минуту.   -  person Peter Cordes    schedule 13.11.2016
comment
Спасибо, есть ли какой-нибудь ресурс, предоставляющий номера для этого?   -  person overseas    schedule 13.11.2016

Ответы (3)


arrow_upward
6
arrow_downward

Согласно тестированию Agner Fog (и другим материалам, таким как AIDA64), процессоры Intel, начиная с Core2, имели imul r32,r32, imm задержку 3c, пропускная способность один на 1c. Начиная с Nehalem, 64-битное умножение также быстрое. (Агнер говорит, что Nehalem imul r64,r64,imm медленнее (пропускная способность 2c), чем imul r64,r64, но это не соответствует другим результатам. ">Instlatx64 говорит 1c.)

Процессоры AMD до Ryzen медленнее, например. Steamroller имеет lat=4c tput=one per 2c для 32-битного умножения. Для 64-битного умножения lat=6c tput=one per 4c. AMD Ryzen имеет такую ​​же превосходную производительность умножения, как и Intel.

LEA с 2 компонентами в режиме адресации (база + индекс, но без постоянного смещения) работает с задержкой 1c на всех процессорах Intel1, за исключением, возможно, Atom, где LEA работает на другом этапе конвейера ( в реальном AGU, а не в ALU) и требует готовности ввода на 4c раньше, чем обычная инструкция ALU. И наоборот, его ввод готов раньше, поэтому я думаю, что ADD может использовать результат в том же цикле. (Я не тестировал это, и у меня нет Atom HW.)

В семействе Intel SnB простой LEA может работать на портах 1 или 5, поэтому его пропускная способность вдвое выше, чем у IMUL.

ADD может работать на любом порту ALU на любом процессоре. HSW представила 4-й порт ALU (по сравнению с IvyBridge), поэтому он может поддерживать 4 операции ALU за такт (теоретически).

Таким образом, версия LEA+ADD имеет задержку 2c на большинстве процессоров x86, а на Haswell может выполнять два умножения за такт.

Сноска 1: на AMD (включая Zen/Zen2) масштабируемый индекс делает LEA медленным (задержка в 2 цикла и работает на меньшем количестве портов). например lea r32, [r64+r64*2] измерено при задержке в 2 цикла на Zen2 по сравнению с 1 циклом на Skylake. (Агнер Фог также упоминает, что lea r32, [r64...] медленнее на AMD, но это могло быть только эффектом бульдозера; это не очевидно в https://uops.info/%27s результаты для Zen / Zen2.)

Но если умножение является лишь небольшой частью большого окружающего цикла, который ограничивает общую пропускную способность uop, а не задержку или пропускную способность умножения, версия IMUL лучше.

Если ваша константа умножения слишком велика для двух LEA или SHL+LEA, то вам, вероятно, лучше использовать IMUL, особенно при настройке в первую очередь для процессоров Intel с их чрезвычайно высокопроизводительными целочисленными множителями.

SHL+LEA или SHL+SUB могут быть полезны, например. умножить на 63. (из Godbolt: gcc6.2 -O3 -march=haswell)

    movl    %edi, %eax
    sall    $6, %eax
    subl    %edi, %eax

На Haswell, где MOV работает с нулевой задержкой, задержка составляет всего 2c. Но это 3 объединенных доменных операции против 1 для imull $63, %edi, %eax. Таким образом, в конвейере больше мопов, что снижает то, насколько далеко ЦП может видеть выполнение не по порядку. Это также увеличивает нагрузку на кэш uop и I-кэш L1, чтобы компилятор последовательно выбирал эту стратегию, потому что это больше байтов инструкций.

На процессорах до IvyBridge это строго хуже, чем IMUL, если что-то еще не конкурирует за порт 1, потому что это задержка 3c (MOV находится в цепочке зависимостей критического пути и имеет задержку 1c).

Как обычно, ни один из фрагментов ассемблера нельзя назвать оптимальным для всех ситуаций. Это зависит от того, что является узким местом в окружающем коде: задержка, пропускная способность или uops.

Ответ будет другим для одного и того же окружающего кода на разных микроархитектурах.

person Peter Cordes    schedule 13.11.2016

arrow_upward
2
arrow_downward

Я предполагаю, что последовательность сдвига и добавления была быстрее, чем imul; это верно для многих версий чипов x86. Я не знаю, верно ли это для Haswell; тем не менее, выполнение imul за 2 тактовых цикла требует значительных ресурсов чипа, если это вообще выполнимо.

Я немного удивлен, что это не привело к еще более быстрой последовательности:

 lea   y, [2*y]
 lea   y, [5*y]

[OP редактирует свой ответ, показывает оптимизированный код, создающий ADD, а затем LEA. Да, это лучший ответ; ADD r,r меньше по пространству, чем lea ..[2*y], поэтому результирующий код меньше и имеет ту же скорость]

person Ira Baxter    schedule 12.11.2016
comment
www.agnesfog.org — широко уважаемый ресурс для понимания того, как оптимизировать код x86. Фактическое количество циклов для современных ЦП трудно найти в справочных документах; туман, кажется, измеряет все и, как правило, довольно актуален. - person overseas; 12.11.2016
comment
Этот веб-сайт не существует. Вы, наверное, имеете в виду документы на agner.org? - person Ira Baxter; 12.11.2016
comment
stackoverflow.com/questions/6120207/imul-or-shift-instruction упоминает en.wikipedia.org/wiki/Strength_reduction - person overseas; 12.11.2016
comment
В целом это кажется быстрее, за исключением того, что вы можете использовать ILP (см. измерения ниже). Буду рад, если вы проверите, имеет ли это смысл, или мои сборки плохо оптимизированы. - person Kenny Ostrom; 12.11.2016
comment
ILP должен хорошо воспринимать последовательности добавления/сдвига/освобождения, особенно если они находятся в разных регистрах. - person overseas; 12.11.2016
comment
Регистры назначаются автоматически g++. С ILP и без развертывания цикла я получаю следующий код для версии imul (V1) pastebin.com/r3edQPXD, и следующий код для версии add/shift/lea (V3): pastebin.com/vVB7JeKq. По крайней мере, результаты для imul ожидаются, поскольку в руководстве по оптимизации Intel упоминается задержка 3-4 цикла и пропускная способность 1 цикл. - person Ira Baxter; 12.11.2016
comment
@Ira: Haswell imul всегда имеет задержку 3c для версии с несколькими операндами, даже для 64-битного размера операнда. (В семействе SnB нет 2c latency uops, чтобы упростить/улучшить планирование, даже если они хотели потратить столько транзисторов на чрезвычайно низкий множитель задержки. Вот почему 3-компонентный _1_ имеет задержку 3c, а не 2, поскольку они не Я не хочу реализовывать оба дополнения в 1с, как это сделал core2). Кстати, выполнение не по порядку означает, что отдельные регистры не имеют значения: опасности WAW и WAR не имеют значения благодаря переименованию регистров. Только истинные зависимости (чтение-после-записи) имеют значение. - person overseas; 12.11.2016
comment
lea eax, [rdi + rdi*2 + 1] циклов на IMUL, потому что вы измеряете эталонные циклы, а не тактовые циклы ядра, и у вас включен режим Turbo. В Haswell _2_ составляет 1 мкп (для порта 1) с задержкой 3 с, по одному на пропускную способность 1 с. (Источник: agner.org/optimize). 2-компонентный LEA составляет 1 мооп для порта 1 или 5, с задержкой 1c и пропускной способностью 0,5c. Измеряйте с помощью счетчиков производительности (например, _3_) для получения лучших результатов. - person Peter Cordes; 13.11.2016

arrow_upward
1
arrow_downward

Я просто сделал некоторые измерения. Мы имитируем следующий код на ассемблере, используя инструкции, данные в вопросе:

    for (unsigned i = 0; i < (1 << 30); ++i) {
        r1 = r2 * 10;
        r2 = r1 * 10;
    }

Возможно, для временных файлов нужны какие-то дополнительные регистры.

Примечание. Все измерения даны в циклах на одно умножение.

Мы используем компилятор clang с параметром -O3, потому что там мы получаем именно ту сборку, которую хотим (gcc иногда добавляет очень мало MOV внутри цикла). У нас есть два параметра: u = #unrolled loops и i = #ilp. Например, для u=4, i=2 получаем следующее:

  401d5b:   0f a2                   cpuid  
  401d5d:   0f 31                   rdtsc  
  401d5f:   89 d6                   mov    %edx,%esi
  401d61:   89 c7                   mov    %eax,%edi
  401d63:   41 89 f0                mov    %esi,%r8d
  401d66:   89 f8                   mov    %edi,%eax
  401d68:   b9 00 00 20 00          mov    $0x200000,%ecx
  401d6d:   0f 1f 00                nopl   (%rax)
  401d70:   6b d5 0a                imul   $0xa,%ebp,%edx
  401d73:   41 6b f7 0a             imul   $0xa,%r15d,%esi
  401d77:   6b fa 0a                imul   $0xa,%edx,%edi
  401d7a:   6b d6 0a                imul   $0xa,%esi,%edx
  401d7d:   6b f7 0a                imul   $0xa,%edi,%esi
  401d80:   6b fa 0a                imul   $0xa,%edx,%edi
  401d83:   6b d6 0a                imul   $0xa,%esi,%edx
  401d86:   6b f7 0a                imul   $0xa,%edi,%esi
  401d89:   6b fa 0a                imul   $0xa,%edx,%edi
  401d8c:   6b d6 0a                imul   $0xa,%esi,%edx
  401d8f:   6b f7 0a                imul   $0xa,%edi,%esi
  401d92:   6b fa 0a                imul   $0xa,%edx,%edi
  401d95:   44 6b e6 0a             imul   $0xa,%esi,%r12d
  401d99:   44 6b ef 0a             imul   $0xa,%edi,%r13d
  401d9d:   41 6b ec 0a             imul   $0xa,%r12d,%ebp
  401da1:   45 6b fd 0a             imul   $0xa,%r13d,%r15d
  401da5:   ff c9                   dec    %ecx
  401da7:   75 c7                   jne    401d70 <_Z7measureIN5timer5rtdscE2V1Li16777216ELi4ELi2EEvv+0x130>
  401da9:   49 c1 e0 20             shl    $0x20,%r8
  401dad:   49 09 c0                or     %rax,%r8
  401db0:   0f 01 f9                rdtscp

Обратите внимание, что это не 8, а 16 инструкций imul, потому что это r2 = r1 * 10; г1 = г2 * 10; Я опубликую только основной цикл, т.е.

  401d70:   6b d5 0a                imul   $0xa,%ebp,%edx
  401d73:   41 6b f7 0a             imul   $0xa,%r15d,%esi
  401d77:   6b fa 0a                imul   $0xa,%edx,%edi
  401d7a:   6b d6 0a                imul   $0xa,%esi,%edx
  401d7d:   6b f7 0a                imul   $0xa,%edi,%esi
  401d80:   6b fa 0a                imul   $0xa,%edx,%edi
  401d83:   6b d6 0a                imul   $0xa,%esi,%edx
  401d86:   6b f7 0a                imul   $0xa,%edi,%esi
  401d89:   6b fa 0a                imul   $0xa,%edx,%edi
  401d8c:   6b d6 0a                imul   $0xa,%esi,%edx
  401d8f:   6b f7 0a                imul   $0xa,%edi,%esi
  401d92:   6b fa 0a                imul   $0xa,%edx,%edi
  401d95:   44 6b e6 0a             imul   $0xa,%esi,%r12d
  401d99:   44 6b ef 0a             imul   $0xa,%edi,%r13d
  401d9d:   41 6b ec 0a             imul   $0xa,%r12d,%ebp
  401da1:   45 6b fd 0a             imul   $0xa,%r13d,%r15d
  401da5:   ff c9                   dec    %ecx
  401da7:   75 c7                   jne    401d70 <_Z7measureIN5timer5rtdscE2V1Li16777216ELi4ELi2EEvv+0x130>

Вместо rtdsc мы используем perf (PERF_COUNT_HW_REF_CPU_CYCLES = «циклы ссылки» и PERF_COUNT_HW_CPU_CYCLES = «циклы процессора»).

Фиксируем u = 16 и варьируем i = {1, 2, 4, 8, 16, 32}. Мы получили

name    uroll ilp   ref cyclescpu cyclesp0      p1      p2      p3      p4      p5      p6      p7      
V1      16    1        2.723   3.006   0.000   1.000   0.000   0.000   0.000   0.000   0.031   0.000
V1      16    2        1.349   1.502   0.000   1.000   0.000   0.000   0.000   0.000   0.016   0.000
V1      16    4        0.902   1.002   0.000   1.000   0.000   0.000   0.000   0.000   0.008   0.000
V1      16    8        0.899   1.001   0.000   1.000   0.004   0.006   0.008   0.002   0.006   0.002
V1      16    16       0.898   1.001   0.000   1.000   0.193   0.218   0.279   0.001   0.003   0.134
V1      16    32       0.926   1.008   0.000   1.004   0.453   0.490   0.642   0.001   0.002   0.322

Это имеет смысл. Циклы ссылок можно игнорировать.

Столбцы справа показывают количество микроопераций на исполнительных портах. У нас есть одна инструкция на p1 (разумеется, имуль) и на p6 у нас есть декремент (1/16 в первом случае). Позже мы также можем увидеть, что мы получаем другие микрооперации из-за сильного давления на регистр.

Хорошо, давайте перейдем ко второй версии, которая сейчас:

  402270:   89 ea                   mov    %ebp,%edx
  402272:   c1 e2 02                shl    $0x2,%edx
  402275:   01 ea                   add    %ebp,%edx
  402277:   01 d2                   add    %edx,%edx
  402279:   44 89 fe                mov    %r15d,%esi
  40227c:   c1 e6 02                shl    $0x2,%esi
  40227f:   44 01 fe                add    %r15d,%esi
  402282:   01 f6                   add    %esi,%esi
  402284:   89 d7                   mov    %edx,%edi
  402286:   c1 e7 02                shl    $0x2,%edi
  402289:   01 d7                   add    %edx,%edi
  40228b:   01 ff                   add    %edi,%edi
  40228d:   89 f2                   mov    %esi,%edx
  40228f:   c1 e2 02                shl    $0x2,%edx
  402292:   01 f2                   add    %esi,%edx
  402294:   01 d2                   add    %edx,%edx
  402296:   89 fe                   mov    %edi,%esi
  402298:   c1 e6 02                shl    $0x2,%esi
  40229b:   01 fe                   add    %edi,%esi
  40229d:   01 f6                   add    %esi,%esi
  40229f:   89 d7                   mov    %edx,%edi
  4022a1:   c1 e7 02                shl    $0x2,%edi
  4022a4:   01 d7                   add    %edx,%edi
  4022a6:   01 ff                   add    %edi,%edi
  4022a8:   89 f2                   mov    %esi,%edx
  4022aa:   c1 e2 02                shl    $0x2,%edx
  4022ad:   01 f2                   add    %esi,%edx
  4022af:   01 d2                   add    %edx,%edx
  4022b1:   89 fe                   mov    %edi,%esi
  4022b3:   c1 e6 02                shl    $0x2,%esi
  4022b6:   01 fe                   add    %edi,%esi
  4022b8:   01 f6                   add    %esi,%esi
  4022ba:   89 d7                   mov    %edx,%edi
  4022bc:   c1 e7 02                shl    $0x2,%edi
  4022bf:   01 d7                   add    %edx,%edi
  4022c1:   01 ff                   add    %edi,%edi
  4022c3:   89 f2                   mov    %esi,%edx
  4022c5:   c1 e2 02                shl    $0x2,%edx
  4022c8:   01 f2                   add    %esi,%edx
  4022ca:   01 d2                   add    %edx,%edx
  4022cc:   89 fe                   mov    %edi,%esi
  4022ce:   c1 e6 02                shl    $0x2,%esi
  4022d1:   01 fe                   add    %edi,%esi
  4022d3:   01 f6                   add    %esi,%esi
  4022d5:   89 d7                   mov    %edx,%edi
  4022d7:   c1 e7 02                shl    $0x2,%edi
  4022da:   01 d7                   add    %edx,%edi
  4022dc:   01 ff                   add    %edi,%edi
  4022de:   89 f2                   mov    %esi,%edx
  4022e0:   c1 e2 02                shl    $0x2,%edx
  4022e3:   01 f2                   add    %esi,%edx
  4022e5:   01 d2                   add    %edx,%edx
  4022e7:   89 fe                   mov    %edi,%esi
  4022e9:   c1 e6 02                shl    $0x2,%esi
  4022ec:   01 fe                   add    %edi,%esi
  4022ee:   01 f6                   add    %esi,%esi
  4022f0:   89 d5                   mov    %edx,%ebp
  4022f2:   c1 e5 02                shl    $0x2,%ebp
  4022f5:   01 d5                   add    %edx,%ebp
  4022f7:   01 ed                   add    %ebp,%ebp
  4022f9:   41 89 f7                mov    %esi,%r15d
  4022fc:   41 c1 e7 02             shl    $0x2,%r15d
  402300:   41 01 f7                add    %esi,%r15d
  402303:   45 01 ff                add    %r15d,%r15d
  402306:   ff c8                   dec    %eax
  402308:   0f 85 62 ff ff ff       jne    402270 <_Z7measureIN5timer5rtdscE2V2Li16777216ELi4ELi2EEvv+0xe0>

Измерения для V2

name    uroll ilp   ref cyclescpu cyclesp0      p1      p2      p3      p4      p5      p6      p7      
V2      16    1        2.696   3.004   0.776   0.714   0.000   0.000   0.000   0.731   0.811   0.000
V2      16    2        1.454   1.620   0.791   0.706   0.000   0.000   0.000   0.719   0.800   0.000
V2      16    4        0.918   1.022   0.836   0.679   0.000   0.000   0.000   0.696   0.795   0.000
V2      16    8        0.914   1.018   0.864   0.647   0.006   0.002   0.012   0.671   0.826   0.008
V2      16    16       1.277   1.414   0.834   0.652   0.237   0.263   0.334   0.685   0.887   0.161
V2      16    32       1.572   1.751   0.962   0.703   0.532   0.560   0.671   0.740   1.003   0.230

Это тоже имеет смысл, мы медленнее, а при i=32 у нас наверняка слишком большое давление в регистре (показано другими используемыми портами и в сборке)... При i=0 мы можем убедиться, что p0+ p1+p5+p6=~3,001, так что никакой ILP, конечно. Мы могли бы ожидать 4 такта процессора, но MOV предоставляется бесплатно (распределение регистров).

При i=4: SHL выполняется на p0 или p6, ADD и MOV выполняются на p0, 1, 5 или 6. Таким образом, у нас есть 1 операция на p0 или p6 и 2+1 операция (добавить/переместить) на p0, p1, p5 или p6. Опять же, MOV бесплатен, поэтому мы получаем 1 цикл за умножение.

И, наконец, с оптимизированной версией:

  402730:   67 8d 7c ad 00          lea    0x0(%ebp,%ebp,4),%edi
  402735:   01 ff                   add    %edi,%edi
  402737:   67 43 8d 2c bf          lea    (%r15d,%r15d,4),%ebp
  40273c:   01 ed                   add    %ebp,%ebp
  40273e:   67 8d 1c bf             lea    (%edi,%edi,4),%ebx
  402742:   01 db                   add    %ebx,%ebx
  402744:   67 8d 7c ad 00          lea    0x0(%ebp,%ebp,4),%edi
  402749:   01 ff                   add    %edi,%edi
  40274b:   67 8d 2c 9b             lea    (%ebx,%ebx,4),%ebp
  40274f:   01 ed                   add    %ebp,%ebp
  402751:   67 8d 1c bf             lea    (%edi,%edi,4),%ebx
  402755:   01 db                   add    %ebx,%ebx
  402757:   67 8d 7c ad 00          lea    0x0(%ebp,%ebp,4),%edi
  40275c:   01 ff                   add    %edi,%edi
  40275e:   67 8d 2c 9b             lea    (%ebx,%ebx,4),%ebp
  402762:   01 ed                   add    %ebp,%ebp
  402764:   67 8d 1c bf             lea    (%edi,%edi,4),%ebx
  402768:   01 db                   add    %ebx,%ebx
  40276a:   67 8d 7c ad 00          lea    0x0(%ebp,%ebp,4),%edi
  40276f:   01 ff                   add    %edi,%edi
  402771:   67 8d 2c 9b             lea    (%ebx,%ebx,4),%ebp
  402775:   01 ed                   add    %ebp,%ebp
  402777:   67 8d 1c bf             lea    (%edi,%edi,4),%ebx
  40277b:   01 db                   add    %ebx,%ebx
  40277d:   67 44 8d 64 ad 00       lea    0x0(%ebp,%ebp,4),%r12d
  402783:   45 01 e4                add    %r12d,%r12d
  402786:   67 44 8d 2c 9b          lea    (%ebx,%ebx,4),%r13d
  40278b:   45 01 ed                add    %r13d,%r13d
  40278e:   67 43 8d 2c a4          lea    (%r12d,%r12d,4),%ebp
  402793:   01 ed                   add    %ebp,%ebp
  402795:   67 47 8d 7c ad 00       lea    0x0(%r13d,%r13d,4),%r15d
  40279b:   45 01 ff                add    %r15d,%r15d
  40279e:   ff c9                   dec    %ecx
  4027a0:   75 8e                   jne    402730 <_Z7measureIN5timer5rtdscE2V3Li16777216ELi4ELi2EEvv+0x170>

Измерения для V3

name    uroll ilp   ref cyclescpu cyclesp0      p1      p2      p3      p4      p5      p6      p7      
V3      16    1        1.797   2.002   0.447   0.558   0.000   0.000   0.000   0.557   0.469   0.000
V3      16    2        1.273   1.418   0.448   0.587   0.000   0.000   0.000   0.528   0.453   0.000
V3      16    4        0.774   0.835   0.449   0.569   0.000   0.000   0.000   0.548   0.442   0.000
V3      16    8        0.572   0.636   0.440   0.555   0.017   0.021   0.032   0.562   0.456   0.012
V3      16    16       0.753   0.838   0.433   0.630   0.305   0.324   0.399   0.644   0.458   0.165
V3      16    32       0.976   1.087   0.467   0.766   0.514   0.536   0.701   0.737   0.458   0.333

Ладно, теперь мы быстрее имула. 2 такта для i=0 (1 для обеих инструкций), а для i=8 мы еще быстрее:. lea может выполняться на p1 и p5, а add, как указано выше, на p0, p1, p5 или p6. Таким образом, при идеальном расписании LEA переходит к p1 и p5, ADD к p0 или p6. К сожалению, в данном случае все не так идеально (сборка в порядке). Я предполагаю, что планирование не идеально, и несколько ADD приземляются на порты p1/p5.

Попробуйте собрать с включенной оптимизацией. Добавьте флаг 

    for (unsigned i = 0; i < (1 << 30); ++i) {
        r1 = r2 * 10;
        r2 = r1 * 10;
    }
и проверьте сборку.

person overseas    schedule 12.11.2016
comment
Компромисс между IMUL и LEA интересен для умножения на 10 или что-то вроде того, где требуется две инструкции, чтобы сделать это без IMUL, но по-прежнему имеет задержку 2c вместо 3c. Если пропускная способность uop объединенного домена является узким местом, а задержка — нет, то выигрывает IMUL. IIRC, clang любит использовать IMUL для 2.78, но gcc любит использовать LEA + ADD, оба с imul r,r, imm. - person Peter Cordes; 13.11.2016
comment
Этот цикл IMUL inline-asm скомпилирован без оптимизации? Это объяснило бы дополнительные инструкции MOV. К счастью для вас, Haswell обрабатывает эти инструкции MOV с нулевой задержкой на этапе регистрации-переименования. - person Peter Cordes; 13.11.2016
comment
@PeterCordes Спасибо за ваши комментарии. Сейчас я интегрировал производительность и обновил измерения (было бы здорово, если бы вы могли прокомментировать разницу, которую я все еще наблюдаю между циклами ref/циклами процессора). Я как-то сбит с толку, почему этот вопрос так часто занижается, потому что я почти уверен, что мои измерения улучшаются, и вопрос наверняка не так уж плох. Поэтому, если кто-то что-то упускает, я бы предпочел комментарий, а не просто отрицательные голоса (в принципе, меня не волнуют отрицательные голоса, но я хотел бы сделать эти измерения правильно). - person Peter Cordes; 13.11.2016
comment
Опорные циклы (подсчитываемые RDTSC и счетчиком производительности опорных циклов) всегда учитываются на номинальной максимальной частоте ЦП. (например, процессор с тактовой частотой 2,4 ГГц будет учитываться при этом, независимо от того, будет ли ядро, выполняющее ваш код, ускорено до 3,1 ГГц или понижено до 1,6 ГГц. RDTSC в настоящее время разработан, чтобы хорошо работать в качестве источника времени для таких вещей, как gettimeofday, в большей степени, чем perf измерения.) Поскольку все, что вы измеряете, идеально масштабируется с тактовыми циклами ядра, вам следует заботиться только об этом; тогда вам не нужны циклы прогрева, и, что более важно, ваши числа будут соответствовать реальному поведению ЦП в циклах с целыми числами. - person overseas; 13.11.2016
comment
например ваш первый набор результатов для основных тактовых циклов точно соответствует тому, что вы могли бы предсказать, исходя из известного факта, что _1_ имеет задержку 3 с, одну на 1 с пропускной способности: узкое место по задержке составляет один на 3 с без ILP или два на 3 с. Но с большим количеством ILP, чем это, узким местом является пропускная способность один за такт. - person Peter Cordes; 13.11.2016
comment
re: вопрос против: как я прокомментировал вчера, причина, по которой я проголосовал против, заключается в том, что вы отвлекаетесь от вопроса IMUL против LEA+ADD, говоря о целой куче неоптимизированного вывода компилятора, что совершенно бессмысленно и является пустой тратой времени . например Я только что попробовал версию imul r,r,imm на Godbolt, и gcc/clang/icc все увидели, что она делает, и скомпилировали ее так же, как _2_ (godbolt.org/g/qCkXNe). Если вы этого не поняли, вы делаете что-то очень неправильное (например, не используете _3_ или _4_). Как только вы перепишете вопрос, чтобы убрать все неоптимизированное дерьмо, я бы с удовольствием проголосовал за него. - person Peter Cordes; 13.11.2016
comment
О, только что нашел абзац, который вы имели в виду о циклах ref: используйте драйвер acpi-cpufreq с производительностью регулятора, фиксированной на 3,5 ГГц. Это, вероятно, не отключает турбо. Turbo всегда находится под аппаратным управлением и может активироваться всякий раз, когда программное обеспечение устанавливает часы на максимальную номинальную частоту. (Решения по тактовой частоте в турборежиме учитывают больше информации, чем у SW. Skylake может сделать это даже для всех решений по тактовой частоте, а не только в турборежиме. 408A-8B61-65D7520025A8/7/5#sessionID=155" rel="nofollow noreferrer">выступление SKL power mgmt на IDF2015 сравнивает HSW и SKL) - person Peter Cordes; 13.11.2016
comment
В секции shift+add: i=32, у нас наверняка слишком большое давление регистра?? Это вывод компилятора или написанный от руки ассемблер? Это на самом деле вылилось в память, или это просто догадки, не глядя на ассемблер? Другим эффектом будет то, что будет слишком много мопов для запуска из буфера обратной связи. Тем не менее, это все однократные инструкции, поэтому они должны эффективно работать из кеша uop. Взгляните на эти вопросы и ответы для графиков зависимости пропускной способности uop от размера цикла - person Peter Cordes; 13.11.2016
comment
В вашей версии LEA, почему вы заставляете базовые и индексные регистры быть разными? И зачем эти инструкции MOV? Если вы напишите его как _1_ _2_ _3_ _4_ _5_, вы должны получить оптимальный ассемблер, который читает напрямую из старого регистра, вместо того, чтобы копировать R9 в регистры для уничтожения. У вас, вероятно, узкое место во внешнем интерфейсе, 4 операции с объединенным доменом за такт. Вы должны получать почти 2 умножения за такт (без накладных расходов на цикл). - person Peter Cordes; 13.11.2016
comment
Было бы неплохо по крайней мере дать ссылку на источник этого материала на Godbolt, чтобы мы могли видеть, какой asm используется для каждого случая unroll и ILP. - person Peter Cordes; 13.11.2016
comment
Хорошо, изменил вопрос без дерьма. Это весь вывод компилятора, когда я использую i=32, я вижу много дополнительных движений в выводе ассемблера. - person Peter Cordes; 13.11.2016
comment
Версия LEA: Отлично, что вы это видели. Сейчас у нас два цикла. Похоже, что две операции занимают всего 1/2 цикла, я полагаю. Но не уверен. Я проверю, могу ли я связать источник с Godbolt... - person overseas; 13.11.2016
comment
Таким образом, вы все еще используете встроенный ассемблер, и нигде вы не синхронизируете вывод компилятора из цикла C с _1_, который вы показываете в верхней части своего ответа (clang выполняет некоторые оптимизации для него, например, он замечает, что результат всегда равен нулю, но все еще зацикливается с -march=haswell) См. godbolt.org/g/6PlRhQ. Вы должны просто удалить этот исходный код C++ и просто сохранить фактические циклы ассемблера, которые вы измеряете. Не подразумевайте, что у вас есть этот цикл для компиляции в ассемблер, который вы показываете. - person overseas; 13.11.2016
comment
В вашем встроенном ассемблере вам не нужно r1 = r2 * 10 после каждой инструкции. Вот почему все это выглядит с двойным интервалом. Используйте _2_, чтобы начать следующую инструкцию с новой строки с табуляцией. Я исправил это для вас, но goo.gl не будет сокращать такую ​​длинную ссылку Godbolt (и глупые комментарии SO не поддерживают длинные URL-адреса). Вот только измененная часть: godbolt.org/g/weMVwW. Довольно забавно, как gcc пытается автоматически векторизовать его или что-то в этом роде, или не может оптимизировать часть хранения в массивах и выполняет VPINSRD вместе с каждым умножением. - person Peter Cordes; 14.11.2016
comment
Конечно, я не делаю r1 = r2 * 10 в реальном коде. Я хотел придерживаться трех вариантов сборки, приведенных в вопросе, без каких-либо дополнительных ходов. Сборки там всегда с входным != выходным регистром, поэтому я тоже делаю это здесь (иначе нагрузка на регистры была бы другой). Итак, моя цель — написать код, который компилируется именно в тот ассемблер, который я показываю в вопросе, который, на мой взгляд, дан в данном случае. Другой вопрос, ясно ли это в моем ответе. - person Peter Cordes; 14.11.2016
comment
Я изменил \r\n (думаю, я начал с некоторого кода, где некоторые участники работали над окнами...). Мысль с gcc довольно забавная, и это произошло только тогда, когда я добавил второй массив с двумя do_ilp_step в do_unroll_step (до этого он также выполнял только инструкции imul). - person overseas; 14.11.2016
comment
Да, было ясно, что вы на самом деле сделали, особенно после просмотра вашей ссылки на божественную стрелу. Это последнее обновление теперь исправляет ответ, чтобы он не вводил в заблуждение. - person overseas; 14.11.2016
comment
Однако в ваших выводах есть некоторые ошибки: оба ADD и MOV выполняются на p0, 1, 5 или 6: не совсем так. MOV вообще не нужен порт выполнения, и он выполняется во время переименования регистра. Это называется удалением mov. Это все еще объединенный домен uop, поэтому вы являетесь узким местом в выпуске / удалении ширины неупорядоченного ядра при 1 умножении за такт (IDK, почему вы сказали 1,25; вы видите это только тогда, когда у вас заканчиваются регистры и проливается на память). - person Peter Cordes; 14.11.2016
comment
Похоже, что две из трех инструкций занимают всего 1/2 цикла: Три инструкции? LEA+ADD — это всего две инструкции. И да, это дает вам пропускную способность, равную двум умножениям за такт (теоретически при идеальном планировании ядром ООО; на практике конфликты ресурсов из-за того, что ADD крадут циклы на p1 или p5, снижают вашу пропускную способность до одного на 0,65 цикла). Как я уже сказал в своем ответе, простой LEA может работать на p1/p5, а ADD может работать на любом порту ALU. - person Peter Cordes; 14.11.2016
comment
Они не были в курсе. Простите за это. В какой-то момент я заметил дополнительный ход (который был удален из-за переименования регистра, я думаю). - person Peter Cordes; 14.11.2016
comment
Отказ от инструкций MOV во время компиляции не является регистровым переименованием. Если вы хотите назвать это как-то иначе, возможно, лучше будет использовать регистровое распределение. Кстати, я не думаю, что это хорошая идея, чтобы удалить временной код из вашей ссылки Godbolt. Люди могут захотеть попробовать тот же код на своих собственных процессорах. Довольно легко найти соответствующую часть ассемблерного вывода, поскольку символы новой строки между каждой группой делают очевидным, какая часть принадлежит inline-asm. - person overseas; 14.11.2016
comment
Спасибо за поправку. Добавлен полный код. Это, вероятно, не так красиво, этого достаточно для работы (и оно скопировано из нескольких файлов, поэтому, вероятно, включения не так хорошо оптимизированы). - person Peter Cordes; 14.11.2016
comment
All code can be seen on - person overseas; 14.11.2016