Есть ли штраф, когда база + смещение находятся на другой странице, чем база?
Время выполнения для этих трех фрагментов:
pageboundary: dq (pageboundary + 8)
...
mov rdx, [rel pageboundary]
.loop:
mov rdx, [rdx - 8]
sub ecx, 1
jnz .loop
И это:
pageboundary: dq (pageboundary - 8)
...
mov rdx, [rel pageboundary]
.loop:
mov rdx, [rdx + 8]
sub ecx, 1
jnz .loop
И это:
pageboundary: dq (pageboundary - 4096)
...
mov rdx, [rel pageboundary]
.loop:
mov rdx, [rdx + 4096]
sub ecx, 1
jnz .loop
На 4770K примерно 5 циклов на итерацию для первого фрагмента и примерно 9 циклов на итерацию для второго фрагмента, а затем 5 циклов для третьего фрагмента. Они оба получают доступ к одному и тому же адресу, который выровнен по 4K. Во втором фрагменте только вычисление адреса пересекает границу страницы: rdx а также rdx + 8 не принадлежат той же странице, нагрузка по-прежнему выравнивается. С большим смещением он снова возвращается к 5 циклам.
Как этот эффект работает в целом?
Направление результата от загрузки через инструкцию ALU как это:
.loop:
mov rdx, [rdx + 8]
or rdx, 0
sub ecx, 1
jnz .loop
Делает это занимает 6 циклов за итерацию, что имеет смысл как 5+1. Reg+8 должен быть особой быстрой загрузкой, а AFAIK занимает 4 цикла, так что даже в этом случае, кажется, есть некоторый штраф, но только 1 цикл.
Такой тест был использован в ответ на некоторые комментарии:
.loop:
lfence
; or rdx, 0
mov rdx, [rdx + 8]
; or rdx, 0
; uncomment one of the ORs
lfence
sub ecx, 1
jnz .loop
Ввод or перед mov делает цикл быстрее, чем без каких-либо or, положив or после mov делает цикл медленнее.
2 ответа
Правило оптимизации: в связанных с указателем структурах данных, таких как связанные списки / деревья, поместите next или же left / right указатели в первых 16 байтах объекта. malloc обычно возвращает 16-байтовые выровненные блоки (alignof(maxalign_t)), так что указатели ссылок будут на той же странице, что и начало объекта.
Любой другой способ убедиться, что важные элементы структуры находятся на той же странице, что и начало объекта, также будет работать.
Семейство Sandybridge обычно имеет 5-тактовую задержку использования нагрузки L1d, но есть особый случай для погони за указателем с небольшими положительными смещениями в режимах base+disp.
Семейство Sandybridge имеет 4-х тактовую задержку использования нагрузки для [reg + 0..2047] режимы адресации, когда базовый регистр является результатом mov загрузить, а не инструкцию ALU. Или штраф, если reg+disp находится на другой странице, чем reg ,
На основании этих результатов испытаний на Haswell и Skylake (и, возможно, оригинальных SnB, но мы не знаем), кажется, что все следующие условия должны быть выполнены:
- база рег происходит от другой нагрузки. (Грубая эвристика для погони за указателем, и обычно означает, что задержка загрузки, вероятно, является частью цепочки dep). Если объекты обычно размещаются, не пересекая границу страницы, то это хорошая эвристика. (Очевидно, HW может определить, с какого исполнительного устройства пересылается вход.)
- Режим адресации
[reg]или же[reg+disp8/disp32], ( Или индексированная загрузка с регистром индекса с нулевым нулем! Обычно практически бесполезна, но может дать некоторое представление о стадии выпуска / переименования, преобразующей мопы загрузки.) - смещение <2048. то есть все биты выше бита 11 равны нулю (условие HW может проверять без полного целочисленного сумматора / компаратора.)
(Скайлэйк, но не Хэсвелл / Бродвелл): последняя загрузка не была повторной попыткой. (Таким образом, base = результат 4 или 5 циклической загрузки, он будет пытаться выполнить быстрый путь. Но base = результат 10-тактной повторной загрузки, не будет. Штраф на SKL, кажется, 10 против 9 на HSW).
Я не знаю, имеет ли значение последняя попытка загрузки на том порту загрузки, или это действительно то, что произошло с загрузкой, которая произвела этот ввод. Возможно, эксперименты, преследующие две параллельные цепи депо, могли бы пролить свет; Я только попробовал один указатель, преследующий цепочку деп со смешанным смещением изменения страницы и не изменения страницы.
Если все это верно, порт загрузки предполагает, что окончательный эффективный адрес будет на той же странице, что и базовый регистр. Это полезная оптимизация в реальных случаях, когда задержка при использовании нагрузки формирует депонированную цепочку переноса, как для связанного списка или двоичного дерева.
объяснение микроархитектуры (моя лучшая догадка при объяснении результата, а не из публикаций Intel):
Кажется, что индексирование L1dTLB находится на критическом пути для задержки загрузки L1d. Начало этого 1 цикла раньше (без ожидания вывода сумматора для вычисления конечного адреса) сокращает цикл полного процесса индексации L1d с использованием младших 12 битов адреса, а затем сравнивает 8 тегов в этом наборе с высоким биты физического адреса, создаваемого TLB. (L1d от Intel - это VIPT 8-way 32kiB, поэтому у него нет проблем с наложением имен, поскольку все биты индекса берутся из младших 12 битов адреса: смещение на странице, одинаковое как для виртуального, так и для физического адреса. младшие 12 бит переводят бесплатно из вирт в физ.)
Поскольку мы не обнаруживаем эффекта пересечения 64-байтовых границ, мы знаем, что порт загрузки добавляет смещение перед индексацией кэша.
Как предполагает Хади, представляется вероятным, что, если есть выход из бита 11, порт загрузки позволяет завершить загрузку неправильного TLB, а затем восстанавливает его, используя обычный путь. (В HSW общая задержка загрузки = 9. В SKL общая задержка загрузки может составлять 7,5 или 10).
Теоретически возможно прерывание сразу и повторная попытка в следующем цикле (чтобы сделать 5 или 6 циклов вместо 9), но помните, что порты загрузки конвейерны с пропускной способностью 1 на тактовую частоту. Планировщик ожидает, что в следующем цикле сможет отправить еще один моп на порт загрузки, а семейство Sandybridge стандартизирует задержки для всего 5 циклов и меньше. (Нет 2-х тактных инструкций).
Я не проверял, помогают ли 2M огромные страницы, но, вероятно, нет. Я думаю, что аппаратное обеспечение TLB достаточно простое, поэтому оно не может распознать, что индекс на 1 страницу выше будет выбирать ту же запись. Так что, вероятно, медленная повторная попытка выполняется в любое время, когда смещение пересекает границу 4 КБ, даже если она находится на той же огромной странице. (Загрузка с разделением страниц работает следующим образом: если данные фактически пересекают границу 4 КБ (например, 8-байтная загрузка со страницы 4), вы платите штраф за разделение страниц, а не только за разделение строк кэша, независимо от огромных страниц)
Руководство по оптимизации Intel описывает этот особый случай в разделе 2.4.5.2 Lache DCache (в разделе Sandybridge), но не упоминает никаких ограничений на другие страницы или того факта, что оно предназначено только для отслеживания указателей, и не происходит, когда есть инструкция ALU в цепочке dep.
(Sandybridge)
Table 2-21. Effect of Addressing Modes on Load Latency
-----------------------------------------------------------------------
Data Type | Base + Offset > 2048 | Base + Offset < 2048
| Base + Index [+ Offset] |
----------------------+--------------------------+----------------------
Integer | 5 | 4
MMX, SSE, 128-bit AVX | 6 | 5
X87 | 7 | 6
256-bit AVX | 7 | 7
(remember, 256-bit loads on SnB take 2 cycles in the load port, unlike on HSW/SKL)
Текст вокруг этой таблицы также не упоминает ограничения, существующие в Haswell/Skylake, и может также существовать в SnB (я не знаю).
Возможно, у Sandybridge нет таких ограничений, и Intel не задокументировала регрессию Haswell, или Intel просто не задокументировала ограничения в первую очередь. Таблица довольно определенно говорит о том, что режим адресации всегда имеет задержку 4с со смещением = 0..2047.
@ Эксперимент Гарольда по размещению инструкции ALU в качестве части цепочки зависимостей загрузки / использования указателя подтверждает, что именно этот эффект вызывает замедление: ALU insn уменьшил общую задержку, эффективно давая такую инструкцию, как and rdx, rdx отрицательная дополнительная задержка при добавлении к mov rdx, [rdx-8] dep chain в этом конкретном случае пересечения страниц.
Предыдущие предположения в этом ответе включали предположение, что использование задержки в ALU по сравнению с другой нагрузкой определяло задержку. Это было бы супер странно и потребовало бы заглядывать в будущее. С моей стороны это было неверным толкованием эффекта добавления инструкции ALU в цикл. (Я не знал о влиянии 9-ти циклов на пересечение страниц и думал, что механизм HW - это быстрый путь пересылки для результата внутри порта загрузки. Это имеет смысл.)
Мы можем доказать, что важен источник ввода базы данных, а не место назначения результата загрузки: сохраняйте один и тот же адрес в двух разных местах, до и после границы страницы. Создайте цепочку депозита ALU => load => load и убедитесь, что это вторая нагрузка, которая уязвима к этому замедлению / может извлечь выгоду из ускорения с помощью простого режима адресации.
%define off 16
lea rdi, [buf+4096 - 16]
mov [rdi], rdi
mov [rdi+off], rdi
mov ebp, 100000000
.loop:
and rdi, rdi
mov rdi, [rdi] ; base comes from AND
mov rdi, [rdi+off] ; base comes from a load
dec ebp
jnz .loop
... sys_exit_group(0)
section .bss
align 4096
buf: resb 4096*2
Приурочен с Linux perf на скл и7-6700к.
off = 8, предположение верно, и мы получаем общую задержку = 10 циклов = 1 + 5 + 4. (10 циклов за итерацию).off = 16,[rdi+off]нагрузка медленная, и мы получаем 16 циклов / iter = 1 + 5 + 10. (Похоже, штраф на SKL выше, чем на HSW)
С изменением порядка загрузки [rdi+off] сначала загрузите), это всегда 10 c независимо от выключенного =8 или выключенного =16, поэтому мы доказали, что mov rdi, [rdi+off] не пытается спекулятивный быстрый путь, если его ввод происходит из инструкции ALU.
Без and, а также off=8 мы получаем ожидаемое 8c за iter: оба используют быстрый путь. (@harold подтверждает, что HSW также получает 8 здесь).
Без and , а также off=16 мы получаем 15 c за iter: 5 + 10. mov rdi, [rdi+16] пробует быстрый путь и терпит неудачу, принимая 10с. затем mov rdi, [rdi] не выполняет быстрый путь, потому что его ввод не удался. (HSW @ harold берет здесь 13: 4 + 9. Таким образом, это подтверждает, что HSW делает попытку быстрого пути, даже если последний отказал в быстром пути, и что штраф за отказ в быстром пути действительно составляет всего 9 на HSW против 10 на SKL)
К сожалению, SKL не осознает этого [base] без смещения всегда можно безопасно использовать быстрый путь.
На скл, причем всего mov rdi, [rdi+16] в цикле средняя задержка составляет 7,5 циклов. Основываясь на тестах с другими микшерами, я думаю, что он чередуется между 5 c и 10c: после загрузки 5 c, которая не попыталась выполнить быстрый путь, следующая попытается и потерпит неудачу, взяв 10c. Это заставляет следующую загрузку использовать безопасный путь 5с.
Добавление регистра с нулевым индексом фактически ускоряет его в этом случае, когда мы знаем, что быстрый путь всегда будет неудачным. Или не используя базовый регистр, как [nosplit off + rdi*1] к которому собирается NASM 48 8b 3c 3d 10 00 00 00 mov rdi,QWORD PTR [rdi*1+0x10], Обратите внимание, что это требует disp32, так что это плохо для размера кода.
Также имейте в виду, что индексированные режимы адресации для операндов с микроплавкой памятью в некоторых случаях не ламинированы, в то время как режимы base+disp - нет. Но если вы используете чистые нагрузки (например, mov или же vbroadcastss), нет ничего плохого в режиме индексированной адресации. Однако использование дополнительного обнуленного регистра не очень хорошо.
Я провел достаточное количество экспериментов на Haswell, чтобы точно определить, когда спекулятивно выдаются загрузки памяти, прежде чем эффективный адрес будет полностью рассчитан. Эти результаты также подтверждают догадки Петра.
Я изменил следующие параметры:
- Смещение от
pageboundary, Используемое смещение одинаково в определенииpageboundaryи инструкция по загрузке. - Знак смещения либо +, либо -. Знак, используемый в определении, всегда противоположен знаку, используемому в инструкции загрузки.
- Выравнивание
pageboundaryв исполняемом двоичном файле.
На всех следующих графиках ось Y представляет задержку нагрузки в циклах активной зоны. Ось X представляет конфигурацию в форме NS1S2, где N - это смещение, S1 - это знак смещения, используемого в определении, а S2 - это знак, используемый в инструкции загрузки.
На следующем графике показано, что нагрузки выдаются до расчета эффективного адреса, только когда смещение положительное или равно нулю. Обратите внимание, что для всех смещений от 0 до 15 базовый адрес и эффективный адрес, используемые в инструкции загрузки, находятся в пределах одной страницы 4K.
На следующем графике показана точка, где этот шаблон изменяется. Изменение происходит по смещению 213, которое является наименьшим смещением, когда базовый адрес и эффективный адрес, используемые в инструкции загрузки, находятся в разных страницах 4K.
Еще одно важное наблюдение, которое можно сделать из предыдущих двух графиков, заключается в том, что даже если базовый адрес указывает на набор кеша, отличный от эффективного, штраф не налагается. Таким образом, кажется, что набор кеша открывается после вычисления эффективного адреса. Это указывает на то, что задержка попадания DTLB L1 составляет 2 цикла (то есть, для получения тега L1 D требуется 2 цикла, но требуется только 1 цикл, чтобы открыть набор массивов данных кэша и набор массивов тегов кэша (что происходит в параллели).
Следующий график показывает, что происходит, когда pageboundary выравнивается по границе страницы 4K. В этом случае любое смещение, отличное от нуля, приведет к тому, что базовый и эффективный адреса будут находиться на разных страницах. Например, если базовый адрес pageboundary 4096, то базовый адрес pageboundary в инструкции загрузки используется смещение 4096, которое, очевидно, находится на другой странице 4K для любого ненулевого смещения.
На следующем графике показано, что шаблон снова изменяется, начиная со смещения 2048. В этот момент нагрузки никогда не выдаются до расчета действующего адреса.
Этот анализ можно подтвердить, измерив количество мопов, отправленных на порты нагрузки 2 и 3. Общее количество мопов с нагрузкой в отставке составляет 1 миллиард (что равно количеству итераций). Однако, когда измеренная задержка нагрузки составляет 9 циклов, количество загрузок, отправленных на каждый из двух портов, составляет 1 миллиард. Также, когда задержка загрузки составляет 5 или 4 такта, количество загрузок, отправленных на каждый из двух портов, составляет 0,5 миллиарда. Так что-то вроде этого будет происходить:
- Модуль загрузки проверяет, является ли смещение неотрицательным и меньше 2048. В этом случае он выдаст запрос на загрузку данных с использованием базового адреса. Также начнется расчет эффективного адреса.
- В следующем цикле вычисление эффективного адреса завершено. Если выясняется, что загрузка выполняется на другую страницу 4K, модуль загрузки ожидает завершения выполненной загрузки, а затем отбрасывает результаты и воспроизводит загрузку. В любом случае, он снабжает кэш данных заданным индексом и смещением строки.
- В следующем цикле выполняется сравнение тегов, и данные передаются в буфер загрузки. (Я не уверен, будет ли прервана адресно-спекулятивная нагрузка в случае пропуска в L1 D или DTLB.)
- В следующем цикле буфер загрузки получает данные из кэша. Если он должен отбрасывать данные, он отбрасывается и говорит диспетчеру воспроизвести загрузку с отключенной для него спекуляцией адресом. В противном случае данные записываются обратно. Если для следующей инструкции требуются данные для вычисления ее адреса, она получит данные в следующем цикле (поэтому она будет отправлена в следующем цикле, если все ее другие операнды будут готовы).
Эти шаги объясняют наблюдаемые задержки в 4, 5 и 9 циклах.
Может случиться так, что целевая страница - это огромная страница. Единственный способ для загрузочной единицы узнать, указывают ли базовый адрес и эффективный адрес на одну и ту же страницу при использовании больших страниц, - это заставить TLB предоставить загрузочной единице размер страницы, к которой осуществляется доступ. Затем блок загрузки должен проверить, находится ли эффективный адрес на этой странице. В современных процессорах при пропадании TLB используется специальное аппаратное обеспечение для просмотра страниц. В этом случае я думаю, что модуль загрузки не будет предоставлять индекс набора кеша и смещение строки кеша в кеш данных и будет использовать фактический эффективный адрес для доступа к TLB. Для этого требуется, чтобы аппаратные средства просмотра страниц различали нагрузки с умозрительными адресами и другие нагрузки. Только если этот другой доступ пропущен, TLB будет проходить по странице. Теперь, если целевая страница оказалась огромной страницей, и она является хитом в TLB, возможно, можно сообщить единице загрузки, что размер страницы больше 4 КБ или, возможно, даже точного размера страницы. Затем блок нагрузки может принять лучшее решение относительно того, следует ли повторно воспроизводить нагрузку. Однако эта логика должна занимать не более времени, чтобы (потенциально неверные) данные достигли буфера загрузки, выделенного для нагрузки. Я думаю, что на этот раз только один цикл.