Автор в статье: так как мы хотим хранить значения в диапазоне [0, n-1], в качестве null'а возьмём 2n-1
Я: отлично, логично, всё понятненько
Автор в коде: очевидно, в качестве null можно взять использовать n-1
Я: *второй вечер бью голову об вопрос* почему...

Upd. ненулевой шанс, что имплементация подогнана под бенчи, а бенчи могут этот корнер-кейс и не задеть 🙃

Upd 2. попробовать что ли автору написать...

Upd 3. похоже, действительно алгоритм ломается, если брать n-1 вместо 2n-1, но бенчи это не покрывают и не особо проверяют. Да и бенчи не слишком-то честные...

Upd 4. или бенч всё-таки честный... но тогда и алгоритм работает? ну что за качели

ЪУЪ

Ларчик просто открывался: я дурачок, всё работает и написано прям по статье

Фига, я лох
Умудрился майнер на линь-сервак поймать

Ура! Справился-таки написать реализацию очереди

Сводки из приключений в процессе:
* кучу времени дебажил проблему, что часть записей в очередь теряется
* не мог понять, накосячил в реализации или в тесте
* в какой-то момент понял, что нашёл кейс, не покрытый алгоритмом в статье
* "ну точно где-то я нашизил"
* совершил немыслимое: залез в секцию "доказательство корректности" (обычно при прочтении статей у меня на ней мозг перемешивается в однородную кашицу, потому она скипается)
* осознал, что в тесте не учёл инвариант: в очереди не должно оказаться больше n элементов. Обеспечивается он тем, что это служебная очередь

В процессе думаю над тем, что можно обкромсать для MPSC кейса (который рискует оказаться для меня более интересным). Статья строит очередь произвольных элементов на двух очередях индексов: занятых и свободных (поскольку все n индексов, циркулирующих по очередям, прописаны на инициализации, инвариант, на который я наткнулся выше, всегда выполняется). То бишь, идейно выглядит так (вся магия спрятана внутри SCQ очередей)

class Queue {
    bool try_enqueue(T elem) {
        optional<size_t> idx = free.dequeue();
        bool success = idx.has_value();
        if (success) {
            data[*idx] = elem;
            acquired.enqueue(*idx);
        }
        return success;
    }

    optional<T> dequeue() {
        optional<T> result;
        optional<size_t> idx = acquired.dequeue();
        if (idx) {
            result = data[*idx];
            free.enqueue(*idx);
        }
        return result;
    }

    SCQ free;
    SCQ acquired;
    T[] data;
};

Чтобы ослабить алгоритм до MPSC, понадобится MPSC очередь занятых индексов (туда пишут producer'ы, читает единственный consumer) и SPMC очередь для свободных индексов (из неё берут элементы producer'ы, туда пишет единственный consumer). Хотя погодите-ка. Реально очередь формируется из занятых индексов. Но свободные нам брать в порядке очереди вообще не обязательно (если не вредно). В статье про ослабленные очереди я натыкался на структуру данных bag: у неё есть операции push(T) и pop_any(): она не обещает вообще никакого порядка, в котором из неё вынимаются элементы. Можно покопать в этом направлении (пока нашёл единственную статью 11-го года — буду вдохновляться, возможно, что-то ещё на эту тему найдётся)

Но прежде, замеры и тюнинг оригинала. Изначально получал 10'000-кратный разброс в результатах, пока сократил до гордых 100 раз (методом распихивания по раздельным кеш-линиям всего, что распихивается). В SPSC режиме лучшая задержка, которую видел, в районе 2 микросекунд (что вообще-то дофига, но пока код не тюненный, да и железо третьей свежести), но чаще получаю несколько десятков. Что поделать, вынимаем напильник, дорабатываем

P.S. Ну и да, в процессе замеров обнаружил, что некий kswapd0 жрёт у меня один из двух процов целиком, паскуда. Даже после ребута, когда использование свопа 0, использование RAM <10%. Неладное заподозрил, когда увидел, что он запущен из-под юзера, на котором у меня всякие докер-шняги крутятся, плюс запущен как ./kswapd0. Судя по тому, что в интернете нашёл, это какой-то майнер. Сходу влезть в бинари не получилось, так что прикопал в архивчик и снёс. Где поймал — хер его пойми

Люблю программирование

Иногда ты отлавливаешь всратый рейс в сетевом протоколе в качестве приключения на 20 минут
А иногда ты 2-3 часа не можешь понять, что у тебя в системе не льются данные, потому что их источник не запущен

Иногда это происходит в один день (сегодня, например)

Колдую вам приятный воскресный вечер

Мой первый дом в каждом заходе в майнкрафт би лайк