Построение множества Мандельброта — классический пример чрезвычайно параллельной задачи (embarrassingly parallel problem).
Вначале мы разберем наивную реализацию, поиграемся с интринсиками (intrinsics) и, не теряя переносимости, заставим компилятор генерировать нам SIMD-инструкции. Далее добавим многопоточность и в заключение обесценим все наши старания несколькими строчками на CUDA.
Многие современные вычислительные задачи, в частности повсеместная обработка изображений и звука или работа с матрицами для ИИ, хорошо поддаются параллелизации на уровне данных. Входные данные таких задач представлены в виде большого вектора данных, элементы которого можно обрабатывать независимо. Чтобы ускорить вычисления с векторами, производители процессоров добавили в архитектуры специальные Single Instruction, Multiple Data инструкции, которые позволяют работать за одну инструкцию сразу с несколькими элементами.
Хотелось бы прокомментировать публикацию Ильи Кабанова в Медузе по поводу новых разработок в алгоритмах хеширования: "Optimal Bounds for Open Addressing Without Reordering" (Farach-Colton, Krapivin, and Kuszmaul, 2025) и последующую "The Bathroom Model: A Realistic Approach to Hash Table Algorithm Optimization" (Wang, 2025). И особенно кликбейтное: "в перспективе метод Крапивина и его коллег может ускорить многие процессы в интернете."
Я около 7 лет очень плотно занимался темой хеш-таблиц и написал много их вариантов: Читать полностью »
В этот раз прорабатывались следующие большие темы:
В этот раз без внимания не остались темы:
Старую собаку новым трюкам не обучишь, вот и я взялся за старое. Blurhash — это компактный способ представления размытой превьюшки изображения в виде ASCII-строки. Разработан финской компанией Wolt (аналог Delivery Club). Давно хотелось внедрить такое к себе в API, чтобы любой клиент мог более плавно и изящно делать загрузку контент на своем сайте. Но сколько я на него смотрел — всегда не давала покоя скорость работы, уж больно медленно и «в лоб» он был написан. Но вот время пришло наконец-то разобраться, что же он так медленно работает.
У меня в портфолио есть несколько готовых пет-проектов на Rust, и я заметил, что позиция «а у нас уже получилась DataFrame?» нисколько меня не устраивает. Поэтому я подумал, не сделать ли мне элементарный контейнер, который решал бы мою конкретную задачу. Но этот проект вышел из-под контроля.
Год спустя, написав немало кода, я создал одну из самых быстрых библиотек датафреймов, применимую в Rust и Python. Вот мой первый официальный «Hello World» на polars, размещённый у меня в блоге. Надеюсь, что с помощью этого поста я смогу пояснить читателю некоторые решения, которые мне довелось принять при проектировании, и вам станет понятнее, как Polars работает под капотом.
Читать полностью »
Fail2ban — утилита чрезвычайно полезная во многих случаях. Думаю, многие используют её для того, чтобы в автоматическом режиме блокировать особенно назойливых «посетителей». К сожалению, если входящий поток становится слишком большим, fail2ban теряет все свои полезные свойства, потому что разбор лога безнадёжно отстаёт от реальности.
Вот, например, лог nginx из 100 тысяч строчек fail2ban при самых простых настройках (failregex='^<ADDR>') разбирает порядка 45 секунд:
$ fail2ban-regex nginx.log '^<ADDR>'
Running tests
=============
Use failregex line : ^<ADDR>Читать полностью »
Снова поговорим об ускорении работы клиентской стороны веб-приложения и о том, как для этого задействовать все вычислительные ресурсы процессора.
В предыдущей части мы нарисовали фрактал Ньютона с помощью WebAssembly на Rust. В этой части мы задействуем SIMD команды и параллельные вычисления, чтобы добиться ещё большей производительности.
Вживую увидеть прирост скорости можно на онлайн-демо. На моём компьютере она составляет ~900% по сравнению с обычной реализацией на wasm.
Читать полностью »