В общем к чему я веду, стандарт сказал сдейлайте атомики 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

https://quick-lint-js.com/blog/cpp-vs-rust-build-times/
Оно конечно немного стрёмно, в духе сравнения apple clang 14 (что примерно соответствует 12-13 llvm clang) и llvm clang 15
Но любопытно и впечатляет насколько много бесполезного было сделано

Давно не писал, чем я вообще занимаюсь

Читаю книжки:
1. https://nlp.stanford.edu/IR-book/information-retrieval-book.html — про идеи и алгоритмы, которые стоят за поиском.
В целом, я многое уже знал по работе, но мне нравится, то что структурирует мои знания и в целом более теоретический взгляд.
Ещё в очередной раз убедился насколько книжки с упражнениями лучше, чем книжки без них, единственный минус, в отличии от perfbook, здесь нет ответов, чтобы проверить себя (остается, либо доказывать, либо гуглить, если не уверен).

2. https://ciir.cs.umass.edu/irbook
По сути тоже самое, но якобы более практическое (из прикольного к книжке есть жаба код учебного поискового движка http://www.search-engines-book.com), по факту мне показалась более поверхностной и менее интересной.

Вообще на работе сейчас занимаюсь ускорением geo поиска, так как он работает у нас на s2, у меня периодически горит с них жопа.
Например, сделал оптимизацию для случая, когда кверить будут только точки и заодно улучшил интерфейс, чтобы не нужно было делать аллокацию на каждый вызов, PR до сих пор висит https://github.com/google/s2geometry/pull/303, потому что гугловый чел не оценил моего расширения интерфейса. Надеюсь его не сократят, а то не знаю сколько ещё ждать ответа.

В целом мне кажется историю, которая у нас сейчас: храним термы для кверинга в инвертед индексе, а потом вычисляем точную операцию, можно делать принципиально лучше, проблема в том что s2 почти не развивается, а нужно, чтобы их индекс умел в выдачу конкретных фигур в intersects/contains не только для поиска точек, но и полилиний и полигонов, вроде как они планируют это сделать, но когда — хрен его знает :(

Вообще как бы вы решали задачу k-way merge (есть k отсортированных input, нужно получить 1 отсортированный output)?

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

Но с практической можно делать меньшее (в константу раз) число сравнений.
Вчера я вспомнил, что хотел померить это в arangosearch.

Ну и в общем в чем же идея?
Давайте сначала вспомним, что будет происходить в случае кучи:
Каждый раз доставая элемент нужно сделать sift down обновленной вершины:
Это в свою очередь спуск вниз на глубину log(k), к сожалению на каждом спуске нам ещё нужно проверять спускаться в левое или в правое под дерево, то есть в итоге мы получим не больше 2 * log(k)
(в плюсах и многих других языках из коробки ещё хуже, так как decrease key отсутствует, нужно сделать pop + push, что уже до 3 логарифмов, +1 потому что push это sift up, который требует не более логарифма сравнений)

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

Поэтому вместо этого можно поддержать дерево явно, по сути сделав дерево отрезков минимумов, такой подход называют tournament tree, и он даст ровно log сравнений

Cегодня я набросал код и вероятно завтра напишу микробенчмарки, потом еще посмотрю на перф в аранге:
https://github.com/iresearch-toolkit/iresearch/pull/476

В целом весьма очевидно что мы выигрываем, есть ли минусы? В сравнение с pop + push подходом нет, в сравнении с sift_down к сожалению да.

Главная проблема что в случае дерева нам нужно поднимать новое значение снизу, то есть логарифм сравнений мы делаем всегда.
В случае же с кучей мы опускаем значение среди других значений и если нам повезло и input-ы не пересекаются мы на каждый push в output будем делать только 2 сравнения (кроме тех где input закончился).

Резюмируя для [0;4-8] инпутов tournament tree однозначно лучший подход, относительно числа сравнений.

А дальше это зависит от данных. Если данные рандомные то все еще лучший. А вот если по какой-то причине у вас очень мало переключений инпутов или вообще disjoint диапазоны, то вероятно ручной sift down покажет себя оптимальнее :(

Можно ли что-то с этим сделать?
Наверно нет, только страдать, впрочем еще мне нравится подход с деревом тем, что это всегда фиксированное число сравнений, их число не зависит от того как именно output данные расположены в input-ах

Не конструктивный пост, для меня C++ лучший выбор для разработки чем Rust, да у него есть очевидные преимущества над C++, впрочем верно и обратное.

Сейчас я не буду перечислять все, а расскажу об одном из наиболее важных для меня недостатков, который декларируется как преимущество, это cargo и система пакетов.
В вакууме она безусловно лучше того, что предоставляет C++ (кривые поделия, отсутствие стандарта => большинство зависимостей собирается из сорцов).

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

Качество кода и глубина зависимостей становятся куда менее однородными, чем при подходе сборки из сорцов.
Есть статья которая в целом отражает мое отношение к зависимостям:
https://research.swtch.com/deps

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

Впрочем в си на мой взгляд есть противоположная проблема, когда библиотеки практически не используются (кроме domain specific: сжатие, криптография, етс), а в стандартной библиотеке отсутствуют контейнеры, как следствие все реализуется по 10 раз, а дефолтная структура данных для си это список (из-за своей простоты).

Резюмируя, у каждого из подходов есть свои недостатки, но контролировать, что в твоём проекте нет лишних велосипедов, сильно легче на мой взгляд, чем контролировать что все зависимости не зависят от чего то зря (да и что делать в таком случае не очень ясно).