Автор строит быструю lock-free очередь на C++ с нуля. Стандартный std::queue под std::mutex хорош при слабой конкуренции, но когда 16 потоков долбятся в очередь тысячами операций в секунду, начинаются беды. Под капотом мьютекса при блокировке ОС делает контекстный свитч — сохраняет регистры, вытесняет поток и будит другой, тратя микросекунды на операцию, которая сама длится наносекунды. Поэтому хочется уйти от блокировок: не ждать, а пробовать снова и снова, полагаясь на атомарные инструкции.
Главный примитив — compare_exchange_strong (CAS). Он атомарно сравнивает текущее значение с ожидаемым и, если совпало, заменяет на новое; иначе даёт прочитать актуальное, и поток крутится в цикле. Но наивная очередь на связном списке сразу ловит три проблемы. Первая — лавина выделений: каждый Push зовёт new, каждый Pop — delete, и потоки упираются в глобальный лок кучи, теряя весь выигрыш. Вторая — ужасная локальность кэша: узлы разбросаны по памяти, и CPU постоянно торчит на промахах. Третья — классическая ABA-проблема: пока поток А собрался сделать CAS на хвосте, поток Б уже вынул узел, удалил его, а потом аллокатор выдал тот же адрес под новый узел; поток А видит тот же указатель, CAS проходит, а данные — мусор.
Для борьбы с аллокациями и кэш-промахами автор меняет структуру: каждый узел FastQueueNode хранит не один элемент, а массив слотов на Size штук. Вся арифметика указателей выполняется раз в блок, а не на каждый элемент. Слот FastQueueNodeSlot размещает данные типа T и флаг готовности на std::atomic_flag. Тип обязан быть тривиально копируемым — для этого стоит C++20 constraint std::is_trivially_copyable_v, чтобы можно было просто memcpy без лишних вызовов конструкторов. Производитель атомарно накручивает head внутри узла, резервирует слот, копирует данные и взводит флаг с memory_order::release. Потребитель атомарно двигает tail, проверяет флаг (через acquire) и читает. В блокирующей версии (BlockingRead == true) потребитель может не жечь CPU, а уйти в atomic_flag::wait, который в Linux превращается в futex, на Windows — в WaitOnAddress, на macOS — в __ulock_wait. Пробуждение через notify_one обходится без мьютексов и условных переменных.
Чтобы потоки не мешали друг другу даже на уровне кэш-линий x86 и ARM, атомарные поля head, tail, next и сам массив слотов выровнены по 64 байтам через alignas(64). Иначе изменения в разных переменных, попавших на одну линию, вызывали бы лавину инвалидаций кэша — тот самый false sharing. Так получается основа быстрой очереди, где выделения памяти случаются в Size раз реже, данные дружат с кэшем, а ожидание при необходимости не дёргает ядро попусту. Проблему корректного освобождения блоков (чтобы не налететь на use-after-free) автор обещает закрыть hazard pointers в следующей части.