Attic #42

https://youtu.be/2olsGf6JIkU?list=WL
https://www.logicalbee.in/cpp-stl-algorithms-cheat-sheet

Видяшка и cheat sheet по всем основным алгоритмам в STL-е.

Осталось запомнить все это разнообразие и не забывать применять в коде и щеголять на собесах!

P.S. Вот что надо печатать на настенные плакаты вместо карт этих ваших Средиземий

#cpp #algo

https://webkit.org/blog/6161/locking-in-webkit/

Про локи и юзер-спейс фьютекс.

#futex #mutex #lock #concurrency

https://youtu.be/OPJ_IcdSqig

Elle - инструмент для black-box тестирования баз данных на уровень изоляции. От того же чувака, что делает jepsen!

В общем проверка на сериализуемость - это NP-трудная задача. Но Elle делает на тест ограничения, чтобы его было легче проверить: вместо обычных записей Elle производит Append (list l1, value x). Засчет этого в самих значениях сохраняется история операций.

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

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

На практике Elle _очень_ показал себя. Нашел даже в древнем постгресе баг! И работает намного быстрее более классического решения jepsen-а (Knossos). Никакого экспоненциального взрыва!

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

#jepsen #testing #consistency #distsys

https://www.microsoft.com/en-us/research/uploads/prod/2019/06/mimalloc-tr-v1.pdf

Mimalloc - аллокатор от MS для функциональных языков с паттерном "много маленьких аллокаций". Очень приятная, понятная инженерная статья. Лайк.

Основная идея: шардировать фри-листы на страницы (!= ОС страницы), чтобы была локальность аллокаций.

Основной путь аллокации - это всегда тред-локал список. Поэтому синхронизация нужна только при вызове фри из другого потока. Из-за таких (и других) сложностей возникают аж штуки 3-4 вида фри-листов.

Из забавного: один из счетчиков деаллокаций (thread_freed) читается неатомарно, из-за чего возникает дата рейс, но разработчики знают, что он не принесет ничего плохого, поэтому рейс посажен там специально! Ухх!

#allocator #c

https://queue.acm.org/detail.cfm?id=1594206

Интервью с инженером гугла о GFS: а точнее, о проблемах, возникающих на пути.

Система дизайнилась для батчевой обработки, а в итоге ее стали использовать клиенты, требующие latency. Вот те и большинство проблем.

Еще сингл-мастер был крутой (и нестандартной!) идеей в начале: дизайн получился простым и позволил быстро (за год, карл!) построить GFS, но потом конечно стал боттлнеком.

Одна особенность: гугл делает как инфру, так и приложения-клиенты для нее. Поэтому можно было спокойно и то и другое друг под друга настраивать.

#gfs #distsys #system #google

http://aturon.github.io/tech/2016/09/07/futures-design/

Дизайн Rust-овских фьюч. Объясняют, почему не подходили файберы, и стандартный подход к фьючам.

Надо посмотреть на Task в C++ - возникает смутное ощущение, что Task в С++ и Rust - родственные сущности.

#rust #futures

http://demsky.eecs.uci.edu/publications/c11modelcheck.pdf

Один из первых stateless модел-чекеров, проверяющих атомики С11. Он исследует программу, обходя сами исполнения, и по пути строя rf, mo, sc, hb с помощью векторных часов.

В основе - DPOR. Но внутри цикла DPOR появляется цикл по behaviours - т.е. по тем значениям, которые может прочесть читающая операция.

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

loom (https://github.com/tokio-rs/loom) ссылается именно на эту имплементацию.

#model_checking #loom #dpor

https://youtu.be/0emIUsU1_0E

Rust in Production - Стив Клабник

Стив офигенно (как всегда) рассказывает о расте: о его 4 ключевых словах в определении, показывает киллер-фичи на примерах, и рассказывает забавные истории адопта раста компаниями.

Хочу писать на расте!

#rust

https://www.youtube.com/watch?v=Dq0WFigax_c
https://blog.golang.org/generics-next-step

Раньше Го пытался ввести контракты в язык. Но разница между контрактами и интерфейсами была слишком непонятной, поэтому опубликовали драфт-v2. В двух словах - дженерики го как с++, т.е. код генерируется для каждого типа на этапе компиляции. В результате получается обычный код на го.

P.S. Господи, они хотят синтаксис F(T), а не F или любой другой! Это ужасно, в декларации функции итак уже слишком много скобок: func (this A) foo(b B) (c C)

Why Go Generics + ранний дизайн (contract):
https://youtu.be/WzgLqE-3IhY

Драфт:
https://go.googlesource.com/proposal/+/refs/heads/master/design/go2draft-type-parameters.md

#go #generics

https://youtu.be/mFUXNMfaciE?list=WL

Ranges TS - видео от автора Эрика Ниблера

Объясняет, как использовать рэнжи в очень элегантном примере с календарями. Получается эдакий функциональный-cpp. Код красивый и понятный, аж захотелось пойти уже и изучить хаскель, или хотя бы курс по функпроге вспомнить!

По перфомансу непонятно: вроде такая вложенность, векторы внутри трансформа должны заставить все это работать не самым оптимальным образом. Но: 1) это все хорошо инлайнится компиляторами 2) тебе не всегда нужен перфоманс (особенно когда пишешь календарь), иногда важнее maintainability: понятность, возможность вносить изменения.

С таким подходом программа не содержит стейта, не содержит (явно) циклов, ифов и всего этого контрол-флоу, который взрывает мозг.

Понравилась фраза: "Correct by design".

TODO: ranges + coros - как это сочетается?

#cpp #ranges #cpp_20

Я для себя выделяю два типа модел чекинга: stateful и stateless.

С первым все понятно: храним состояния явно, не посещаем их повторно.

Со вторым интереснее. Состояния не хранятся явно, поэтому нужны техники, которые позволили бы не посещать повторные состояния. Даже не состояния, а целые траектории.

Есть POR, но для рантайма эти техники сложны - нужно статически анализировать программу. Знать, что поток предпримет в будущем.

Поэтому есть другая крутая техника, специально для stateless runtime-а - DPOR.

https://users.soe.ucsc.edu/~cormac/papers/popl05.pdf

Ее суть - это наблюдение, что две траектории могут привести в один стейт. Какие траектории обладают таким свойством? А те, в которых действия независимы - т.е. неформально - конечное состояние не зависит от порядка применения этих действий.

Чтобы эту инфу трекать прямо в рантайме, DPOR не анализирует ничего сразу же - он трекает точки динамически. Т.е. запускает как попало программу, и по дороге делает бэктрекинг: берет потенциальное действие из текущего стейта, и находит действие в прошлом, с которым это действие зависимо. Только такие нам и интересны. Дальше запоминает это, и позже (обход дфс) попытается "свапнуть" действия. Пример - лоад и стор одного атомика.

Реализация такой техники - это векторные часы. Прямо как в тсане!

Самое крутое, что это не теоретическая забава. Ее реально применяют, например Rust по мотивам написал чекер (loom), который еще и слабые атомики поддерживает (векторные часы же!):
https://github.com/tokio-rs/loom

А вот реальное применение loom - тестирование планировщика из tokio:
https://tokio.rs/blog/2019-10-scheduler/

#dpor #rust #loom #model_checking #scheduler #tokio

Интересный подход Rust к async-io:
https://www.youtube.com/watch?v=lJ3NC-R3gSI

https://www.youtube.com/watch?v=NNwK5ZPAJCk&list=LLJlwnbUloqmnZOaqE7ZpOxQ&index=6

https://www.youtube.com/watch?v=skos4B5x7qE&list=LLJlwnbUloqmnZOaqE7ZpOxQ&index=2

Видео в порядке от общего к частному.
Цель раста - zero-cost abstractions.
В Rust-е решили, что зеленые треды - это слишком дорого, + раст часто зовут из си. Для зеленых тредов пришлось бы писать свой рантайм, и получается, из си вызывать его. До-ро-го!
Поэтому асинхронщина в раст - это фьючи + стейт-машина из await-ов засчет компилятора.
Причем фьючи очень (для меня) необычные: на них не вешаются колбеки. Потому что тогда пришлось бы выделять место на хипе для них и тратиться на сихнронизацию (???). Приходят на помощь poll-based фьючи! Итого, абстракция распадается на: executor (он поллит фьючу), reactor (делает ио и будит фьючу по завершении ио), future (юнит работы, стейт-машина из кусочков с await-ом).

Пока непонятные вопросы: а poll происходит только тогда, когда надо? Не жжется ли cpu? Что придумали в C++, ведь там тоже должна быть zero-cost абстракция?

#rust #async #zero_cost