Lockfree, coroutines & fibers

01 Mar, 2025

Данный пост является объединением 3-ех лекций из “Продвинутого курса C++” для второго курса ПМИ ВШЭ.

Неблокирующая многопоточность

Чем отличаются atomic’и и mutex’ы? Они представляют 2 различных подхода к многопточности.

~ Замеряем производительность атомиком и мьютексов ~

Итоги: на одном потоке мьютекс быстрее, на 2 и более мьютексы становятся быстрее. Зачем же нужны атомики?

Мьютекс не гарантирует время исполнения операции.

Любой многопоточный алгоритм: lock-free, wait-free, либо никакой. Wait-free - все потоки одновременно продвигаются. Lock-free - хоть один поток делает прогресс в системе.

Как же писать lock free код.

fetch методы атомика

ЗАДАЧА: fetch-mul

Пример некорректоного кода:

#include <atomic>
int FetchMul(std::atomic<int>& a, int b) {-
    int value = a.load();- 1
    a.store(d: value * b);~ return value;-
    return value;
}

void FetchMul(std::atomic<int>& a, int b) {
    int exptected = a.load();

    // compare and swap, Cas
    if (a.compare_exchange_strong(expected, expected * b)) {
        // return true
    } else {
        // update expected
    }

    a.compare_exchange_weak(); // может сфейлиться даже, если значения совпали, но на уровне железа работает быстрее
}

Lock-free stack

#include <stack> 
template <typename T>
class LockFreeStack {
public:
    void Push(T value) {
        Node* expected_head = nullptr;-
        Node* new_head = new Node{expected_head, std::move(value)};

        while (!head_.compare_exchange_weak(expected_head, new_head)) {
            new_head next = expected_head;
        }
    }

    std::optinal<T> Pop() {
        Node* expected_head = head.load();

        // Hazard pointers - один из вариантов
        // dodo
    }
}

Корутины

Функции, которые могут приостанавливаться (сохраняя состояния) и передавать управление другой функции.

statefull (хранит состояние на куче) / stateless (на стеке)

без поддержки компилятора / обязательно поддержка

библиотека: cppcoro

Корутины в C++20

Корутина - функция, где есть использование одного из трех co_ - операторов

co_return
co_yield
co_await

Такие названия нужны ради обратной совместимости. Первые 2 слова - сахар Важнее co_await

Утиная типизация для корутин.

Смотрим свойства:

Корутина - это обычная функция Много соглашений, много соглашений …

поведение функции определяется типом возврата (return object)

return_object promise_type <- сохраняет состояние coroutine_handle <- ручка

// generated code
nonstd::generator<int> numbers(int from, int to, int step) {
    using return_object = nonstd:: generator<int>; // реализовываем мы
    using promise_type = typename return_object::promise_type; // реализовываем мы
    using coroutine_handle = std:: coroutine_handle<promise_type>;

    promise_type promise(from, to, steps);
    return_object res = promise.get_return_object();
    //...
}

co_yield -> co_await promise.yield_value() co_return -> co_await promise.return_value()

co_await - приостанавливает управление и передает его вызывающей стороне

пример типичной корутины

// generated code
nonstd:: generator<int> numbers (int from, int to, int step) {
    using return_object = nonstd::generator<int>;
    using promise_type = typename return_object::promise_type;

    promise_type promise{from, to, step};
    return_object res = promise.get_return_object();
    co_await promise.initial_suspend();

    try {
    /* coroutine body */
    } catch (...) {
        promise.unhandled_exception();
    }
    co_await promise.final_suspend ();
}

Promise Что должно быть в минимальном promise?

promise.get_return_object()
promise. initial_suspend ()
promise. final_suspend ()
promise.unhandled_exception () Есть еще несколько продвинутых методов-точек расширения поведения.

resumable hello_world() {
    std::cout < "Hello, ";
    co_await std::suspend_always{}; // awaitable, стандарнтные примитивы suspend_always и suspend_never
    std::cout < "world!\n";
}

int main() {
    auto coro = hello_world();
    coro.resume();
    coro.resume();
}

Когда нужны корутины?

Когда программа много работает с внешним миром. Когда программа не cpu bound.

lection12.cpp - пример простой корутины lection12-gen.cpp - пример генератора

обсудили teleport_to - awaitable

void await_suspend(std::corutine_handle<> handle) const noexcept {
    target = std::thread{[handle] {
        handle.resume();
    }};
}

Что такое fiber и почему они крутые?

Сначала идет повторение матриала про корутины и их пользу (при работе с внешними вызовами).

Проблема: в не cpu-bounded задачах мы не знаем, сколько потоков запускать.

Сейчас можно пользоваться асинхроннными системными вызовами и т.д.

Чтобы было удобно со всем этим добром работать, придумали абстракции coroutines / fiber для асинхронного программирования.

Проблема корутин - тяжело использовать. Много багов, много проблем из-за памяти.

Корутины сильно делят кодовую базу на 2 типа функций, что неудобно, много кода написано без корутин.

Компиляторы только-только научились корутинам, еще в clang-17 есть множество критических багов.

Но как же люди живут на самом деле?

Ответ: fiber (или stackfull coroutines)

Что нужно, чтоб сохранить контекст исполнения функции? На самом деле выгрузить все регистры, а стек он и так находится в адрессном пространстве процессора и мы полагаем, что он не затрется в силу устройства современных архитектур.

Вся магия в следующем коде:

#pragma once
struct Context {
    void* ip;
    void* sp;
    void* regs regs[10];
};

enum class ESaveContextResult : int {
    Saved  = 0,
    Resumed = 1,
};

// Implimented in context.S
extern "C" ESaveContextResult SaveContext(Context* ctx) __attribute__((returns_twice));

extren "C" void JumpContext(Context* ctx) __attribute__((noreturn)); // атрибут, обозначающий, что мы не вернемся

Дальше в качестве демонстрации идет код на ассемблере, который собственно и сохраняет контекст.

Резко переходим к fiber’ам - оберткой над всей этой темой.

Fiber’ы проще корутин. Но дороже, и по памяти, и по cpu.

В плюсах нет одного общего движка Fiber’ов.

Вывод: нужно разбираться дальше, но тема крутая

#Cpp