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 (но я не знаю их достаточно, поэтому не гарантирую)

https://github.com/abseil/abseil-cpp/commit/535f22b4a08a11166c91fabc22fe130933c745a7#diff-63e37c19fd975193f3b7ebfc5bf0a0d0b47761463d5c683df93e2823999be1faR256
Прикольно

В общем я не специалист по написанию sql/etc запросов, хоть и пишу бд.

Сейчас узнал (из issue) про забавный хак: ORDER BY RAND() LIMIT N. Собственно идея в том чтобы получить N случайных записей из таблицы (зачем нужно уже это без понятия, но прикольно).

https://youtu.be/ugw0lQoATB4
Мне тут ютуб порекомендовал любопытный доклад про различные заброшенные опенсурс субд.
Кстати про несколько систем из списка слышал, но вообще довольно грустно

В целом как-то не было особо времени/желания писать посты, на работе как то загружено, а остальное время занимался яклибом.
Между прочим я уже скоро два месяца как в Кельне, и в общем мне тут нравится.
Мои опасения по поводу отсутствия разнообразия в местной кухне не оправдались, а работать из офиса намного лучше ;)

Вы наверно знаете, что такое конечные автоматы.
Но возможно, как и я до недавнего времени, не слышали об FST.

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

Еще эта структура данных примечательна тем, что имеет полезные применения:
- Используется для хранения словаря термов (и не только) в lucene и других поисковых движках. Кстати в качестве полукольца веса может быть и строка
- В распознавании речи в kaldi, статья довольно подробно описывает зачем, только учитывайте, что за исключением части раздела 2 и раздела 4 это по большей части повторение первой статьи.

Как я думаю следствием этого является наличие вменяемых имплементаций.
Например гугловая библиотека C++ OpenFST, ее используют kaldi и например мы в ArangoDB.

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

Но зачем вообще в ArangoDB OpenFST? Мы используем ее в https://github.com/iresearch-toolkit/iresearch (аналог lucene), правда с некоторыми патчами.
Поставьте нам в iresearch звездочку кстати!

К сожалению OpenFST не без недостатков, что неудивительно учитывая что либа была написана еще в 2000-ых:
- bazel/make как система сборки, это типичный недостаток гугловых/старых либ, но это не большая проблема, можно написать свой простенький cmake для нужного вам (есть в iresearch)
2. То что это все живет не на условном github/gitlab/etc, хз принимают ли они патчи например, ну и в целом мне кажется это сказывается на активности разработки.
3. В либе много довольно странного API, который стоило бы задеприкейтить.
В целом ощущение что оно почти не развивается

Если же говорить про другие библиотеки fst, я видел несколько любопытных на rust:
- Попытка переписать openfst
- Реализация fst на rust, которая используется в tantivy
Собственно имплементация в lucene
Вроде бы еще что-то есть на java но я не интересовался

Еще постараюсь до нг написать про fault-injection немного и геометрию

Всех с наступающим/наступившим новым годом!
В общем надеюсь что новый год будет лучше чем этот для всех нас.

Кстати YACLib добавили в conan!
https://github.com/conan-io/conan-center-index/pull/14006