Используйте 2M огромных страниц для диапазонов адресов, которые заполнены «горячими» данными, которые ядро не может с пользой поменять на любые / многие фрагменты 4k. Это уменьшит количество пропусков TLB, но затрачивает дополнительную физическую память, если на огромной странице есть 4k кусков, которые не являются горячими.
Linux делает это прозрачно для анонимных страниц (https://www.kernel.org/doc/Documentation/vm/transhuge.txt),, но вы можете использовать madvise(MADV_HUGEPAGE) на тех страницах, которые, как вы знаете, стоят того, чтобы заставить ядро дефрагментировать физическую память, даже если это не так значение по умолчанию в /sys/kernel/mm/transparent_hugepage/defrag. (Вы можете посмотреть на /proc/PID/smaps, чтобы увидеть, сколько прозрачных огромных страниц используется для любого данного отображения.)
Исходя из того, что вы опубликовали в своем ответе: заказанный набор набора nodesToVisit даст вам наибольшую локальность, но может быть слишком дорогим для обслуживания . Множественный доступ в пределах одной и той же строки 64-байтового кэша на намного дешевле, чем возврат к нему позже, после того как он был удален из кэша L3 и должен снова поступить из DRAM.
Если в вашем наборе есть много адресов для посещения, выполнение одного прохода радикальной сортировки в 2M сегмента даст вам местоположение в пределах одной огромной страницы. 2M также меньше размера кэша L3, поэтому вы, вероятно, получите некоторые попадания в кэш при посещении нескольких объектов в одной строке кэша, даже если вы не ударили их спина к спине.
В зависимости от того, насколько велик ваш Set, использование такого количества указателей, даже для их частичной сортировки, может не стоить занимаемого трафика. Но, вероятно, есть какое-то приятное место: взять окно данных и, по крайней мере, частично отсортировать его. Использование указателей до , они изгоняются из кеша - это хорошо.
Предварительная выборка SW может инициировать просмотр страницы, чтобы избежать пропуска TLB, поэтому вы можете _mm_prefetch(_MM_HINT_T2) один адрес из следующего сегмента 2M перед запуском текущего блока. См. также Примеры предварительной выборки? . Я не проверял это, но это может работать хорошо. Это не поможет с ошибками страницы: предварительная выборка с не отображенной страницы не приведет к сбою страницы, и вы не захотите запускать фактическую PF, пока не будете готовы коснуться страницы.
Предложение MSalter попросить ОС выполнить предварительную выборку и подключить следующую страницу, интересно (я думаю, madvise(MADV_WILLNEED) - это эквивалент Linux), но системный вызов будет медленным без какой-либо выгоды, если страница уже была отображена + подключена к HW страница таблицы. Там нет инструкции x86 asm, которая просто спрашивает, отображается ли страница без ошибок, если это не так, поэтому я не могу придумать, как эффективно решить не вызывать ее. И кстати, я думаю, что Linux разбивает прозрачные огромные страницы на 4k обычных страниц для постраничного ввода / вывода. Но не пишите большой цикл, который просто делает _mm_prefetch() или madvise на всех страницах 4k в блоке 2M; это, вероятно, отстой. Часть prefetcht2, вероятно, просто приведет к тому, что лишние запросы на предварительную выборку будут отброшены.
Используйте счетчики перфорации, чтобы посмотреть на количество попаданий / промахов в кэше. На процессорах Intel событие mem_load_retired.l1_miss и / или .l2_miss должно показывать, получаете ли вы попадания в кэш при доступе к самому набору, а также при обращении к этим ссылкам. Эти счетчики являются точными событиями, поэтому они должны точно отображаться в инструкции по загрузке. (например, perf record -e mem_load_retired.l2_miss ./my_program / perf report в Linux).
Мы удаляем один элемент за один раз из nodesToVisit
Я не знаю много о дизайне GC, но разве вы не можете использовать порядковый номер или tagged-pointer или что-то еще, чтобы избежать изменения самой структуры данных Set при каждом проходе GC? Если минимальное выравнивание объекта составляет 4 байта, у вас есть 2 бита для воспроизведения внизу каждого указателя. Снять их до разыменования очень дешево.
x86-64 с полными 64-битными указателями в настоящее время требует, чтобы верхние 16 были расширением знака нижних 48. Таким образом, вы можете использовать биты (16 бит или, возможно, только верхний байт), если вы повторно канонизируете указатели. (Повторите расширение знака или просто обнулите старшие 16 битов, если хотите использовать указатели на пространство пользователя; Linux использует макет виртуальной машины с половиной ядра, поэтому адреса пространства пользователя всегда находятся в нижней половине виртуального адресного пространства. IDK what Windows делает.)
На x86-64 вы можете рассмотреть возможность использования x32 ABI (32-разрядные указатели в длинном режиме) , если 4 ГБ адресного пространства достаточно , особенно если вы нажимаете пределы физической памяти и обмен. Меньшие указатели означают меньшие структуры данных, таким образом, половина площади кеша.
Некоторые системы Linux построены без поддержки ядра для x32, однако, только классический x86-64 и обычно 32-битный режим. Но если это работает в ваших системах, рассмотрите gcc -mx32.