1) Пишем write в буфер фиксированного размера
2.1) Периодически флашим его, то есть асинхронно отправляем write c буффером через io_uring интерфейс (тут также понадобится некоторый кеш блоков, так как мы отдаем владение блоком ядру, но это просто список, стек)
2.2) Тут возможна оптимизация, есть два варианта как пользоваться io_uring сабмитить данные самому через сискол, или завести специальный поток на стороне ядра который будет поллить очередь [3].
3) Когда же попросили сделать fsync, мы просто флашим буфер, и хочется сказать "отправляем fsync через io_uring", но нет, ведь ядро, может исполнять запросы в очереди в произвольном порядке, что и делает io_uring действительно быстрым (забавно кстати, что есть некоторые параллели с тем как vulkan отличается от opengl). То есть, если мы просто будем отправлять fsync, то ядро сначала может исполнить его, а затем уже write-ы которые в очереди.
3) Что же тогда делать? Ну можно было бы дождаться завершения всех вызовов в очереди, то есть самим по-poll-ить completion queue, но есть решения лучше, давайте просто запушим nop операцию которая будет с DRAIN флагом, такая операция и будет барьером, который не позволит ядру запустить fsync раньше чем исполнить все write, при этом мы не будем ждать (!)

Собственно все, задача решена, самое приятное с точки зрения файлового IO, что все это работает как с буферезованным, так и с нет IO, например никто не мешает использовать mmap файла для рандомных чтений.

Ну и как вишенка на торте, то что помимо правильного API мы получаем самое производительное решение: есть разные бенчмарки, вот например [5]

Пожалуй единственный печальный момент, что даже 5.1 кернел еще далеко не у всех юзеров, как я понимаю enterprise на данный момент это в основном 3-4 кернелы (что конечно пиздец, но спасибо хоть не 2)

Что же с аналогами не из мира linux?

Ну на Windows, довольно быстро сообразили, что тут сделали офигенную штуку и сделали аналог [6], судя по тому, что я видел, разница около косметическая, что если WIndows это уже давно, просто лишняя абстракция над Linux кернелом? Работает же WSL как-то, ощущения что буквально взяли почти как есть io_uring.
Из особенностей, помимо мелких отличий, оно более свежее, так что мануалов, багов и тд, наверно больше. А еще, помоему, нет некоторых фичей, но задел под флаги есть [7], так что думаю это только вопрос времени.

В FreeBSD, macOS, ... ну вы поняли, насколько я знаю аналога нет :(
Ну пожалуй стоит заметить, что kqueue изначально сделан более прямо чем epoll и умеет в fd в отличии от него (epoll всегда возвращает что готов)
Как следствие проблема именно файлового IO там вероятно чуть менее остра? Ну а сокращение количества вызовов сисколов (только сейчас задумался как же странно это звучит), и возможность делать асинхронными не только read/write видимо менее критична на их взгляд. Не знаю, вообще macOS закрытая, а FreeBSD полутруп?

Но говоря про последнее, меня очень привлекает в io_uring именно возможность удешевления сисколов до почти обычных вызовов [8].
Может кто знает, я не интересовался такими маргинальными знаниями раньше: похоже ли io_uring на то, как обычно делают взаимодействие между компонентами в микроядерных ОС?
Но ладно, это неважно, важно, как мне кажется, то что по мере добавления поддержки новых сисколов в io_uring, возможно из Linux-а вынесут к черту большую часть кернел имплемнатции дров? И будет в кернеле не 20+ млн строк, а хотя бы какая-нибудь парочка)

Ладно оставим эти влажные фантазии, надеюсь на какую-то активность в комментах, я старался, а io_uring классный

Ну и за рамками обсуждения осталось, то что никто не мешает прикрутить io_uring к сокетам и посоревноваться с epoll, но учитывая, что последний итак хорошо работает, как по мне это уже не так интересно.

Ссылочки, для тех кому TLDR

[1] Efficient IO with io_uring собственно описание
[2] Функция, которая вызывается в golang для сисколов
[3] Пример с обьяснениями поллинга submission queue
Также это в целом отличный сайт с крутым названием, о том как использовать io_uring и liburing, кстати у автора сайта в блоге есть серия статей c примерами.
[4] IOSQE_IO_DRAIN
[5] Опыт и бенчмарки ScyllaDB
[6] Windows I/O Rings описание в прикольном блоге, там же есть пост в котором автор пишет о тех различиях, на которые он обратил внимание
[7] Windows I/O Rings дока, как видим пока флажков нет
[8] Доклад про микроядерную ОС: managarm, в общем выглядит красиво

Мда это фейл

https://telegra.ph/Bla-bla-bla-pro-io-uring-02-03 одной ссылкой про io_uring

Еще и спалился что не пишу большие тексты в телеге

Бля, почему слинковаться с libc++ так сложно?

Например такое пишут в simdjson:
https://github.com/simdjson/simdjson/blob/master/cmake/developer-options.cmake#L162
> # The next line is needed empirically.

Я в итоге сделал
add_link_options(-stdlib=libc++ -lc++abi)
add_compile_options(-stdlib=libc++)

Причем пришлось глобально в cmake сетитить чтобы пробросить в gtest

Но это пиздец. ненавижу cmake, писателей опций компиляторов и их документацию и тд. Почему блин не сделать все хотя бы внутри cmake просто добавили бы что-то вроде;
set(CMAKE_CXX_STDLIB ...)

Привет, в общем ситуация сейчас фиговая, у кого-то меньше, у кого-то совсем, а война это плохо.
Писать про это не хочу, итак весь телеграмм в этом, да и мой канал не об этом. В целом стараюсь не забивать на свои обычные дела.

Так что вот: https://github.com/YACLib/Bench
мы сделали сравнение YACLib, Folly, Boost::Thread фьюч, в бенчмарках практически полностью аналогичных бенчмаркам Folly.
Если вам любопытно, или не сложно, запустите пожалуйста их у себя и сделайте PR c результатами, мы будем очень признательны!
В readme есть how to guide, но если возникнут какие-то вопросы, или что-то не будет получаться, то можно написать issue, либо спросить здесь в комментариях.

P.S. Картинок пока к сожалению нет, но в ближайшем будущем добавим скрипт, который их рисует + применим его к тем результатам что уже в репе.
А еще наверно будет пост на reddit и habr, с разбором результатов бенчмарков

А никто не знает какого нибудь плагина для zsh, который бы делал из истории что то вроде lru кеша неограниченного размера.

Проще говоря если я повторяю команду нужно удалить прошлый ее вызов из истории

Наконец-то получил загран!

Кстати разбираю сейчас EPaxos, статью и алгоритм в целом, думаю напишу подробнее об этом, было бы круто если кто нибудь тоже прочитает и готов обсудить (в комментах)

// godbolt умеет в много файлов и cmake
https://twitter.com/CompileExplore/status/1431022441917210625
Я единственный слоупок который не знал об этой фиче?
В общем это прям классно, единственный минус, нельзя ничего качать в cmake :(
Есть issue, но там пишут что по secure причинам не хотят разрешать.
Есть мысль что можно предложить local storage из которого будут пытаться по alias-у забрать

Но в целом это не супер важно, пример работы фичи с яклибом:
https://godbolt.org/z/e6WP4Wb6o

// Как вы блокируете > 1 мьютекса?
Наверно у вас есть на них какой-то порядок, либо вы используете std::lock (иначе possible deadlock).
std::lock использует алгоритм наподобии (только обобщенный до n мьютексов):

while (true) {
  std::unique_lock l0(m0);
  if (m1.try_lock()) {
    l0.release();
    break;
  }
  l0.unlock();
  std::this_thread::yield();
  std::unique_lock l1(m1);
  if (m0.try_lock()) {
    l1.release();
    break;
  }
  l1.unlock();
  std::this_thread::yield();
}

И мне всегда казалось неочевидным, что это лучше, чем упорядочить по адресам (адрес обьекта мьютекса не может измениться, что кстати должно быть неправдой в rust?).
Недавно в коде folly обнаружил ссылку на любопытную статью с бенчмарками
http://howardhinnant.github.io/dining_philosophers.html

В общем если у вас не естественный порядок (например у вас всего два мьютекса и вы всегда держите блокировку на первом дольше чем на втором) std::lock покажет себя лучше чем упорядочивание по адресам.
Условный пример, когда std::lock лучше:
У вас есть счета юзеров, каждый из них обладает мьютексом.
Чтобы совершить перевод с одного счета на другой вы блокируете мьютекс отправителя и мьютекс получателя

В итоге Epaxos оказался сложной и интересной темой, и я решил написать несколько постов о leaderless replicated state machine.
А потом оказалось что у меня куча дел и в итоге вы читаете первый пост только сейчас.

Наверно многие из вас в какой-то степени знают Raft/Paxos/MultiPaxos.
Исторически сложилось так, что Raft стал самым популярным алгоритмом для RSM.
Какие оптимизации (относительно запуска single decree Paxos в каждой ячейке реплицируемого лога, что очевидно проще) используются в нем?
1) То что у нас есть лидер, причем строгий, то есть никогда не может существовать несколько лидеров одновременно (это ключевое отличие от MultiPaxos, где тоже обычно есть лидер, но не строгий, выбираемый по иным правилам. А ещё это переносит livelock в Raft с фаз Prepare/Accept на выбор лидера, по сути остался только выбор лидера и Accept). Главное, эта оптимизация позволяет лидеру практически не сталкиваться с конкуренцией.
2) То что после фазы Prepare/выбора лидера мы отправляем Accept-ы батчами, это позволяет нам делать 1 rtt вместо 2 (без учёта клиента, которого редиректят на лидера, и собственно самого выбора лидера/первого Prepare для MultiPaxos)

К сожалению эти оптимизации не лишены недостатков:
1) Страдает доступность, ведь в случае каких-то проблем с лидером: падает, тормозит, сеть медленная, етс. У нас возникают проблемы в целом, от долгих перевыборов до чего то посложнее (пример решения части из них https://decentralizedthoughts.github.io/2020-12-12-raft-liveness-full-omission)
2) В случае WAN происходит 2 WAN коммуникации (клиент лидер, лидер фоловеры)
3) В целом так или иначе, но лидер это бутылочное горлышко

Поэтому мне кажется мысль, которая возникает у многих, особенно в случае WAN, а нельзя ли как-то оставить алгоритм leaderless, и при этом получить хороший throughput и низкую latency.

Собственно о статьях про такие алгоритмы я и хочу рассказать.

#leaderless_0

В процессе изучения темы, я столкнулся с тем что leaderless алгоритмы: EPaxos, FPaxos, Atlas, etc довольно сложны, при том что сам по себе Paxos довольно прост.

Так что начну я с обзора одной несложной статьи, автор которой опирается на собственные исследования в рамках CASPaxos (https://arxiv.org/abs/1802.07000)

Идея CASPaxos крайне проста: если state RSM меньше чем команда лога, компактный, то можно реплицировать его вместо лога. И выиграть как с точки зрения упрощения алгоритма, так и с точки зрения перфоменса, то есть в батчинге (можно отправлять/записывать результат не каждой отдельной команды батча, а его финальное состояние)

http://rystsov.info/2020/06/27/pacified-consensus.html:
Собственно идея самого алгоритма который позволит реплицировать leaderless и быстро произвольный RSM (а не только регистр) очень прикольна. Давайте возьмём условный MultiPaxos, и вместо того чтобы выбирать лидера, уменьшим конфликты засчет порядка на запросах клиентов, то есть сделаем батчинг, и определим позицию в логе заранее (сделаем это с помощью CASPaxos, так как реплицируемый стейт это просто набор запросов), а ещё этот CASPaxos можно не fsync-ать, так как даже если что-то разломается, сам наш алгоритм -- примитивный Paxos, и продолжит работать, пусть и медленее.

#leaderless_1

В общем можно посмотреть мой доклад по фьючам в яклибе:
https://youtu.be/VbWEJibHlg8

Вообще довольно обзорно получилось наверное, если вы более менее знаете как писать неплохие фьючи.
В яклибе несколько больше интересных моментов, можно обсудить

Кек, со мной такое в первый раз, я ещё думаю какого фига не открывается

https://scholar.harvard.edu/files/mickens/files/thesaddestmoment.pdf смешной текст про византийские отказы

В общем если честно мне субъективно не нравится mold, там стремный подход к разработке, в нем куча багов, может фейлится, видимо в нетривиальных кейсах и тд.

Но у него есть одно важное преимущество, на данный момент во многих кейсах он быстрее других линкеров.

И это круто, потому что это заставило пошевелиться авторов lld (линкера, который я использую).
Если посмотреть на историю коммитов, то было сделано много в плане перфа именно после релиза mold.
А ещё можно найти такую интересную статью от автора lld, про то как его можно ускорить:
https://maskray.me/blog/2021-12-19-why-isnt-ld.lld-faster
Ну и кое что уже сделали
https://discourse.llvm.org/t/parallel-input-file-parsing/60164/10
В общем классно

https://www.reddit.com/r/cpp/comments/wilctv
Я тут сделал небольшой пост-анонс на реддите о яклиб, если у вас есть технические вопросы, или что-то подобное, пишите ;)

Ещё я почистил issue, и отметил good first issue, может кого заинтересует:
https://github.com/YACLib/YACLib/issues?q=is%3Aopen+is%3Aissue+label%3A%22good+first+issue%22


Ну и в качестве чего-то интересного:
Известные мне реализации в библиотеках user-space mutex для корутин C++20, в cppcoro, libunifex, folly::coro, содержат одинаковый серьезный баг, весь код после unlock может быть сериализован.
Проблема в общем здесь https://github.com/facebook/folly/blob/main/folly/experimental/coro/Mutex.cpp#L73, код после unlock начнет исполняться только после исполнения всех критических секций в батче и при этом будет исполняться последовательно, то есть после unlock нужен reschedule, и даже это лишь маскирует проблему и лишает смысле Unlock как просто функция.


В YACLib мы сделали Unlock иначе:
https://github.com/YACLib/YACLib/blob/main/include/yaclib/coroutine/async_mutex.hpp#L215
И избежали этой проблемы, сохранив преимущества эффективной lockfree реализации и возможности батчинга критических секций (только с co_await Unlock), вот тест:
https://github.com/YACLib/YACLib/blob/main/test/unit/coroutine/async_mutex.cpp#L273

Надо бы создать issue...

В общем накипело.
atomic wait/notify и все связанное c этой фичей в C++20 просто сломано причем в куче мест

Давайте разберемся по пунктам:

Начнем с апи, стандарта, оно неправильное
1.1) Неправильно требовать валидный *this для нотификации.
Ведь в большинстве юзкейсов у нас его уже нет, а в имплементациях нам он не нужен.
На эту тему есть proposal, единственное маленькое уточнение, такой код логичнее, чем тот что приводит в примере Льюс Бейкер
1.2) Менее важный момент, что wait ждет изменения значения, мы сразу сталкиваемся с кучей проблем, подробнее дальше, но вот краткий список:
spurious wakeups (мы должны их обрабатывать), пропуск нотификаций, изменение значение без нотификаций и так далее
Резюмирую: wait и notify обязаны были быть кроссплатформенными обертками над сисколами

Дальше про проблемы имплементаций:
2) Вроде все неплохо в MSVC STL, так как на винде есть WaitOnAddress для 1, 2, 4, 8 байт, реализация же вроде работает без багов и делает что-то разумное:
Делает load с нужным memory order и вызывает системную имплементацию

Загрузка wait функций страшная и непонятно насколько правильна fallback реализация, но лично мне пофиг на древнюю винду.
По поводу загрузки кажется как минимум то, что на вызов делается 2 atomic load можно было бы поправить:
1. https://github.com/microsoft/STL/blob/8ca7bd3c002d383940de9abe6379721e96eb12e3/stl/src/atomic_wait.cpp#L163
2. https://github.com/microsoft/STL/blob/8ca7bd3c002d383940de9abe6379721e96eb12e3/stl/src/atomic_wait.cpp#L173
Но наверно на фоне сискола это незначительно.

И тут мы плавно переходим к проблеме других реализаций, как можно поправить то что syscall дорогой.
Ну например добавив счетчик сколько сейчас ждет, или spin c cpu_relax/etc сколько-то итераций.

Нужно ли это делать? НЕТ.
А если вдруг хочется оптимально имплементировать wait, для этого есть condvar, semaphore, etc
Поэтому спасибо разработчикам MSVC STL за хорошую реализацию (кстати второй раз натыкаюсь на то, что остальные сделали плохо, а они хорошо, первый visit variant).

Как мы помним у MSVC все хорошо отчасти потому что WaitOnAddress работает с атомиками sizeof 1,2,4,8.
На линуксе же это не так, как многие из вас знаю futex требует uint32_t, а в принципе работает с любым 32 битным адресом.
Так что дальше будет хуже.
В принципе, чтобы это исправить (а на самом деле для windows софта в wine/proton) добавили futex2 в ядре 5.16
К сожалению оно пока больше про другие возможности Wait/WakeOnAddress, то есть все еще только 32 битное.
Да и даже так ни одна stdlib пока не поддерживает, и хорошо если поддержит лет через 10.

3) Возникла мысль, что ничего страшного ведь для 32 битных атомиков все будет как на винде?
Для libc++ действительно практически так, но есть пара нюансов:
3.1) Перед сисколом будет spin в wait, то есть до сискола мы будем крутиться (если что там выше по стеку проверяется каждую итерацию значение атомика, первые 64 итерации now() не вызывают), в чем проблема? Другие реализации могут иметь другой спин, не кроссплатформенно
3.2) Эта реализация будет использоваться только в случае, если у вас linux и atomic_int32_t.
Почему не разрешить для других подходящих по sizeof и alignment типов? Потому что им пофиг, написали, галочку, что поддержали, поставили и идите вы все в жопу.
3.3) Какая же реализация в случае других типов или других операционных систем?
Берется хеш адреса вашего атомика и выбирается ячейка из двух 32 битных атомиков в таблице на 256 ячеек
Один из атомиков используется для подсчета сколько сейчас ждет потоков в этой ячейке (и оптимизации: не нужно делать нотификацию если нет тех кто спит)
Другой для ожидания на сисколе (кстати теоритически можно смоделировать ситуацию что мы пропустим нотификацию из-за переполнения 31 бит (хотя там уб в таком случае так как signed)
3.4) Кстати, а как пользователь должен узнавать какой тип отвечает за нативное ожидания? int32 или что то еще?
В стандарте добавили atomic_signed_lock_free, atomic_unsigned_lock_free, которыех к сожалению нет libstdc++, а в libc++ они 64 битные :)

В общем к чему я веду, стандарт сказал сдейлайте атомики c ожиданием для всех платформ, для всех sizeof-ов.
Но оказалось что если не сделать spin для неудачного sizeof, все будет работать очень плохо.
А если не добавить spin во все реализации, то самая оптимальная реализация перестанет быть таковой для малого времени ожидания.
В итоге получаем сильно разные реализация в разных stdlib :(

4) Ну и последним, посмотрим краем глаза на самое мерзкое, на libstdc++.
Начнем с хорошего, здесь добрые пользователи уже пофиксили, то что futex на вашем атомике будет использоваться для любого int like типа
В остальном же реализация похожа на ухудшенную версию libc++:
4.1) spin намного проще, 16 итераций, после 12 делается бесполезный sched_yield
4.2) Также странное количество ячеек в таблице всего лишь 16, можете представить как хреново это будет работать на 40-100 ядерной машине (используется только в случае не int like типа)
4.3) Реализация использует таблицу так же, чтобы избегать нотификаций (увеличивать контеншн*), даже в случае futex реализации.
4.4) А да, чуть не забыл, похоже что реализация бажная (тщательно тестируемый код зависает только с реализацией на atomic wait, с mutex + condvar все хорошо и только atomic wait + libstdc++)

Резюме:
Используйте системное api или mutex + condvar (написать который самостоятельно герои из stdlib не смогли/не захотели и там pthread/srwlock/etc), или тщательно проверяйте это дерьмо

Если у вас возникла мысль, что я зря качу на них бочку, то могу привести еще примеры:
Например counting_semaphore, на который ссылается Льюис Бейкер в пропозале, написан неправильно и зависает даже в тривиальных тестах.
Как в libc++, так и в libstdc++ (был еще один но его недавно пофиксили (фикс отдельный кайф), этот же все еще воспроизводиться), до сих пор :(
А теперь вспомните сколько докладов с названием расскажу вам про semaphore, latch etc в C++20 вы видели.

Какой из этого вывод?
Concurrency фичи C++20 по большей части либо не работают, либо работают частично (как корутины например).
Зато можно использовать https://github.com/YACLib/YACLib и не знать о таких и других проблемах)

Привет, сегодня будет лайтовый пост, про union.

Многие говорят про современный С++, никогда не используйте union, используйте variant/optional.

1) И если мы говорим об использовании в виде:
some_unsigned flag;
union { types... };
это безусловно так.
Хотя visit может быть менее оптимален чем ручной switch, но это проблема имплементации (несмотря на то что конкретно этот баг пофикшен, общее поведение не изменилось, что на мой взгляд весьма печально, единственную полноценную имплементацию этой идеи я видел в msvc stl)

Но что насчёт других применений union, где это не так?
2) Наверное первое что приходит в голову это type punning (union { unsigned, float }, чтобы посмотреть на битики float), в C это можно, но в C++ это UB.
Вероятно причина в том что если можно взять помимо мутабельной ссылки, ещё хотя бы одну любую ссылку, можно очень легко получить UB из-за aliasing-а:
void foo(A&, B&)
union { A a; B b; } x;
foo(x.a, x.b);
(Возможно в Rust это не проблема из-за borrow чекера?)
Другая возможная причина во взаимодействии с битовыми полями.
Резюмируя в C++ можно использовать только memcpy, или bitcast (до сих пор нет в apple libc++, учитывая что оно появилось в llvm libc++ 14, подозреваю будет в apple libc++ 16)

3) Два других менее очевидных применения это ленивый вызов конструктора и ранний вызов деструктора.
В обоих случаях можно использовать optional, но он увеличивает sizeof вашего класса, и не позволяет убрать conditional jmp из ленивого конструктора и сделать настоящий деструктор тривиальным (также убрав из него conditional jmp и вызов настоящего деструктора).

В YACLib мы этим пользуемся в паре мест, это в части бенчмарков дает нам выигрыш в 5-10%.
Сам же ленивый вызов конструктора нужен потому что у нас нет результата не запущенной функции.
А ранний вызов деструктора нужен чтобы разрушить функтор (например лямбду с захватом каких-то локов) сразу после того как она была вызвана.

В Rust кстати есть MaybeUninit специально для этого

4) variant не позволяет использовать SoA вместо AoS для флага, в случае же с union это вполне возможно, иногда полезно, и удобно если типы тривиальны.

5) Вместо aligned_storage_t или alignas(...) std::byte[...] (первое кстати задеприкейтили так как убогое).
На это есть несколько причин, во-первых это банально красивее и удобнее (нет нужды постоянно делать reinterpret_cast)
Во-вторых, по крайне мере до недавнего времени (не знаю можно ли сейчас) placement new нельзя было использовать в constexpr контексте, поэтому если вы хотели написать variant/optional<constexpr_allowed_type> вам нужно было в имплементации variant/optional использовать union

На этом вроде все, что вспомнилось, пишите если я что-то забыл!

А ещё я думаю по большей части это применимо и в других языках, например таких как Rust (но я не знаю их достаточно, поэтому не гарантирую)