Воюю с очередями каждый день, часть N

В какой-то момент умудрился увидеть задержку в 1 микросек, но уже не помню, при каких условиях и как вообще так. Больше я её не видел (спойлер: ещё увижу)
В целом, замеры очень шумные (медиана задержек может скакать в 3 раза) — долго с этим боролся
* Научился изолировать потоки под свои нечистые дела
* Мне раскрыли глаза на особенности устройства моих xeon'ов: на одном кристалле находятся два модуля по 8 ядер, а я пинился так, что потоки оказывались в разных модулях. Кеш-миссы свалились с 37% до 12%, пропускная способность подросла где-то на 50-60%
* Уложил все данные в один шмат памяти (до этого было 3: по штуке на вспомогательные очереди, 1 непосредственно с данными) — шиш мне это дало
* Вернулся к гипнотизированию flamegraph'ов. Поймал случай с хорошими и плохими задержками. (Сейчас стоит вспомнить, что я рассматриваю MPSC применение) Увидел, что у consumer'а ухудшается часть free.enqueue(), а у producer'а — free.dequeue() (см. выше). Более того, во вспомогательных очередях есть функция catchup, которая вызывается, если dequeue убежал за enqueue (случается с FAA-очередями). В хорошем прогоне эта функция не светится, в плохом — становится очень заметной

Вывод. Если consumer не справляется, всё начинает идти пи... плохо. Я пытался от этого отгородиться, напихав producer'ам nop'ов, но их оказалось недостаточно, иногда — вообще недостаточно. 2000 nop'ов против 1000 nop'ов — пик 1 и 2 соответственно

Что делать. Раз страдать начинает очередь free, разгонять надо её. Ещё до этого у меня была мысль, что именно очередь свободных индексов — оверкилл. У нас тут множество элементов от 0 до n-1. По-любому можно сделать проще

Что делать ещё. До сих пор это MPMC очередь. Когда дожму с неё всё, что смогу, пойду исследовать, что мне может дать релаксация до MPSC случая

Сайд-квест 1. Насколько я знаю, на x64 размер кеш-линии это 64 байта. Но в референсной реализации выравнивание штуков было по 128 байт. На практике выравнивание действительно надо делать по 128, потому что на 64 перформанс проседает. Интересно, почему так

Сайд-квест 2. Во вспомогательных очередях индексы самой очереди перемешиваются так, чтобы как можно дольше не заходить в одну кеш-линию. Интересно, что будет, если сменить условие на "как можно дольше не заходить на одну кеш-линию, оставаясь на одной странице"

Воюю с очередями ваще не каждый день, часть N + 1
Пошёл выполнять сайд-квест 2 (потому что на основной квест-линии надо думать)

Итак, у нас есть две вспомогательные очереди, которые держат индексы от 0 до n. Внутри циклический массив, собственно, индексов. Решаем вопрос, как выбрать, куда писать очередной элемент.

Тривиальное решение:

uint64_t idx = tail_++ % capacity_;

Плюс: просто
Минус: false-sharing (несколько потоков будут писать в одну кеш-линию -> инвалидировать её друг другу -> страдать)

Решение из референсной реализации очереди:
1. Возьмём uint64_t local_tail = tail_++;
2. Битово сдвинем local_tail влево на log2(CACHE_LINE_SIZE / sizeof(uint64_t)) (в цифрах: log2(128 / 8) = 4)
3. Старшие 4 бита справа от log2(capacity_) перенесём в начало
Так мы не вернёмся к элементу в первой кеш-линии, пока не дойдём до упора в capacity_
Плюс: мы не упрёмся в false-sharing
Минус: вымываем кеши на турбированной скорости, на каждом enqueue перепрыгивая через 128 байт

Решение, которое я решил опробовать:
То же, что в предыдущем, но
3. Старшие 4 бита справа от `log2(PAGE_SIZZE / sizeof(uint64_t))`перенесём в начало
Теперь мы вернёмся к элементу в первой кеш-линии уперевшись не в capacity_, а в размер страницы
Плюсы:
* Всё ещё не так страдаем от false-sharing'а, как в тривиальном случае
* Плотнее сидим в кешах
Минусы:
* Напороться на false-sharing стало легче: раз в 32 вставки (4096 / 128)
* В частности, пока непонятно, насколько хорошо будет работать для >32 одновременных producer'ов

Перф говорит, что действительно в кеши стали попадать почаще (было: пик1, стало: пик2). Но есть ли смысл?

To be continued...

Воюю с очередями ваще не каждый день, часть N + 1 (измерительная)
Что нам дало сидение на одной странице (на моём потенциально однобоком бенче)

1. Консьюмер стал дышать легче. Как выяснил раньше, консьюмер захлёбывается, если продьюсер крутит 1000 nop'ов между вставками, и страдает куда меньше при 3000 nop'ов. Решил посмотреть, как справляемся теперь с паузой в 1000 nop'ов. Медианная задержка упала с 16мкс до 2мкс. Приятно (пик1 -> пик2)

2. По задержкам интересно. Сказал бы, что медианы в районе погрешности, но пусть мой способ действительно похуже. Однако, у моего способа хвост задержек потоньше (пик3). Лучше это видно на табличках: пик4 для варианта автора, пик5 для моего. Авторский вариант (пик4) показывает себя лучше на низких квантилях, мой (пик5) — на высоких (и, внезапно, в среднем)

3. Раньше меня преследовало число 128. Теперь ещё и 512. Рисую задержки для каждого элемента (пик6). Ясно видно, что у выбросов есть периодичность. Выбросы поредее происходят раз в 128 элементов. Выбросы погуще — раз в 512. Я ВСЁ ЕЩЁ НЕ ПОНИМАЮ, ПОЧЕМУ, ЭТИ ЧИСЛА ПРЕСЛЕДУЮТ МЕНЯ, ПОМОГИТЕ. Оказывается, видимая разница в выбросах на 128 и на 512 появилась на моменте введения 3000 nop'ов (пик7), явно видно, что они плотнее. То есть, как-то это с походами в память связано. Но пока я не смог придумать, в какую формулу подставить числа, чтоб всё сложилось

4. Попытка херачить в MPSC режиме без nop'ов всё ещё гробит всё настолько, что с nop'ами быстрее 🙂

Итого, стоит ли оно того? Спорно. Высокие квантили спиленные настолько, что делают среднее лучше, меня прельщают, так что для меня — да

Что ж. Дальше придётся-таки воспользоваться так называемым умом, и написать параллельный битсет, чтобы попробовать выбросить очередь свободных индексов