#science #article

Inverse Occam’s razor https://www.nature.com/articles/s41567-022-01575-2
https://arxiv.org/abs/2204.08284

#prog #design #article

When fonts fall (Система font fallback: что происходит, когда шрифт не может найти нужный символ)

Тёмные темы в софте получают непропорционально много внимания

Как это называется, когда вместо иконки WhatsApp тыкаешь иконку приложения Сбера?

MRE = Minimal Rust example

#prog #db #postgresql #sql #article

«Ленивый сахар» PostgreSQL

SQL - декларативный язык - то есть вы описываете "что" хотите получить, а СУБД сама решает, "как" именно она будет это делать. Некоторые из них при этом позволяют им "подсказывать", как именно лучше выполнять запрос, но PostgreSQL - нет.

Тем не менее, "синтаксический сахар" некоторых языковых конструкций позволяет не только писать меньше кода (учите матчасть!), но и добиться, что ваша база будет делать часть вычислений "лениво", только при фактической необходимости.

Тем временем я завершил майский челлендж Leetcode, в кои-то веки не пропустив ни одного дня. И, кстати, написал самое быстрое решение на Rust для последней задачи.

#prog #rust

Nice

#prog #rust

Для тех случаев, когда отравленность надо убирать, причём не безусловно, добавили метод Mutex::clear_poison (и RwLock::clear_poison)

В СМЫСЛЕ УЖЕ ИЮНЬ

Круг замкнулся, получается

#prog #rust #article

BonsaiDb performance update: A deep-dive on file synchronization

tl;dr: Reading data from BonsaiDb is still very efficient, but due to mistakes in benchmarking, writes are quite slow for workflows that insert or update a lot of data in a single collection. I am still excited and motivated to build BonsaiDb, but I am currently uncertain whether I will still write my own low-level database layer. All assumptions about BonsaiDb's performance must be reset.

BTW, судя по всему, в MacOS нету способа надёжно записать данные на диск.

#prog #db #article

Durability and Redo Logging, или немного о том, как базы данных обеспечивают сохранность данных при помощи redo log (aka "write ahead log" — кмк, довольно сбивающий с толку термин).

#algo #article

Branch and Bound — объяснение метода ветвей и границ на наглядном примере задачи коммивояжёра

#prog #performancetrap #article

It Can Happen to You

Или как один человек — достаточно умный, чтобы написать невероятно быстрый 3d-визуализатор stl-файлов, допустил ровно ту же самую ошибку, из-за чего время на парсинг формата в текстовой форме превосходило время, потраченное на все остальные стадии визуализации, вместе взятые.

#prog #db #article

Push vs. Pull-Based Loop Fusion in Query Engines (pdf)

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

Pull-based подход — который исторически был придуман ранее — предполагает композицию операторов, каждый из которых предоставляет метод next. Данные материализуются по мере последовательных вызовов next у самого верхнего оператора, который вызывает next у нижележащего, тот, в свою очередь, вызывает next у оператора ещё ниже и так далее вплоть до непосредственного источника данных. В данном подходе направления потока управления и потока данных противоположны. Если вам это всё кажется похожим на итератор, то интуиция вас не подводит — это соответствует паттерну "итератор" из ООП, и данный подход был описан под названием Volcano Iterator model.

Альтернативный подход — push-based — предполагает составление цепочки операторов, в которых источник данных активно передаёт данные вверх вплоть до корневого SELECT. Не смотря на то, что этот подход кажется менее естественным, порождаемый им код имеет более простой граф потока управления и потому лучше подвергается оптимизациям компилятора, что делает этот подход значительно быстрее pull-based варианта — на порядок.

...Ну или так утверждалось ранее в работах, которые цитируют авторы этой статьи. Они утверждают, что данное мнение необоснованно, поскольку в предшествующих сравнениях сравнивались версии push-based с оптимизациями компилятора — с инлайнингом — и pull-based без оптимизаций. Как они сами пишут:

Recent papers [42, 30] seem to suggest that this push-model consistently leads to better query processing performance than the pull model, even though no direct, fair comparisons are provided. One of the main contributions of this paper is to debunk this myth. As we show, if compared fairly, push and pull based engines have very similar performance, with individual strengths and weaknesses, and neither is a clear winner. Push engines have in essence only been considered in the context of query compilation, conflating the potential advantages of the push paradigm with those of code inlining. To compare them fairly, one has to decouple these aspects.

Для того, чтобы достичь этого самого decoupling, авторы показывают соответствие между операторами запросов и комбинаторами коллекций (такими, как std::iter или LINQ) и далее экспериментируют с кодом, который реализует различные подходы на коллекциях. Такой подход они считают обоснованными, поскольку фактически именно к этому и сводятся базы данных, размещающие данные в оперативной памяти, а в базах данных, размещающих данные на диске, время на пересылку данных из диска в память перекрывает разницу в производительности подходов.

Авторы показывают, что эти два подхода, будучи подверженными одному и тому же набору оптимизаций, показывают схожую производительность — push-based обычно быстрее, но незначительно. Более того, в запросах, в которых можно утилизировать ленивость — с операторами LIMIT и MERGE JOIN — все преимущества push-based подхода вылетают в трубу, давая значительно худшую производительность. Сравнения проводились как на микробенчмарках с простыми запросами, так и с эквивалентами запросов из тестов TPC-H.

Второй вклад этой статьи — предложенный ими новый подход для движков запросов, который хитрым способом объединяет pull- и push-based варианты. Цитируя статью:

The Антон urge to read computer science papers in the middle of night