#algo #article
Branch and Bound — объяснение метода ветвей и границ на наглядном примере задачи коммивояжёра
Branch and Bound — объяснение метода ветвей и границ на наглядном примере задачи коммивояжёра
oleg_log
Красивая история как Rockstar парсили 10мб жсон в GTA V во имя сатане. Для заядлых геймеров даже патчик есть. Неофиц. https://nee.lv/2021/02/28/How-I-cut-GTA-Online-loading-times-by-70/ Напомнило https://t.iss.one/oleg_log/3970
#prog #performancetrap #article
It Can Happen to You
Или как один человек — достаточно умный, чтобы написать невероятно быстрый 3d-визуализатор stl-файлов, допустил ровно ту же самую ошибку, из-за чего время на парсинг формата в текстовой форме превосходило время, потраченное на все остальные стадии визуализации, вместе взятые.
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 варианты. Цитируя статью:
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 варианты. Цитируя статью:
👍2
Furthermore, we illustrate how the same challenge and tradeoff has been met and addressed by the PL community, and show a number of results that can be carried over from the lessons learned there. Specifically, we study how the PL community’s answer to the problem, stream fusion [11], can be adapted to the query processing scenario, and show how it combines the advantages of the pull and push approaches. Furthermore, we demonstrate how we can use ideas from the push approach to solve well-known limitations of stream fusion. As a result, we construct a query engine which combines the benefits of both push and pull approaches. In essence, this engine is a pull-based engine on a coarse level of granularity, however, on a finer level of granularity, it pushes the individual data tuples.
Блог*
#prog #db #article Push vs. Pull-Based Loop Fusion in Query Engines (pdf) Для того, чтобы исполнить SQL-запрос, движок базы данных сначала должен скомпилировать его из декларативного представления в конкретный план, который уже можно интерпретировать. Технически…
#prog #article
Про папир прочитал тут: Query Engines: Push vs. Pull. Если вас не волнует тот новый гибридный подход, но вы всё же хотите почитать про отличия двух подходов, то по ссылке можно почитать сравнение, которое несколько более понятно обычному смертному.
Про папир прочитал тут: Query Engines: Push vs. Pull. Если вас не волнует тот новый гибридный подход, но вы всё же хотите почитать про отличия двух подходов, то по ссылке можно почитать сравнение, которое несколько более понятно обычному смертному.
#bio
TIL: Пенисная кость реально существует. У человека её, вопреки несколько расхожему заблуждению, нет, но есть у некоторых млекопитающих, в частности, у горилл и шимпанзе.
TIL: Пенисная кость реально существует. У человека её, вопреки несколько расхожему заблуждению, нет, но есть у некоторых млекопитающих, в частности, у горилл и шимпанзе.
Wikipedia
Baculum
bone in the penis
Forwarded from waffle private
tip: функции в расте не могут иметь более 65535 аргументов
😢17😱7🤯4
Forwarded from There will be no singularity
MASKING POLICY in PostgreSql:
https://www.postgresql.org/about/news/postgresql-anonymizer-10-privacy-by-design-for-postgres-2452/
https://www.postgresql.org/about/news/postgresql-anonymizer-10-privacy-by-design-for-postgres-2452/
PostgreSQL News
PostgreSQL Anonymizer 1.0: Privacy By Design For Postgres
Limoges, France, May 17th, 2022 `PostgreSQL Anonymizer` is an extension that hides or replaces personally identifiable information (PII) or commercially …
👍1
#prog #rust #rustlib
Impl-tools: beyond derive
Библиотека для уменьшения бойлерплейта при написании реализаций трейтов.
Impl-tools: beyond derive
Библиотека для уменьшения бойлерплейта при написании реализаций трейтов.
#[impl_tools::impl_default(Option::None)]
pub enum Option<T> {
None,
Some(T),
}
#[impl_tools::autoimpl(Deref, DerefMut using self.animal)]
struct Named<A> {
name: String,
animal: A,
}
#[autoimpl(Clone, Debug, Default where T: trait)]
struct Wrapper<T>(T);👍4💩1
😒🤚 Читать статьи Амоса, чтобы лучше знать Rust
😒🤚 Читать статьи Амоса, чтобы лучше ругать Go
😏👉 Читать статьи Амоса, чтобы расширять словарный запас
😒🤚 Читать статьи Амоса, чтобы лучше ругать Go
😏👉 Читать статьи Амоса, чтобы расширять словарный запас
🥰5👍2🤮1