Паттерны параллелизма в Rust
Финальный блок: как всё это применяют. Спрашивают про rayon, воровство задач, почему параллельные счётчики не ускоряются и что делать с мьютексом-узким-местом.
Стержень: параллелизм упирается не в число потоков, а в конкуренцию - за замок, за кэш-линию, за очередь.
// Формулировки: «что делает par_iter?», «что такое false sharing?», «мьютекс стал узким местом - что делать?»
rayon и воровство задач
rayon превращает обход в параллельный одной заменой: iter() на par_iter(). Внутри - пул воркеров и разбиение работы на куски, снаружи - привычные map, filter, sum. Компилятор при этом проверяет, что замыкания Send, а разделяемые данные Sync.
Балансировкой занимается воровство задач: у каждого воркера своя очередь, и, закончив её, он забирает работу из чужой с дальнего конца. Это выравнивает неоднородную нагрузку без глобального замка - тот же принцип лежит в основе планировщика tokio.
// На маленькой коллекции параллельный обход обычно медленнее: разбиение и синхронизация стоят дороже самой работы.
- par_iter
- параллельный итератор rayon поверх пула воркеров
- work stealing
- воровство задач из чужой очереди свободным воркером
Ложное разделение
Восемь потоков инкрементируют каждый свой элемент массива счётчиков - гонки нет, а ускорения тоже нет. Причина в кэше: линия занимает 64 байта, восемь соседних u64 попадают в одну, и запись любого потока инвалидирует её у остальных. Ядра начинают гонять одну линию туда-сюда.
Лечится двумя способами. Разнести данные по разным линиям - выравниванием через repr(align(64)) или паддингом. Или, что чаще проще, накапливать локально в каждом потоке и сложить результаты один раз в конце.
// Это классический пример, где профилировщик показывает «непонятно медленно» при идеально корректном коде: логической конкуренции нет, аппаратная есть.
- кэш-линия
- единица обмена с кэшем, обычно 64 байта
- false sharing
- конкуренция ядер за одну линию без логической гонки
Шардирование и порядок блокировок
Общий кэш под одним Mutex рано или поздно становится узким местом: воркеры стоят в очереди. Первое, что делают, шардируют: массив замков, номер шарда по хешу ключа. Потоки с разными ключами перестают мешать друг другу, и это почти всегда даёт эффект. Увеличение числа воркеров лишь удлиняет ту же очередь.
Второй классический риск - дедлок: первый поток держит A и ждёт B, второй держит B и ждёт A. Rust ловит гонки данных, но порядок захвата это логика программы, и её компилятор не проверяет. Дисциплина одна: глобальный порядок блокировок, короткие секции, где взяты сразу два замка, и try_lock с откатом там, где без двух не обойтись.
- шардирование
- разбиение одной точки конкуренции на N независимых
- дедлок
- взаимная блокировка из-за разного порядка захвата
Как отвечать: «Общий Mutex стал узким местом - что делаешь?»
Сначала смотрю, что именно под замком: часто там оказывается работа, которой там быть не должно - сериализация, запрос наружу, логирование. Сужаю критическую секцию до собственно изменения структуры. Дальше шардирую: вместо одного замка массив по хешу ключа, и потоки с разными ключами перестают конкурировать. RwLock рассматриваю, только если нагрузка реально перекошена в чтения, иначе он добавит сложности без выигрыша. Добавлять воркеров бессмысленно - очередь за тем же замком станет только длиннее.
Ты идёшь по шагам от дешёвых к дорогим и явно отвергаешь неправильный ход с добавлением воркеров. Так отвечает человек, который это чинил.
На чём валятся
- −Ждут ускорения от par_iter на короткой коллекции.
- −Не знают про false sharing и объясняют отсутствие ускорения «накладными расходами».
- −Добавляют потоки вместо того, чтобы убрать конкуренцию.
- −Не могут объяснить, почему компилятор не ловит дедлок.
- −Держат под замком длинную работу вроде сетевого вызова.
Проверьте себя
Пять вопросов из банка по этой подтеме. Всего их 12, остальные разбираются в тренажёре.
- Что такое воровство задач (work stealing) в пуле потоков?A)Задачи перераспределяются по приоритету при каждом запускеB)Освободившийся воркер забирает часть работы из очереди занятогоC)Воркеры дублируют задачи и берут результат того, кто успел раньшеD)Планировщик отбирает поток у долгой задачи и отдаёт короткой
показать ответ и разбор
+B)Освободившийся воркер забирает часть работы из очереди занятого// разбор: У каждого воркера своя очередь; закончив её, он лезет в чужую и забирает работу с дальнего конца. Это выравнивает нагрузку без глобального замка и хорошо переносит неоднородные задачи, когда заранее не известно, какая часть данных окажется тяжёлой. Тот же принцип лежит в основе планировщика tokio.
- Восемь потоков инкрементируют счётчики в общем массиве, каждый свой индекс. Скорость не растёт. Вероятная причина?A)Ложное разделение: счётчики попали в одну кэш-линиюB)Планировщик не распределил потоки по разным ядрамC)Гонка данных: инкременты теряются, и часть работы повторяетсяD)Проверка границ массива добавляет блокировку на каждый доступ
показать ответ и разбор
+A)Ложное разделение: счётчики попали в одну кэш-линию// разбор: Кэш-линия — 64 байта: восемь соседних u64 лежат в одной, и запись любого потока инвалидирует линию у остальных. Формально гонки нет, а по факту ядра дерутся за одну строку кэша. Лечится разнесением по линиям — выравнивание через repr(align(64)) или паддинг, — либо локальным накоплением с одним сложением в конце.
- Общий кэш под Mutex стал узким местом: воркеры стоят в очереди за блокировкой. Что обычно делают первым?A)Увеличивают число воркеров, чтобы компенсировать ожиданиеB)Заменяют Mutex на RwLock и оставляют структуру как естьC)Шардируют: массив замков по хешу ключа вместо одного общегоD)Переносят кэш в атомики через compare_exchange
показать ответ и разбор
+C)Шардируют: массив замков по хешу ключа вместо одного общего// разбор: Шардирование разбивает одну точку конкуренции на N независимых: ключ хешируется в номер шарда, и потоки с разными ключами больше не мешают друг другу. Это дёшево и почти всегда даёт эффект. RwLock помогает только при перекосе в чтения, а рост числа воркеров лишь удлиняет очередь за тем же замком.
- Два потока берут мьютексы A и B в разном порядке. Чем это грозит и как чинится?A)Отравлением мьютексов; лечится обработкой Err при lockB)Ложным разделением; лечится выравниванием данных по кэш-линиямC)Голоданием потока; лечится сменой Mutex на RwLockD)Взаимная блокировка; лечится единым порядком захвата
показать ответ и разбор
+D)Взаимная блокировка; лечится единым порядком захвата// разбор: Классический дедлок: первый держит A и ждёт B, второй держит B и ждёт A. Rust ловит гонки данных, но не порядок захвата — это логика программы. Дисциплина одна: договориться о глобальном порядке блокировок и придерживаться его; вспомогательные меры — try_lock с откатом и сокращение секций, где взяты сразу два замка.
- Сохранится ли порядок элементов, если заменить iter().map().collect() на par_iter().map().collect()?A)Нет: элементы окажутся в порядке завершения обработки, и результат придётся сортироватьB)Нет: rayon собирает результат в произвольном порядке ради скоростиC)Да, но только если коллекция была отсортирована до начала обработкиD)Да: rayon восстанавливает исходный порядок при сборке результата
показать ответ и разбор
+D)Да: rayon восстанавливает исходный порядок при сборке результата// разбор: Параллельные итераторы rayon сохраняют семантику последовательных: работа делится на куски, но результат собирается в исходном порядке. Меняется другое — порядок выполнения замыканий, поэтому побочные эффекты вроде печати перемешаются, а само замыкание обязано быть Send и не зависеть от очерёдности. Для операций, где порядок принципиален, есть fold и reduce с явным нейтральным элементом.
дальше
Теорию прочитали. Навык ставится повторением
В Сеньорчике эта подтема идёт в ежедневных сессиях: движок возвращает её, пока ответы не станут уверенными, и ведёт прогресс отдельно по каждой подтеме. Теория внутри тоже бесплатна, лимит только на количество вопросов в день.