Промахи TLB: шесть гигабайт случайного доступа

Что болело

Оффлайн-джоб строит хеш-таблицу на 400 млн записей, около 6 ГиБ, и потом делает по ней 2 млрд случайных поисков. Прогон занимал 3,1 с, и это казалось нормой, пока я не прикинул нижнюю границу: при латентности памяти ~90 нс и случайном доступе выходило около 1,8 с. Полтора раза куда-то девались.

Гипотеза про кеш

Случайный доступ к 6 ГиБ - очевидный кандидат на промахи кеша последнего уровня. perf stat это подтвердил, но не до конца:

$ perf stat -e cycles,instructions,LLC-load-misses,dTLB-load-misses ./probe
   9 412 004 551      cycles
   3 010 882 110      instructions   #  0,32  insn per cycle
   1 904 221 013      LLC-load-misses
     410 882 004      dTLB-load-misses

Промахи LLC ожидаемы - по одному почти на каждый поиск. Но dTLB-load-misses в 410 млн меня остановили: это промах буфера трансляции адресов, и каждый из них запускает обход таблицы страниц, отдельные обращения к памяти ещё до самого доступа к данным. 0,32 инструкции за такт - процессор почти всё время ждёт, и часть этого ожидания не LLC, а именно обход страниц.

Обход страниц

Таблица на 6 ГиБ при страницах по 4 КиБ - это 1,5 млн страниц. TLB второго уровня держит порядка полутора тысяч записей; при случайном доступе почти каждый поиск промахивается и мимо TLB, и мимо кеша страничных таблиц. Доля циклов в обходе видна отдельным счётчиком:

$ perf stat -e cycles,dtlb_load_misses.walk_active ./probe
   9 410 118 220      cycles
   2 931 004 880      dtlb_load_misses.walk_active   # 31,1% backend cycles

Треть тактов движок памяти занят обходом таблицы страниц. Это не доступ к данным и не LLC - это накладная работа MMU, которую видно только по TLB-счётчикам, а в профиле по символам она размазана по той же функции поиска и выглядит как «медленный доступ».

Большие страницы

Лечится укрупнением страниц: на 2 МиБ ту же область покрывают 3072 страницы вместо полутора миллионов, и они почти целиком помещаются в TLB. Таблицу я кладу в анонимную область и прошу ядро про крупные страницы явно:

size_t n = 6ULL << 30;
void *p = mmap(NULL, n, PROT_READ | PROT_WRITE,
               MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
madvise(p, n, MADV_HUGEPAGE);   /* THP для этой области */
/* и выравнивание базы на 2 МиБ, иначе край области дробится на 4К */

Полагаться на прозрачные THP по умолчанию я не стал: MADV_HUGEPAGE включает их для области адресно, а базу mmap я выровнял на 2 МиБ сам, иначе ядро раздаёт крупные страницы только с первой выровненной границы, а хвосты оставляет по 4 КиБ. Проверять, что страницы действительно крупные, надо по /proc/pid/smaps, по строке AnonHugePages, а не по факту вызова madvise - он лишь совет.

Числа

Стенд: x86-64, 8 ядер / 32 ГиБ, ядро 6.6, gcc 13.2, регулятор performance, турбо выключено, пять прогонов, медиана, первый - прогрев.

Промахи TLB упали в 19 раз, обход страниц почти исчез, и полтора раза вернулись. LLC-промахи при этом не изменились - данные как лежали в шести гигабайтах, так и лежат, и каждый случайный поиск по-прежнему мимо кеша; просто теперь процессор не платит ещё и за трансляцию адреса сверху.

Где я ошибся

Я чуть не ушёл оптимизировать раскладку данных под LLC - менять коэффициент заполнения, пробовать открытую адресацию плотнее. Это дало бы проценты, потому что реальная потеря была не в кеше данных, а в кеше трансляций. Разделил эти два промаха ровно счётчик dtlb_load_misses.walk_active: пока не посмотришь на долю тактов именно в обходе страниц, LLC-промахи и TLB-промахи сливаются в одно «медленно читает память». Теперь на любой структуре больше пары гигабайт со случайным доступом я сначала смотрю TLB, а уже потом раскладку.