Правило оптимизации: в связанных с указателем структурах данных, таких как связанные списки / деревья, поместите указатели 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, но мы не знаем), он появляетсячто должны выполняться все следующие условия:
- base reg происходит от другой нагрузки .(Грубая эвристика для погони за указателем, и обычно означает, что задержка загрузки, вероятно, является частью цепочки dep).Если объекты обычно размещаются, не пересекая границу страницы, то это хорошая эвристика.(Очевидно, HW может определить, с какого исполнительного устройства пересылается вход.)
- Режим адресации -
[reg] или [reg+disp8/disp32].( Или индексированная нагрузка с регистром индекса с нулевым нулем! Обычно практически не полезна, но может дать некоторое представление о стадии преобразования проблемы / переименования, изменяющей мопы.) - смещение<2048 </strong>.т.е. все биты выше бита 11 равны нулю (условие HW может проверить без целочисленного сумматора / компаратора.)
( Skylake, но не Haswell / Broadwell ): последняя загрузкане был повторным путем.(Таким образом, base = результат 4 или 5 циклической нагрузки, он будет пытаться выполнить быстрый путь. Но base = результат 10-тактной повторной загрузки не получится. Казалось бы, штраф в SKL равен 10 против 9 в HSW).
Я не знаю, имеет ли значение последняя попытка загрузки на том порту загрузки, или это действительно то, что произошло с нагрузкой, которая произвела этот ввод.Возможно, эксперименты, преследующие две параллельные цепи депо, могли бы пролить свет;Я пробовал только один указатель, преследующий цепочку деп со смешанным смещением при изменении страницы и без изменения страницы.
Если все это верно, порт загрузки предполагает , что окончательный эффективный адрес будет находиться на той же странице, что и базовый регистр. Это полезная оптимизация в реальных случаях, когда задержка при использовании нагрузки формирует переносимую цепочку dep, как длясвязанный список или двоичное дерево.
микроархитектурное объяснение (моя лучшая догадка при объяснении результата, а не из публикаций 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 страницу выше все равно выберет ту же запись.Так что, вероятно, медленная повторная попытка выполняется в любое время, когда смещение пересекает границу 4k, даже если это на той же огромной странице.(Загрузка с разделением страниц работает следующим образом: если данные фактически пересекают границу 4 КБ (например, 8-байтная загрузка со страницы 4), вы платите штраф за разделение страниц, а не только за разделение строк кэша, независимо от огромных страниц)
Руководство по оптимизации Intel документирует этот особый случай в разделе 2.4.5.2 L1 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 просто не сделала этого ».В первую очередь, документируйте ограничения.Таблица довольно определенно говорит о том, что режим адресации всегда имеет задержку 4c со смещением = 0..2047.
@ Эксперимент Гарольда, в котором инструкция ALU помещается как часть указателя загрузки / использования.погоня за цепочкой зависимостей подтверждает, что именно этот эффект вызывает замедление: ALU insn уменьшил общую задержку, фактически давая команду, такую как and rdx, rdx отрицательная инкрементная задержка при добавлении в цепочку mov rdx, [rdx-8] dep в этом конкретном переходе страницыcase.
Предыдущие предположения в этом ответе включали предположение, что использование задержки результат в ALU против другой нагрузки было тем, что определяло задержку.Это было бы супер странно и потребовало бы заглядывать в будущее.С моей стороны это было неверным толкованием эффекта добавления инструкции ALU в цикл.(Я не знал о эффекте 9-ти циклов при пересечении страниц, и думал, что механизм HW - это быстрый путь пересылки для результата внутри порта загрузки. Это имело бы смысл.)
Мы можем доказать, что важен источник базового ввода reg, а не место назначения результата загрузки. : Хранить один и тот же адрес в 2 разных местах, до и после границы страницы.Создайте цепочку депозита 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
Timed with Linuxperf на SKL i7-6700k.
off = 8, предположение верно, и мы получаем общую задержку = 10 циклов = 1 + 5 + 4. (10 циклов на итерацию).
off = 16, загрузка [rdi+off] медленная, и мы получаем 16 циклов / макс. = 1 + 5 + 10. (На SKL штраф выше, чем на HSW)
При обратном порядке загрузки (сначала выполняется загрузка [rdi+off]), он всегда равен 10c независимо от выключенного = 8 или выключенного = 16, поэтому мы доказали, что mov rdi, [rdi+off]не пытается спекулятивный быстрый путь, если его ввод происходит из инструкции ALU.
Без and и off=8 мы получаем ожидаемые 8c на итерацию: оба используют быстрый путь.(@harold подтверждает, что HSW также получает здесь 8).
Без and и off=16 мы получаем 15c за итерацию: 5 + 10 .mov rdi, [rdi+16] пробует быстрый путь и терпит неудачу, принимая 10c.Тогда mov rdi, [rdi] не пытается выполнить быстрый путь, потому что его ввод не удался.( @Wharold's HSW занимает здесь 13: 4 + 9 . Таким образом, это подтверждает, что HSW делает попытку быстрого пути, даже если последний отказал в быстром пути, и что штраф за отказ в быстром пути действительно составляет всего 9 наHSW против 10 на SKL)
К сожалению, SKL не осознает, что [base] без смещения всегда может безопасно использовать быстрый путь.
На SKL, простоmov rdi, [rdi+16] в цикле, средняя задержка составляет 7,5 циклов.Основываясь на тестах с другими микшерами, я думаю, что он чередуется между 5c и 10c: после загрузки 5c, которая не пыталась выполнить быстрый путь, следующая попытается и терпит неудачу, принимая 10c.Это заставляет следующую загрузку использовать безопасный путь 5c.
Добавление регистра с нулевым индексом фактически ускоряет его в этом случае, когда мы знаем, что быстрый путь всегда будет давать сбой.Или без использования базового регистра, например [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), нет ничего плохого в режиме индексированной адресации.Использование дополнительного обнуленного регистра не очень хорошо.