Разработчик nahla-nee опубликовал реализацию новой bounded очереди для Rust, которую назвал WFQueue. Это структура с гарантией bounded waiting — то есть у каждой операции есть предсказуемый верхний предел времени ожидания, если только не случится зависания потока или сбоя. При этом автор сразу уточняет: очередь не является wait-free, как он ошибочно утверждал в первой версии поста — за поправку спасибо пользователю Reddit matthieum.
В основе лежит система с двумя атомарными счётчиками (AtomicUsize) для производителей и потребителей, а также двумя кольцевыми буферами. Один буфер хранит данные, второй — состояние каждого слота. Состояние — это тоже AtomicUsize: младшие 63 бита хранят номер резервации (тикета), а старший бит указывает, чья сейчас очередь — производителя или потребителя. Логика простая: производитель захватывает слот, ждёт своего номера, записывает значение, переключает бит статуса на потребителя. Потребитель делает то же самое в обратную сторону.
За счёт того, что слоты независимы, очередь минимизирует head-of-line blocking — медленный потребитель не блокирует всю очередь, а тормозит только свой слот. Кроме того, нет CAS-циклов: ожидание построено на чтении, что снижает когерентность кэша. Для асинхронных сценариев есть «управляемые» версии операций — они возвращают структуру с методом drive, который сам решает, сколько раз пытаться выполнить операцию, прежде чем вернуть управление.
Есть и фундаментальное ограничение: из-за использования старшего бита счётчик резерваций переполняется на уровне 2^63, а не 2^64. Если умудриться запланировать 2^63+1 операций так, что первая и последняя совпадут по номеру слота — случится гонка. На 64-битных системах это ~9.22 квинтиллиона операций, так что риск чисто теоретический. Ещё одна проблема — дроп управляемых операций: если их не довести до конца, слот блокируется навсегда.
Бенчмарки автор гонял на Ryzen 7 7800x3D с Fedora Linux 44. Лучший результат в сценарии «N производителей, N потребителей» — при N=4 (56 млн элементов в секунду), дальше производительность падает, а потом медленно растёт. Автор подозревает, что дело в соотношении типов потоков, но отложил разбор на потом. В сценариях с одним продюсером и многими консьюмерами (и наоборот) скорость растёт плавно до 73–74 млн элементов в секунду на 15 потоках. Исходники и полные таблицы лежат на GitHub.