Я тут заметил, что давно перестал слышать фразу "до морковкина заговенья"

Как оказалось, заговенье это день перед постом, когда люди обычно наедаются всякой жирной пищи, потому морковкино заговенье это оксюморон, и потому выражение имеет значение, которое имеет. Не знал

Lock-free очереди не нужны

Господь дал нам циклический буффер на fetch-and-add'ах, но мы были неблагодарны, сказали, что не настоящий lock-free, ведь могут быть livelock'и — и стали придумывать, как оных избежать

Первая идея просто ошеломительной простоты: а давайте мы затолкаем FAA-очереди в очередь Майкла-Скотта (представьте себе самый простой lock-free односвязный список — вот это она), и будем добавлять новую вместо livelock'а. По памяти не ограничено, очищение памяти не проще, чем через hazard pointer'ы, да и хер с ним

Люди изголялись, как улучшить ситуацию с последним: добавляли слои индирекции, придумали подход fast-path-slow-path и даже добились wait-freedom по цене lock-freedom. Но самую, сука, дурацкую lock-free очередь в своих же бенчмарках обогнать не смогли. То есть, работы это скорее доказательства, что теоретически wait-free очередь может жить на ограниченной памяти, и в целом чувствовать себя неплохо, но на деле ограничивайтесь, мужики, obstruction freedom, и всё у вас будет ништяк

Вход в кроличью нору, чтобы при желании пойти читать референсы: wCQ: A Fast Wait-Free Queue with Bounded Memory Usage

Заморозить компьютер, чтобы вынудить меня его перегрузить, чтобы накатить обновление, это осознанная тактика винды или я опараноел в край?

Upd. Блядь, винда, обои-то что тебе сделали, ирод ты окаянный

Это мы слушаем
https://youtu.be/RYCR55P99yg?si=1a7s0250DyZFk1ZK

Баги расследовать люблю, пиздец

Фан факт: если не трогать окулус квест слишком долго, он магически превращается в кусок пластика

А ещё тот факт, что приложение, нужное для коннекта шлема с компом, требует фейсбук логина, вымораживает

Заставил компилироваться шмат растового кода, фото в цвете

Страшные люди пишут на сях лок-фри алгоритмы
Вот пишет он в статье, мол Cache_Remap нужна, чтобы пореже трогать одну кеш-линию. А смотришь в реализацию — там какая-то мрачная битовая магия, с полчаса медитируешь, чтоб понять, что это он младшие битики наверх утащил. Ща ещё столько же, походу, буду искать, куда этот кудесник флажок запрятал. А потом гадать, что за волшебные условия он расставил по коду, но не по псевдокоду в статье. Ъуъ

У меня курс про лок-фри алгоритмы был на жаве/котле, потому для меня от имплементации пейперов на сях несёт какой-то хтонью

Автор в статье: так как мы хотим хранить значения в диапазоне [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. Судя по тому, что в интернете нашёл, это какой-то майнер. Сходу влезть в бинари не получилось, так что прикопал в архивчик и снёс. Где поймал — хер его пойми