Параллельное программирование *

Машина Тьюринга (МТ) не сферический конь в вакууме программистского бытия. Она не про «единички-нолики» и елозанье вдоль ленты, а про гимнастику мозгов для программистов. Продолжим тему МТ, начатую в [1]. Ее программирование увлекательная и, без сомнения, серьезная работа по созданию алгоритмов при миним миниморум средств на их реализацию Тем и привлекательна. Особенно на этапах обучения алгоритмическому мышлению.

Продолжим тему нахождения наибольшего общего делителя (НОД) двух чисел для МТ. Только теперь это будет обычное программирование. По счастью ли по совпадению нужный нам алгоритм приведен в книге Н.Вирта [2]. Его блок-схема (БС) приведена на рис. 1. Обычная и ни чем не примечательная БС и совсем простой алгоритм. Особенно в сравнении с рассмотренными для МТ. Привел он его, преследуя другие цели, но сейчас не это главное.

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

Ниже — измерение на работающей реализации: во сколько раз каждая редукция сокращает пространство состояний, сколько она стоит в пересчёте на состояние, на каких спецификациях она не даёт ничего, и — главное — экспериментальная проверка того, что четыре условия ample‑множества действительно необходимы, а не унаследованы из статьи без разбора.

Три результата, ради которых стоит читать дальше:

Если вы начинающий программист и у Вас нет машины, то лучшее решение - машина Тьюринга (МТ)! Я в этом вам помогу, а еще Макконнел. Но и не только он один.

Первая моя статья на Хабре о машинах Тьюринга это про тяжелый грузовик [1]. А оно такое надо? Начинать лучше с чего-то полегче. Этим и займемся. Хотя основа или, так сказать, базис по большому счету будет один. Но, ведь, между карьерным самосвалом и самой простой «инвалидкой» тоже есть много общего? И то и другое явно не самолет.

В монографиях Макконнела [2], Карпова [3] и еще много где устройство МТ расписано по винтикам, которых не так уж и много. Я, например, когда-то начинал с книги А.Трахтенброта [4].  Также можно, не мудрствуя лукаво, запустить эмулятор МТ. Их  в Инете найти не сложно. И сразу погонять, не вникая в «винтики». Но это для самых отвязных, т.е. тех, кто не боится снести крышу.

Я предпочитаю среднее. Глубины теории для любителей. По мне гораздо лучше через «ручки». Для этого нужно иметь «конструктор», на котором можно  не только тренироваться, но и реализовать любые фантазии.

Подобие конструктора можно найти у Карпова Ю.Г. Но это пара набросков на псевдокоде. Мы же возьмем конкретный язык и конкретную реализацию. А для совсем уж ленивых будет доступен код по ссылке на Git-репозитарий.

Подобно Макконнелу я за «активный обучающий подход». Т.е. следую его заветам. Хотя следовал я им задолго до знакомства  с его идеями. И это даже хорошо, т.к. не отвлекало. В результате я пошел  даже немного дальше. Для анализа алгоритмов использовал не псевдокод, а другой вариант – формальную вычислительную модель и ее реализацию. Такой «математический псевдокод» позволяет делать  анализ проще, глубже и точнее. По результатам написал статью во времена, когда журналы еще издавались [5].

Когда-то наш почтовый загрузчик был обычным методом с @Scheduled. Раз в 30 минут он подключался к ящикам, искал новые вложения и запускал их обработку. Решение было простым, понятным и долгое время вполне рабочим.

Через несколько итераций вокруг того же загрузчика уже существовали IMAP IDLE listener'ы, PostgreSQL leases, heartbeat экземпляров приложения, перебалансировка почтовых ящиков между pod'ами, UID checkpoints, постоянная идемпотентность и отдельная обработка FolderClosedException. В какой-то момент мы даже попробовали держать несколько IMAP-соединений к одному ящику, но затем сознательно удалили эту часть архитектуры.

Это история не о том, как мы «заменили polling на push» одной настройкой. Она о том, как безобидный интеграционный адаптер постепенно превратился в маленькую распределённую систему. И о границе параллелизма, которую мы сначала провели не там.

Я делаю NotiBox — Pusher‑совместимый сервис realtime уведомлений. Под капотом я использую Sockudo — WebSocket сервер на Rust. Прежде чем показывать реальным пользователям, я решил проверить, на сколько Sockudo на самом деле «blazingly fast».

Я ожидал, что это будет лёгкая прогулка, типичное тестирование нагрузки. Даёшь мало ресурсов серверу, запускаешь бенчмарк, видишь что он захлёбывается запросами в какой‑то момент, и фиксируешь показатели.

Идеальный сценарий — полная загрузка процессора, памяти или сети, тогда ты реально нашёл предел ресурсов. Проверяешь масштабируемость и готово.

Другой сценарий — ничего не перегружено, но новые соединения/запросы не проходят, растёт задержка ответов. Это тоже ожидаемо и понятно как чинить: смотришь на TIME WAIT сокеты, max open files, и другие «предохранители».

А что делать, если там тоже всё по нулям? Вот тут начинается настоящее приключение.

В данной статье я хочу рассказать о проверке одной гипотезы - возможности использования shared memory для ускорения параллельной агрегации методом хэширования. Статья Xu&Marcus, PVLDB, 2025 утверждает, что общая хэш-таблица — незаслуженно списанный со счетов способ параллельной агрегации, если использовать т.н. тикетинг и разделить операции поиска группы и обновления агрегата.

Звучит завлекательно. Собираем в кучу свои знания Internals, подписку на Claude и, поскольку в период летних Heat Wave выходные всё-равно проходят дома под кондиционером - разрабатываем идею так глубоко, насколько это получится.

На четвертом курсе Стэнфорда* я записался на урок по параллельному программированию. Изучив алгоритмы, контейнеры данных и математику, стоящую за нейронными сетками, понял, что толком не знаю, что такое микропроцессор. Было очень интересно углубиться в компьютерную архитектуру и понять лучше, как работает то, для чего мы разрабатываем софт и чем пользуемся ежедневно.

Преподаватели были одни из лучших в моём опыте в Стэнфорде*. Кэйвон Фатахалиан—эксперт в области графики и производительности, а Кунле Олукотун—пионер в создании многоядерных микропроцессоров.

_{Кредит обложки: David Baillot.}

Закон Мура, похоже, задвинули, т.к. упоминается он все реже и реже. А вот закон Амдала нет-нет, да вспомним. Тем более, что он приведен чуть ли не в каждой книге по параллельному программированию. А, ведь, есть и другие законы типа закона Гроша или гипотезы Минского. Но подобный их статус обязывает ко многому. Однако после детального знакомства с ними это ощущение, как правило, теряется.

В законе Амдала, вроде, все правильно, но что-то не так и не то. Подобные сомнения возникли почти сразу после знакомства с ним. Но, правда, кто я такой, чтобы давать оценку? Да и интересовали меня на тот момент другие проблемы, к которым данный закон имел, как мне представлялось, косвенное отношение.

Однако, «давно не было такого и вот опять» – свежая статья на Хабре про закон Амдала, да еще и с настоятельной рекомендацией его изучать[1]. Пришло, видимо, время мне на эту тему высказаться. Хотя бы в пику его «обязательности чтения», т.к. для тех, кто «проектирует параллельные системы», подобные советы представляются не только излишними, а даже вредными.  

Все это, конечно, с «высоты» нынешних моих позиций. За прошедшее время они стали более строгими. Но все же это только моя личная оценка, но опирающаяся на мой опыт и на общепризнанные научные представления о процессах распараллеливания «реальных задач».

Так давайте попробуем понять кто прав, а кто нет.  А поможет нам математика, которую можно не понимать, можно даже не любить, но не уважать нельзя.

Если 95% вашей задачи выполняется параллельно - максимальное ускорение 20 раз. Хоть 8 процессоров, хоть 8 тысяч. Потолок встроен в задачу, не в железо.

Это закон Амдала. Сформулирован в 1967-м на конференции AFIPS в статье с названием "Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities" - то есть "В защиту одиночного процессора". Амдал пришел объяснить, почему массовый параллелизм не даст обещанного выигрыша для многих реальных задач.

Если ваш сервис одновременно пишет в БД и дёргает внешние API, прямо сейчас у вас есть как минимум один из этих сценариев:

– деньги списаны, заказа в базе нет;
– товар на складе заблокирован навсегда под «призрачный» заказ;
– курьерская служба везёт посылку, которую никто не заказывал.

Это не баги в коде – это архитектурная проблема двойной записи. И у неё есть классическое решение: паттерны Transactional Outbox, Result Table и Saga Compensation. Под катом – не только теория, но и живой рабочий проект на Scala, который можно склонировать и запустить.

Лямбды в C++ выглядят безобидно, пока не начинают жить дольше переменных, которые захватили. Висячие ссылки, мёртвый this, копии состояния в потоках и ограничения std::function часто проходят компиляцию без шума, зато потом превращаются в undefined behavior.

Разбираем пять задач на захваты и время жизни, где ошибка прячется не в синтаксисе, а в неверном предположении о том, кому и сколько живёт объект.

Если вы в 2026 году запускаете LLM в продакшене, то почти наверняка больше всего денег тратите на инференс. Одна неоптимизированная модель размером 70B может сжигать десятки долларов в час на нескольких A100, тогда как грамотно оптимизированный стек дает сопоставимый результат за сравнительно меньшую сумму. При активном продакшене это выливается в тысячи долларов в месяц разницы только за счет настройки инференса.

Но как это сделать?

Недавно я наткнулся на подробный гайд по оптимизации инференса на JobsByCulture. Внутри — перевод статьи + мои наблюдения и мысли поверх.

Каждый раз, когда вы пишете .await, происходит не магия, а вполне конкретный механизм: Future, Waker и опрос состояния. Чтобы увидеть это своими глазами, я написал собственный async-рантайм на Rust с нуля - с executor, reactor на epoll и рабочим TCP-эхо-сервером. По пути разобрался, как именно tokio будит ваши задачи, и нашёл баг, который тихо висел у меня в проде. Внутри - весь код целиком и объяснение без отсылок к чёрным ящикам.

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

В этой части будут разобраны другие важные подходы: семафоры, каналы передачи данных, горячие потоки, модель акторов, последовательные обработчики задач, thread confinement.

Для каждого из этих подходов рассмотрим конкретные реализации, выделим плюсы и минусы, приведём примеры использования. В конце объединим все реализации в общую таблицу.

Исполним обещанное в [1], где упомянута задача о светофоре Ангера [2]. Она интересна формулировкой, которая заметно отличается от аналогичных задач, и утверждением, что более компактного решения, чем предложенное автором монографии, не существует.

Обычно светофоры моргают, «тупо» реализуя фиксированную временную последовательность. В светофоре С..Ангера есть динамизм. Он определяется датчиками, фиксирующими ситуацию на перекрестке. И это само по себе интересно. А утверждение формальным путем, сомневаться в справедливости которого оснований, казалось бы, нет.

Но нет исследователя, который не ставил бы перед собой задачу доказать недоказуемое или опровергнуть неопровергаемое. И один из способов достичь желаемого – создать решение, подтверждающее вашу правоту. Как настоящие исследователи, мы именно это и попытаемся сделать, опровергнув, если удастся, тем самым утверждение С.Ангера.

А начнем мы с реализации светофора в исходной формулировке, хотя и в рамках другой формальной модели [3].

Многозадачность кажется простой темой, пока дело не доходит до Python и GIL. В статье разбирается: чем процесс отличается от программы, зачем нужны потоки, что такое ядро процессора и в чём разница между конкурентностью и параллелизмом. Затем – специфика Python: как GIL влияет на потоки, когда стоит использовать процессы, асинхронность или корутины, и чем они отличаются от green threads. Материал сопровождается схемами, рабочими примерами кода и реальными замерами производительности для CPU-bound и I/O-bound задач, а в конце – практические выводы о том, что и когда выбирать.

Привет, мой читатель с Хабра!

Знаешь ли ты о том, что такое многопоточное программирование? Если да, то это хорошо! Если же нет, то придётся почитать немного скучноватой теории про такую известную технологию программирования, как многопоточное программирование, а затем мы копнём эту тему глубже…

Миллион асинхронных задач на Rust спокойно живёт в нескольких сотнях мегабайт. Сто тысяч корутин на Python нередко упираются в память раньше. Дело не в том, что “Rust быстрый, а Python медленный” - дело в том, ГДЕ физически лежит состояние приостановленной задачи.

Разбираю, во что превращается ваш async fn после компиляции: стейт-машина на стеке против объекта в куче. Сравниваю модели Rust (Tokio), Python (asyncio), C# и JavaScript - кто аллоцирует на каждый await, а кто нет, и почему это видно на счётчике RAM при 100k задач.

Внутри: что генерирует компилятор, куда уезжает состояние между await, stackful против stackless, и что с этим делать сегодня.

Ключевые особенности:

Расчёт опорной траектории на 5000 бит всего один раз.
Реактивный расчёт миллионов пикселей на аппаратном double.
При использовании чисел с плавающей запятой двойной точности (порядка ) теория возмущений позволяет приблизиться к уровню - не дальше.
Революционный алгоритм Reference Reset to Zero.
Настоящий SSAA 2x2 для идеально сглаженного изображения.
Параллелизм OpenMP для высокоскоростного многопоточного рендеринга.
Синхронизация через DwmFlush для плавного вывода кадров.
Динамическое вращение палитры для создания классического эффекта.

https://github.com/Divetoxx/Mandelbrot-2#russian

Это Гитхаб с Mandelbrot_AVX2.exe и Mandelbrot_SSE3.exe

А тут полный код на языке С++ - main.cpp

В этой статье я расскажу, на какие подводные камни я споткнулся при разработке своего пет‑проекта — мониторинга сайтов на Golang, аналог UptimeRobot.

Начнем издалека... Я хотел разработать пет‑проект, но не банальный todolist, а что‑то свежее, интересное в плане архитектуры и реализации. Шерстя по просторам интернета, я наткнулся на UptimeRobot — сервис для мониторинга сайтов. Азарт и любопытство взяли верх и я начал продумывать, как буду разрабатывать «свой» UptimeRobot. Думал — делов на пару недель от силы. Ведь принцип прост: дергать URL по таймеру и проверять код ответа и всё. Но на практике все оказалось намного сложнее, чем я изначально представлял...