Воюю с очередями ваще не каждый день, часть 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'ами быстрее 🙂

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

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