Выравнивание ветвей для циклов, включающих микрокодированные инструкции на процессорах семейства Intel SnB
Это связано, но не то же самое, что и этот вопрос: Оптимизация производительности сборки x86-64- прогнозирование выравнивания и ветвления и немного связана с моим предыдущим вопросом: 64-разрядное беззнаковое преобразование: почему этот алгоритм из g++
Ниже приведен нереальный тестовый пример. Этот алгоритм тестирования простоты не имеет смысла. Я подозреваю, что любой реальный алгоритм никогда не будет выполнять такой маленький внутренний цикл столько раз (num простое число размером около 2**50). В C++11:
using nt = unsigned long long;
bool is_prime_float(nt num)
{
for (nt n=2; n<=sqrt(num); ++n) {
if ( (num%n)==0 ) { return false; }
}
return true;
}
затем g++ -std=c++11 -O3 -S производит следующее, с RCX, содержащим n и XMM6, содержащий sqrt(num), См. Мой предыдущий пост для оставшегося кода (который никогда не выполняется в этом примере, так как RCX никогда не становится достаточно большим, чтобы рассматриваться как подписанный минус).
jmp .L20
.p2align 4,,10
.L37:
pxor %xmm0, %xmm0
cvtsi2sdq %rcx, %xmm0
ucomisd %xmm0, %xmm6
jb .L36 // Exit the loop
.L20:
xorl %edx, %edx
movq %rbx, %rax
divq %rcx
testq %rdx, %rdx
je .L30 // Failed divisibility test
addq $1, %rcx
jns .L37
// Further code to deal with case when ucomisd can't be used
Я раз это использую std::chrono::steady_clock, Я продолжал получать странные изменения производительности: от простого добавления или удаления другого кода. Я в конечном счете отследил это до проблемы выравнивания. Команда .p2align 4,,10 попытался выровнять по границе 2**4=16 байт, но для этого используется не более 10 байтов заполнения, я думаю, что баланс между выравниванием и размером кода.
Я написал скрипт на Python для замены .p2align 4,,10 по количеству контролируемых вручную nop инструкции. На следующем точечном графике показаны самые быстрые прогоны 15 из 20, время в секундах, количество заполненных байтов по оси x:
От objdump без заполнения инструкция pxor будет выполняться со смещением 0x402f5f. Работая на ноутбуке, Sandybridge i5-3210m, турбобуст отключен, я обнаружил, что
- Для заполнения 0 байт, низкая производительность (0,42 с)
- Для заполнения 1-4 байта (смещение от 0x402f60 до 0x402f63) становится немного лучше (0,41 с, видимый на графике).
- Для заполнения 5-20 байтов (смещение от 0x402f64 до 0x402f73) достигается высокая производительность (0,37 с)
- Для заполнения на 21-32 байта (смещение от 0x402f74 до 0x402f7f) низкая производительность (0,42 секунды)
- Затем циклы на 32-байтовом образце
Таким образом, 16-байтовое выравнивание не дает наилучшей производительности - оно помещает нас в немного лучшую (или просто меньшую вариацию, по сравнению с диаграммой рассеяния) область. Выравнивание 32 плюс 4 до 19 дает лучшую производительность.
Почему я вижу эту разницу в производительности? Почему это нарушает правило выравнивания целей ветвления по 16-байтовой границе (см., Например, руководство по оптимизации Intel)
Я не вижу проблем с предсказанием ветвлений. Может ли это быть причудой кэша UOP??
Изменяя алгоритм C++ для кэширования sqrt(num) в 64-разрядном целом числе, а затем в цикле, основанном исключительно на целочисленных значениях, я устраняю проблему - выравнивание теперь не имеет значения вообще.
4 ответа
Вот что я нашел на Skylake для того же цикла. Весь код для воспроизведения моих тестов на вашем оборудовании находится на github.
Я наблюдаю три разных уровня производительности, основанных на выравнивании, тогда как OP действительно видел только 2 основных. Уровни очень четкие и повторяемые2:
Здесь мы видим три различных уровня производительности (шаблон повторяется, начиная со смещения 32), которые мы будем называть областями 1, 2 и 3 слева направо (область 2 разделена на две части, охватывающие область 3). Самая быстрая область (1) имеет смещение от 0 до 8, средняя (2) область находится в диапазоне 9-18 и 28-31, а самая медленная (3) - 19-27. Разница между каждым регионом близка или равна 1 циклу / итерации.
Судя по счетчикам производительности, самый быстрый регион сильно отличается от двух других:
- Все инструкции доставляются от устаревшего декодера, а не от DSB1.
- Для каждой итерации цикла существует ровно 2 переключателя микрокода декодера <-> (idq_ms_switches).
С другой стороны, две более медленные области довольно похожи:
- Все инструкции доставляются из DSB (кэш uop), а не из устаревшего декодера.
- На каждую итерацию цикла приходится ровно 3 переключателя декодера <-> микрокода.
Переход от самой быстрой к средней области, когда смещение изменяется от 8 до 9, точно соответствует моменту начала цикла в буфере uop из-за проблем с выравниванием. Вы рассчитываете это точно так же, как Петр в своем ответе:
Смещение 8:
LSD? <_start.L37>:
ab 1 4000a8: 66 0f ef c0 pxor xmm0,xmm0
ab 1 4000ac: f2 48 0f 2a c1 cvtsi2sd xmm0,rcx
ab 1 4000b1: 66 0f 2e f0 ucomisd xmm6,xmm0
ab 1 4000b5: 72 21 jb 4000d8 <_start.L36>
ab 2 4000b7: 31 d2 xor edx,edx
ab 2 4000b9: 48 89 d8 mov rax,rbx
ab 3 4000bc: 48 f7 f1 div rcx
!!!! 4000bf: 48 85 d2 test rdx,rdx
4000c2: 74 0d je 4000d1 <_start.L30>
4000c4: 48 83 c1 01 add rcx,0x1
4000c8: 79 de jns 4000a8 <_start.L37>
В первом столбце я комментировал, как мопы для каждой инструкции попадают в кеш мопов. "ab 1" означает, что они идут в наборе, связанном с адресом, как ...???a? или же ...???b? (каждый набор занимает 32 байта, иначе 0x20), в то время как 1 означает способ 1 (из максимум 3).
На данный момент!!! это вылетает из кэша UOP, потому что test Инструкция не имеет, куда идти, все 3 пути исчерпаны.
Давайте посмотрим на смещение 9 с другой стороны:
00000000004000a9 <_start.L37>:
ab 1 4000a9: 66 0f ef c0 pxor xmm0,xmm0
ab 1 4000ad: f2 48 0f 2a c1 cvtsi2sd xmm0,rcx
ab 1 4000b2: 66 0f 2e f0 ucomisd xmm6,xmm0
ab 1 4000b6: 72 21 jb 4000d9 <_start.L36>
ab 2 4000b8: 31 d2 xor edx,edx
ab 2 4000ba: 48 89 d8 mov rax,rbx
ab 3 4000bd: 48 f7 f1 div rcx
cd 1 4000c0: 48 85 d2 test rdx,rdx
cd 1 4000c3: 74 0d je 4000d2 <_start.L30>
cd 1 4000c5: 48 83 c1 01 add rcx,0x1
cd 1 4000c9: 79 de jns 4000a9 <_start.L37>
Теперь нет проблем! test инструкция проскользнула в следующую строку 32B (cd строка), так что все помещается в кэш UOP.
Таким образом, это объясняет, почему вещи изменяются между MITE и DSB в этот момент. Это, однако, не объясняет, почему путь MITE быстрее. Я попробовал несколько более простых тестов с div в цикле, и вы можете воспроизвести это с более простыми циклами без каких-либо вещей с плавающей запятой. Это странно и чувствительно к случайным вещам, которые вы кладете в цикл.
Например, этот цикл также выполняется быстрее из устаревшего декодера, чем DSB:
ALIGN 32
<add some nops here to swtich between DSB and MITE>
.top:
add r8, r9
xor eax, eax
div rbx
xor edx, edx
times 5 add eax, eax
dec rcx
jnz .top
В этом цикле добавление бессмысленного add r8, r9 Инструкция, которая на самом деле не взаимодействует с остальной частью цикла, ускорила работу для версии MITE (но не для версии DSB).
Поэтому я думаю, что различие между областью 1 и областью 2 и 3 связано с тем, что первый выполняется из устаревшего декодера (что, как ни странно, делает его быстрее).
Давайте также рассмотрим переход от смещения 18 к смещению 19 (где region 2 заканчивается, а 3 начинается):
Смещение 18:
00000000004000b2 <_start.L37>:
ab 1 4000b2: 66 0f ef c0 pxor xmm0,xmm0
ab 1 4000b6: f2 48 0f 2a c1 cvtsi2sd xmm0,rcx
ab 1 4000bb: 66 0f 2e f0 ucomisd xmm6,xmm0
ab 1 4000bf: 72 21 jb 4000e2 <_start.L36>
cd 1 4000c1: 31 d2 xor edx,edx
cd 1 4000c3: 48 89 d8 mov rax,rbx
cd 2 4000c6: 48 f7 f1 div rcx
cd 3 4000c9: 48 85 d2 test rdx,rdx
cd 3 4000cc: 74 0d je 4000db <_start.L30>
cd 3 4000ce: 48 83 c1 01 add rcx,0x1
cd 3 4000d2: 79 de jns 4000b2 <_start.L37>
Смещение 19:
00000000004000b3 <_start.L37>:
ab 1 4000b3: 66 0f ef c0 pxor xmm0,xmm0
ab 1 4000b7: f2 48 0f 2a c1 cvtsi2sd xmm0,rcx
ab 1 4000bc: 66 0f 2e f0 ucomisd xmm6,xmm0
cd 1 4000c0: 72 21 jb 4000e3 <_start.L36>
cd 1 4000c2: 31 d2 xor edx,edx
cd 1 4000c4: 48 89 d8 mov rax,rbx
cd 2 4000c7: 48 f7 f1 div rcx
cd 3 4000ca: 48 85 d2 test rdx,rdx
cd 3 4000cd: 74 0d je 4000dc <_start.L30>
cd 3 4000cf: 48 83 c1 01 add rcx,0x1
cd 3 4000d3: 79 de jns 4000b3 <_start.L37>
Единственное отличие, которое я вижу здесь, состоит в том, что первые 4 инструкции в случае смещения 18 вписываются в ab строка кэша, но только 3 в случае смещения 19. Если мы предположим, что DSB может доставлять мопы в IDQ только из одного набора кеша, это означает, что в какой-то момент один моп может быть выполнен и выполнен на цикл раньше в сценарии смещения 18, чем в сценарии 19 (представьте, например, что IDQ пуст). В зависимости от того, к какому именно порту подключается этот UOP в контексте окружающего потока UOP, это может задержать цикл на один цикл. Действительно, разница между областью 2 и 3 составляет ~1 цикл (в пределах погрешности).
Поэтому я думаю, что мы можем сказать, что различие между 2 и 3, вероятно, связано с выравниванием кэша uop - область 2 имеет немного лучшее выравнивание, чем 3, с точки зрения выдачи одного дополнительного цикла uop на один цикл ранее.
Некоторые дополнительные примечания о вещах, которые я проверил, не удавалось как возможная причина замедлений:
Несмотря на то, что режимы DSB (области 2 и 3) имеют 3 переключателя микрокода по сравнению с 2 на пути MITE (область 1), это, по-видимому, не вызывает прямого замедления. В частности, более простые циклы с
divвыполнить в идентичных счетчиках циклов, но все еще показывают 3 и 2 коммутатора для путей DSB и MITE соответственно. Так что это нормально и не подразумевает замедления.Оба пути выполняют по существу одинаковое количество мопов и, в частности, имеют одинаковое количество мопов, сгенерированных секвенсором микрокода. Так что не похоже, что в разных регионах проводится больше общей работы.
На самом деле не было никакой разницы в промахах кеша (очень низком, как и ожидалось) на разных уровнях, неправильных предсказаниях ветвлений (по существу, ноль3) или любых других типах штрафов или необычных условиях, которые я проверял.
Что принесло свои плоды, так это взгляд на структуру использования исполнительных подразделений в разных регионах. Вот взгляд на распределение мопов, выполненных за цикл, и некоторые показатели задержки:
+----------------------------+----------+----------+----------+
| | Region 1 | Region 2 | Region 3 |
+----------------------------+----------+----------+----------+
| cycles: | 7.7e8 | 8.0e8 | 8.3e8 |
| uops_executed_stall_cycles | 18% | 24% | 23% |
| exe_activity_1_ports_util | 31% | 22% | 27% |
| exe_activity_2_ports_util | 29% | 31% | 28% |
| exe_activity_3_ports_util | 12% | 19% | 19% |
| exe_activity_4_ports_util | 10% | 4% | 3% |
+----------------------------+----------+----------+----------+
Я выбрал несколько разных значений смещения, и результаты были согласованы в каждом регионе, но между регионами у вас были совершенно разные результаты. В частности, в области 1 у вас меньше циклов останова (циклов, когда выполнение не выполняется). У вас также есть значительные различия в циклах без срывов, хотя четкой тенденции "лучше" или "хуже" не видно. Например, область 1 имеет гораздо больше циклов (10% против 3% или 4%) с 4 выполненными мопами, но другие регионы в основном восполняют это с большим количеством циклов с 3 выполненными мопами и несколькими циклами с 1 выполненным мопом.
Разница в UPC4, которую подразумевает вышеупомянутое распределение выполнения, полностью объясняет разницу в производительности (это, вероятно, тавтология, поскольку мы уже подтвердили, что число мопов между ними одинаковое).
Давайте посмотрим, что может сказать по этому поводу toplev.py... (результаты опущены).
Что ж, топлев предполагает, что основным узким местом является внешний интерфейс (50+%). Я не думаю, что вы можете доверять этому, потому что способ вычисления предела FE кажется неправильным в случае длинных строк микрокодированных инструкций. Привязка к FE основана на frontend_retired.latency_ge_8, который определяется как:
Удаленные инструкции, которые извлекаются после интервала, в течение которого интерфейс не доставлял мопов в течение 8 циклов, которые не были прерваны внутренним остановом. (Поддерживает PEBS)
Обычно это имеет смысл. Вы считаете инструкции, которые были задержаны, потому что интерфейс не доставлял циклы. Условие "не прерывается внутренним остановом" гарантирует, что это не сработает, когда внешний интерфейс не доставляет мопы просто потому, что бэкэнд не может их принять (например, когда RS заполнен, потому что бэкэнд выполняет некоторые инструкции с низким уровнем throuput).
Вроде как для div инструкции - даже простой цикл с почти одним div показывает:
FE Frontend_Bound: 57.59 % [100.00%]
BAD Bad_Speculation: 0.01 %below [100.00%]
BE Backend_Bound: 0.11 %below [100.00%]
RET Retiring: 42.28 %below [100.00%]
То есть единственным узким местом является интерфейс ("выход на пенсию" не является узким местом, он представляет полезную работу). Ясно, что такой цикл тривиально обрабатывается внешним интерфейсом и вместо этого ограничивается способностью внутреннего интерфейса жевать все броски, сгенерированные div операция. Топлев может сделать это действительно неправильно, потому что (1) может случиться так, что мопы, доставленные секвенсором микрокода, не учитываются в frontend_retired.latency... счетчики, так что каждый div операция заставляет это событие подсчитывать все последующие инструкции (даже несмотря на то, что процессор был занят в течение этого периода - реального сбоя не было), или (2) секвенсор микрокода может доставить все свои всплывающие сообщения, по существу, "впереди", отбрасывая ~36 моп. в IDQ, после чего он больше не доставляет, пока div закончен, или что-то в этом роде.
Тем не менее, мы можем посмотреть на более низкие уровни toplev для подсказок:
Основное различие между топлевами между регионами 1 и 2 и 3 состоит в увеличении штрафа ms_switches для последних двух областей (так как они несут 3 каждой итерации против 2 для унаследованного пути. Внутренне, toplev оценивает штраф за 2 цикла во внешнем интерфейсе для таких коммутаторов. Разумеется, замедляют ли эти штрафы что-либо сложным образом, зависит от очереди команд и других факторов. Как уже упоминалось выше, простой цикл с div не показывает никакой разницы между путями DSB и MITE, цикл с дополнительными инструкциями делает. Таким образом, возможно, что дополнительный пузырь коммутатора поглощается более простыми циклами (где внутренняя обработка всех мопов, генерируемых div является основным фактором), но как только вы добавите какую-то другую работу в цикл, переключатели станут фактором по крайней мере для переходного периода между div и недивай работа.
Таким образом, я предполагаю, что мой вывод состоит в том, что способ, которым инструкция div взаимодействует с остальной частью внешнего интерфейса и выполнением бэкэнда, не совсем понятен. Мы знаем, что это связано с потоком мопов, доставленных обоими из MITE/DSB (кажется, 4 моп в div) и из секвенсора микрокода (кажется, ~32 моп в divхотя он изменяется при разных входных значениях div op) - но мы не знаем, что это за мопы (хотя мы можем видеть их распределение по портам). Все это делает поведение довольно непрозрачным, но я думаю, что это, скорее всего, связано либо с тем, что коммутаторы MS не работают в обход внешнего интерфейса, либо с небольшими различиями в потоке доставки UOP, что приводит к различным решениям по планированию, которые в итоге приводят к созданию мастера заказов MITE.
1 Конечно, большинство мопов вообще не доставляются из устаревшего декодера или DSB, а через секвенсор микрокода (мс). Таким образом, мы свободно говорим о доставленных инструкциях, а не мопах.
2 Обратите внимание, что ось x здесь является "байтами смещения от выравнивания 32B". То есть 0 означает, что верхняя часть цикла (метка.L37) выровнена по границе 32B, а 5 означает, что цикл начинается на пять байтов ниже границы 32B (используя nop для заполнения) и так далее. Так что мои байты заполнения и смещение одинаковы. ОП использовал другое значение для смещения, если я правильно понял: его 1 байт заполнения привел к смещению 0. Таким образом, вы должны вычесть 1 из значений отступов OP, чтобы получить мои значения смещения.
3 Фактически, скорость предсказания ветвления для типичного теста с prime=1000000000000037 составлял ~99,999997%, отражая только 3 ошибочно предсказанных ветвления за весь прогон (вероятно, при первом проходе цикла и последней итерации).
4 UPC, т. Е. Число мопов за цикл - мера, тесно связанная с IPC для похожих программ, и более точная, когда мы подробно рассмотрим потоки мопов. В этом случае мы уже знаем, что количество мопов одинаково для всех вариантов выравнивания, поэтому UPC и IPC будут прямо пропорциональны.
У меня нет конкретного ответа, только несколько разных гипотез, которые я не могу проверить (нехватка оборудования). Я думал, что нашел что-то убедительное, но у меня было выравнивание на единицу (потому что вопрос считается отступом от 0x5F, а не от выровненной границы). В любом случае, надеюсь, в любом случае будет полезно опубликовать это, чтобы описать факторы, которые, вероятно, здесь играют.
В вопросе также не указывается кодировка ветвей (короткая (2B) или близкая (6B)). Это оставляет слишком много возможностей взглянуть и теоретизировать о том, какая именно команда пересекает границу 32B или нет, вызывает проблему.
Я думаю, что это либо вопрос подгонки циклов в кэше uop, либо нет, или же вопрос выравнивания, определяющий, будет ли он быстро декодироваться устаревшими декодерами.
Очевидно, что цикл asm мог бы быть значительно улучшен (например, путем выведения из него числа с плавающей точкой, не говоря уже об использовании совсем другого алгоритма), но это не вопрос. Мы просто хотим знать, почему выравнивание имеет значение для этого точного цикла.
Вы можете ожидать, что цикл, который является узким местом на делении, не будет узким местом на внешнем интерфейсе или не будет затронут выравниванием, потому что деление является медленным, и цикл выполняет очень мало инструкций за такт. Это правда, но 64-битный DIV микрокодируется в 35-57 микрооперациях (мопах) на IvyBridge, поэтому оказывается, что могут возникнуть проблемы с интерфейсом.
Два основных способа выравнивания могут иметь значение:
- Узкие места переднего плана (на этапах извлечения / декодирования), приводящие к появлению пузырьков при сохранении неисправного ядра, снабженного работой.
- Прогнозирование ветвлений: если две ветви имеют один и тот же адрес по модулю некоторой большой степени 2, они могут использовать псевдонимы друг друга в аппаратном обеспечении прогнозирования ветвлений. Выравнивание кода в одном объектном файле влияет на производительность функции в другом объектном файле, что устраняет эту проблему, но об этом много написано.
Я подозреваю, что это чисто внешняя проблема, а не предсказание ветвлений, поскольку код тратит все свое время в этом цикле и не запускает другие ветки, которые могли бы совпасть с приведенными здесь.
Ваш процессор Intel IvyBridge является идеальным вариантом SandyBridge. В нем есть несколько изменений (например, mov-elission, и ERMSB), но внешний интерфейс похож на SnB/IvB/Haswell. Microarch pdf от Agner Fog содержит достаточно деталей для анализа того, что должно произойти, когда процессор выполняет этот код. См. Также запись Дэвида Кантера SandyBridge для блок-схемы этапов выборки / декодирования, но он разделяет выборку / декодирование из кэша UOP, микрокода и очереди декодированного UOP. В конце приведена полная блок-схема всего ядра. Его статья на Haswell содержит блок-схему, включающую весь интерфейс, вплоть до очереди decoded-uop, которая питает стадию проблемы. (IvyBridge, как и Haswell, имеет буфер очереди / петли 56 мегапикселей, когда не использует Hyperthreading. Sandybridge статически разделяет их на 2 × 28 моп очередей, даже когда HT отключен.)
Изображение скопировано из превосходной записи Дэвида Кантера на Haswell, где он включает декодеры и uop-кеш в одну диаграмму.
Давайте посмотрим, как кеш uop, вероятно, кеширует этот цикл, когда все уладится. (т.е. предполагая, что запись цикла с jmp к середине цикла не оказывает какого-либо серьезного долгосрочного влияния на то, как цикл находится в кэше uop).
Согласно руководству по оптимизации Intel (2.3.2.2 Decoded ICache):
- Все микрооперации в пути (строка кэша uop) представляют собой команды, которые являются статически смежными в коде и имеют свои EIP в одной и той же выровненной 32-байтовой области. (Я думаю, что это означает, что инструкция, которая выходит за границу, идет в кэш-памяти uop для блока, содержащего его начало, а не конец. Команды Spanning должны куда-то идти, и целевой адрес ветвления, который будет выполнять инструкцию, является началом insn, так что наиболее полезно поместить его в строку для этого блока).
- Инструкция по нескольким микрооперациям не может быть разделена на Пути.
- Инструкция, которая включает MSROM, потребляет весь путь. (т. е. любая инструкция, которая занимает более 4 моп (для reg, reg), микрокодируется. Например, DPPD не микрокодируется (4 моп), а DPPS (6 моп). DPPD с операндом памяти, который может Это не будет 5 микропереключателей, но все равно не нужно будет включать секвенсор микрокода (не тестировался).
- Допускается до двух веток на один путь.
- Пара макро-слитых инструкций сохраняется как одна микрооперация.
У записи Дэвида Кантера в SnB есть еще несколько замечательных деталей о кэше UOP.
Давайте посмотрим, как фактический код попадет в кэш UOP
# let's consider the case where this is 32B-aligned, so it runs in 0.41s
# i.e. this is at 0x402f60, instead of 0 like this objdump -Mintel -d output on a .o
# branch displacements are all 00, and I forgot to put in dummy labels, so they're using the rel32 encoding not rel8.
0000000000000000 <.text>:
0: 66 0f ef c0 pxor xmm0,xmm0 # 1 uop
4: f2 48 0f 2a c1 cvtsi2sd xmm0,rcx # 2 uops
9: 66 0f 2e f0 ucomisd xmm6,xmm0 # 2 uops
d: 0f 82 00 00 00 00 jb 0x13 # 1 uop (end of one uop cache line of 6 uops)
13: 31 d2 xor edx,edx # 1 uop
15: 48 89 d8 mov rax,rbx # 1 uop (end of a uop cache line: next insn doesn't fit)
18: 48 f7 f1 div rcx # microcoded: fills a whole uop cache line. (And generates 35-57 uops)
1b: 48 85 d2 test rdx,rdx ### PROBLEM!! only 3 uop cache lines can map to the same 32-byte block of x86 instructions.
# So the whole block has to be re-decoded by the legacy decoders every time, because it doesn't fit in the uop-cache
1e: 0f 84 00 00 00 00 je 0x24 ## spans a 32B boundary, so I think it goes with TEST in the line that includes the first byte. Should actually macro-fuse.
24: 48 83 c1 01 add rcx,0x1 # 1 uop
28: 79 d6 jns 0x0 # 1 uop
Таким образом, при выравнивании 32B для начала цикла он должен запускаться от устаревших декодеров, который потенциально медленнее, чем запуск из кэша UOP. При переключении с кэша UOP на устаревшие декодеры могут даже возникнуть некоторые проблемы.
Тестирование @Iwill (см. Комментарии к вопросу) показывает, что любая микрокодированная инструкция предотвращает запуск цикла из буфера обратной петли. Смотрите комментарии по вопросу. (LSD = детектор Loop Stream = буфер буфера; физически такая же структура, что и IDQ (очередь декодирования инструкций). DSB = буфер потока декодирования = кэш UOP. MITE = унаследованные декодеры.)
Разрушение кэша UOP ухудшит производительность, даже если цикл достаточно мал для запуска из LSD (минимум 28 UOP или 56 без гиперпоточности на IvB и Haswell).
Руководство по оптимизации Intel (раздел 2.3.2.4) гласит, что требования LSD включают
- Все микрооперации также находятся в декодированном ICache.
Таким образом, это объясняет, почему микрокод не подходит: в этом случае uop-кеш содержит только указатель на микрокод, а не сами мопы. Также обратите внимание, что это означает, что перезапуск кэша UOP по любой другой причине (например, множество однобайтовых инструкций NOP) означает, что цикл не может быть запущен из LSD.
С минимальным дополнением, чтобы идти быстро, согласно тестированию OP.
# branch displacements are still 32-bit, except the loop branch.
# This may not be accurate, since the question didn't give raw instruction dumps.
# the version with short jumps looks even more unlikely
0000000000000000 <loop_start-0x64>:
...
5c: 00 00 add BYTE PTR [rax],al
5e: 90 nop
5f: 90 nop
60: 90 nop # 4NOPs of padding is just enough to bust the uop cache before (instead of after) div, if they have to go in the uop cache.
# But that makes little sense, because looking backward should be impossible (insn start ambiguity), and we jump into the loop so the NOPs don't even run once.
61: 90 nop
62: 90 nop
63: 90 nop
0000000000000064 <loop_start>: #uops #decode in cycle A..E
64: 66 0f ef c0 pxor xmm0,xmm0 #1 A
68: f2 48 0f 2a c1 cvtsi2sd xmm0,rcx #2 B
6d: 66 0f 2e f0 ucomisd xmm6,xmm0 #2 C (crosses 16B boundary)
71: 0f 82 db 00 00 00 jb 152 #1 C
77: 31 d2 xor edx,edx #1 C
79: 48 89 d8 mov rax,rbx #1 C
7c: 48 f7 f1 div rcx #line D
# 64B boundary after the REX in next insn
7f: 48 85 d2 test rdx,rdx #1 E
82: 74 06 je 8a <loop_start+0x26>#1 E
84: 48 83 c1 01 add rcx,0x1 #1 E
88: 79 da jns 64 <loop_start>#1 E
Префикс REX test rdx,rdx находится в том же блоке, что и DIV, так что это должно разрушить кэш UOP. Еще один байт заполнения поместил бы его в следующий блок 32B, что имело бы смысл. Возможно, результаты OP неверны, или, возможно, префиксы не учитываются, и имеет значение позиция байта кода операции. Возможно, это имеет значение, или, может быть, ветвь test+ с макросами перенесена в следующий блок?
Макрослияние происходит за границей строки L1I-кэша 64B, поскольку оно не попадает на границу между инструкциями.
Слияние макросов не происходит, если первая инструкция заканчивается байтом 63 строки кэша, а вторая инструкция является условной ветвью, которая начинается в байте 0 следующей строки кэша. - Руководство по оптимизации Intel, 2.3.2.1.
Или, может быть, с коротким кодированием для одного прыжка или другого все иначе?
Или, может быть, уничтожение кэша UOP не имеет к этому никакого отношения, и это нормально, если он быстро декодируется, что и происходит благодаря этому выравниванию. Такое количество отступов едва помещает конец UCOMISD в новый блок 16B, так что, возможно, это фактически повышает эффективность, позволяя ему декодироваться с другими инструкциями в следующем выровненном блоке 16B. Однако я не уверен, что блок предварительного декодирования 16B (поиск по длине команды) или блок декодирования 32B должны быть выровнены.
Я также задавался вопросом, часто ли процессор переключается с кэша UOP на устаревшее декодирование. Это может быть хуже, чем работать с устаревшим декодированием все время.
Согласно руководству по микроархам Agner Fog, переключение с декодеров в кэш UOP или наоборот занимает цикл. Intel говорит:
Когда микрооперации не могут быть сохранены в декодированном ICache из-за этих ограничений, они доставляются из устаревшего конвейера декодирования. Как только микрооперации доставляются из устаревшего конвейера, выборка микроопераций из декодированного ICache может возобновиться только после следующей микрооперации ветвления. Частые переключения могут повлечь за собой штраф.
Источник, который я собрал + разобрал:
.skip 0x5e
nop
# this is 0x5F
#nop # OP needed 1B of padding to reach a 32B boundary
.skip 5, 0x90
.globl loop_start
loop_start:
.L37:
pxor %xmm0, %xmm0
cvtsi2sdq %rcx, %xmm0
ucomisd %xmm0, %xmm6
jb .Loop_exit // Exit the loop
.L20:
xorl %edx, %edx
movq %rbx, %rax
divq %rcx
testq %rdx, %rdx
je .Lnot_prime // Failed divisibility test
addq $1, %rcx
jns .L37
.skip 200 # comment this to make the jumps rel8 instead of rel32
.Lnot_prime:
.Loop_exit:
Из того, что я вижу в вашем алгоритме, вы, безусловно, не так уж много можете сделать, чтобы улучшить его.
Проблема, с которой вы сталкиваетесь, вероятно, заключается не в том, что ветвь находится в выровненной позиции, хотя это все еще может помочь, ваша текущая проблема, скорее всего, конвейерный механизм.
Когда вы пишете две инструкции одна за другой, такие как:
mov %eax, %ebx
add 1, %ebx
Чтобы выполнить вторую инструкцию, первая должна быть завершена. По этой причине компиляторы склонны смешивать инструкции. Скажем, вам нужно установить %ecx к нулю, вы можете сделать это:
mov %eax, %ebx
xor %ecx, %ecx
add 1, %ebx
В этом случае mov и xor оба могут быть выполнены параллельно. Это ускоряет процесс... Число команд, которые могут обрабатываться параллельно, сильно различается между процессорами (Xeon, как правило, лучше в этом).
Ветвь добавляет еще один параметр, где лучшие процессоры могут начать выполнять обе стороны ветви (истину и ложь...) одновременно. Но на самом деле большинство процессоров догадаются и надеются, что они правы.
Наконец, очевидно, что преобразование sqrt() результат в целое число сделает все намного быстрее, так как вы избежите всего этого бессмысленного в коде SSE2, который значительно медленнее, если используется только для преобразования + сравните, когда эти две инструкции можно выполнить с целыми числами.
Теперь... вы, вероятно, все еще задаетесь вопросом, почему выравнивание не имеет значения с целыми числами. Дело в том, что если ваш код помещается в кэш инструкций L1, то выравнивание не имеет значения. Если вы потеряете кэш L1, то он должен перезагрузить код, и именно здесь выравнивание становится весьма важным, поскольку в каждом цикле он может загружать бесполезный код (возможно, 15 байт бесполезного кода...), а доступ к памяти все еще мертв медленный.
Разница в производительности может быть объяснена различными способами, которыми механизм кодирования команд "видит" инструкции. Процессор читает инструкции по частям (было на core2 16 байт, я полагаю) и пытается дать разные суперскалярные единицы измерения. Если инструкции находятся на границах или заказаны маловероятно, блоки в одном ядре могут голодать довольно легко.