Из последовательного алгоритма — в многопоточный

1. Четыре паттерна циклов

Инструмент дня — параллельный режим Numba: декоратор получает флаг parallel=True, а цикл, который вы разрешаете разложить по потокам, помечается prange вместо range. Потоки здесь настоящие, на всех ядрах — и потому вопрос «какой цикл так можно» встаёт в полный рост. Разберём четыре паттерна от простого к безнадёжному.

1.1. Map: независимые итерации

from numba import njit, prange

@njit(parallel=True)
def heavy_map(a, out):
    for i in prange(a.size):      # единственное отличие от последовательной версии
        s = 0.0
        for k in range(200):       # внутренний цикл остаётся range —
            s += (a[i] * k) % 7    # параллелим внешний, работу на итерацию
        out[i] = s

Итерация i читает a[i], пишет out[i] и не смотрит на соседей — критерий независимости выполнен, порядок безразличен. Замер на миллионе элементов (машина с 24 ядрами; ваши числа будут другими, но порядок сохранится): последовательная @njit-версия — 1851 мс, prange — 95 мс, ускорение в 19.5 раза. Не в 24: потоки надо создать, куски раздать, память у всех общая. Результаты обеих версий совпадают до бита.

1.2. Reduce: свернуть массив в число

@njit(parallel=True)
def par_sum(a):
    s = 0.0
    for i in prange(a.size):
        s += a[i]                  # формально — зависимость через s!
    return s

Каждая итерация читает и пишет общую переменную s — по букве закона это зависимость. Но сложение ассоциативно, и Numba распознаёт редукцию: каждый поток копит частичную сумму в своей локальной копии s, а в конце частичные суммы складываются — то же дерево, что вы видели в C05, только построенное компилятором автоматически. Проверка: par_sum совпадает с a.sum() (в пределах допуска округления — сложение float в другом порядке, знакомая история из C05).

1.3. Scan и рекуррентность: где кончается автоматика

# scan — накопленные (префиксные) суммы: x[i] = a[0] + … + a[i]
# рекуррентность — общий случай: x[i] = f(x[i-1], a[i])
for i in range(1, n):
    x[i] = x[i - 1] + a[i]

Итерация i читает x[i−1] — результат предыдущей итерации. Для префиксных сумм (scan) параллельный алгоритм существует — два прохода деревом, как в редукции, — но его надо писать руками или брать готовый (np.cumsum внутри @njit); автоматика prange такой перестройки не делает. А для общей рекуррентности — скажем, y[i] = a·y[i−1] + x[i], это фильтр из обработки сигналов — честного параллельного варианта без переформулировки математики нет вовсе: цепочка есть цепочка.

2. Чего компилятор не сможет — и как это выглядит

Автопараллелизатор консервативен там, где может проверить, и доверчив там, где не может. Обе стороны опасны по-своему: первая молча оставляет цикл последовательным, вторая позволяет вам выстрелить себе в ногу. Разберём главные случаи — все примеры ниже реально запущены, числа настоящие (скрипт p02_prange_races.py в папке сode).

2.1. Гонка: prange делает то, что сказано

@njit(parallel=True)
def race_counter(n):
    c = np.zeros(1)
    for i in prange(n):
        c[0] += 1.0       # НЕ скаляр, а ячейка массива — редукция НЕ распознаётся
    return c[0]

# четыре запуска race_counter(10_000_000), ожидаем 10 000 000:
#   833334, 833333, 833334, 833334

Потерялось 92% инкрементов: 24 потока одновременно выполняли «прочитать c[0], прибавить, записать» и затирали работу друг друга. Заметьте разницу с par_sum: там аккумулятором был скаляр s — его Numba узнала как редукцию и обезопасила; здесь ячейка массива — а записи в массив компилятор честно считает вашей ответственностью. Ещё коварнее гонка по косвенному индексу:

for i in prange(n):
    hist[bins[i]] += 1     # две итерации с одинаковым bins[i] — гонка;
                           # проявится только на данных с повторами

Гистограмма на уникальных данных пройдёт все тесты — и начнёт терять отсчёты на реальных. Лечение любой такой гонки одно: превратить её в настоящую редукцию — дать каждому потоку свой локальный буфер и слить буферы после цикла (или, для скаляра, просто копить в скаляр).

2.2. Рекуррентность: prange даёт неверный результат

@njit(parallel=True)
def cumsum_broken(a):
    x = np.empty_like(a)
    x[0] = a[0]
    for i in prange(1, a.size):
        x[i] = x[i - 1] + a[i]    # чтение чужой итерации
    return x

# на массиве из миллиона единиц правильный последний элемент — 1 000 000
# prange-версия вернула 41 666; совпали лишь 41 668 элементов из миллиона

Каждый поток получил свой кусок диапазона и начал его с x[начало−1], в котором ещё не побывал сосед: цепочка порвалась на границах кусков (41 666 ≈ миллион / 24 — размер куска одного потока: верен только первый кусок). Компилятор не обязан ловить такое: prange — это ваше обещание, что итерации независимы. Нарушили обещание — получили мусор, без предупреждений.

2.3. Что ещё остаётся последовательным

• Нераспознанные редукции: свёртка через ячейку массива (выше), два аккумулятора, обновляемых взаимозависимо, экзотические операции — распознаются только +=, *= и min/max над скаляром.
• break и ранний выход: prange-цикл не умеет прерываться — куски уже розданы потокам; «найти первый подходящий» параллелится иначе (найти все кандидаты map-ом, взять минимальный индекс редукцией).
• Побочные эффекты: печать, запись в файл, append в список — либо не скомпилируются, либо выполнятся в непредсказуемом порядке.
• Зависимость через управление: если условие итерации i зависит от результатов прошлых итераций — это рекуррентность в маскировке.

3. Спросить компилятор: parallel_diagnostics

Хорошая новость: гадать не обязательно. После первого вызова у функции можно спросить, что параллелизатор сделал на самом деле:

heavy_map(a, out)                          # сначала вызвать — компиляция по факту
heavy_map.parallel_diagnostics(level=1)

# ================================================================
#  Parallel Accelerator Optimizing: Function heavy_map ...
# ================================================================
#
#     for i in prange(a.size):-------| #0    ← цикл получил номер: параллелится
#         s = 0.0                    |
#         ...
# ------------------- After Optimisation ------------------------
# Parallel structure is already optimal.

Пометка -------| #0 напротив цикла означает «стал параллельным циклом №0»; циклы без номера остались последовательными. На уровнях level=2–4 отчёт подробнее: какие циклы слиты вместе (fusion), какие выражения numpy превращены в параллельные циклы, где размещены аллокации. Привычка одна и простая: пометили цикл prange — спросите diagnostics, получил ли он номер. Минута проверки против часа недоумения «почему не быстрее».

Кстати о «не быстрее»: parallel=True параллелит и целые numpy-выражения над массивами (a + b * c внутри @njit), так что иногда выигрыш приходит даже без единого prange. А регулировать число потоков можно переменной окружения NUMBA_NUM_THREADS или функцией numba.set_num_threads — полезно для честных графиков «ускорение от числа ядер».

4. Врезка: а почему не threading?

Ветераны Python спросят: зачем Numba, если в стандартной библиотеке есть threading? Ответ — GIL, глобальная блокировка интерпретатора: байткод Python в каждый момент выполняет ровно один поток, сколько бы их ни создали. Потоки threading годятся для параллельного ожидания (сеть, диски) — но вычислять параллельно не могут: вычислительный цикл на четырёх threading-потоках работает не быстрее, а из-за переключений — чуть медленнее однопоточного. Код @njit — не байткод: на время его работы GIL отпускается, и потоки prange считают по-настоящему одновременно. Классическая альтернатива — multiprocessing (отдельные процессы вместо потоков) — обходит GIL ценой копирования данных между процессами; для числовых массивов prange и легче, и быстрее.

5. Тренажёр: параллелится или нет

Контрольные вопросы

• Назовите четыре паттерна циклов и судьбу каждого при параллелизации.
  Map — независимые итерации, параллелится заменой range на prange. Reduce — свёртка в скаляр; Numba распознаёт += , *=, min/max и строит частичные суммы автоматически. Scan — префиксные накопления; параллелится, но специальным двухпроходным алгоритмом, автоматика этого не делает. Рекуррентность — итерация зависит от результата предыдущей; не параллелится без изменения математики.
• Почему s += a[i] в prange работает верно, а c[0] += 1.0 теряет 92% инкрементов?
  Скаляр s компилятор распознаёт как редукцию: каждый поток копит свою локальную копию, в конце копии складываются. Ячейка массива c[0] редукцией не считается — записи в массивы остаются на совести программиста, и 24 потока затирают чтение-модификацию-запись друг друга. Проверено запуском: 833 334 вместо 10 000 000.
• Что произошло с накопленной суммой при prange и почему число 41 666 не случайно?
  Диапазон порезали на куски по числу потоков; каждый поток начал свой кусок с x[начало−1], куда сосед ещё ничего не записал. Верным остался только первый кусок: 1 000 000 / 24 ≈ 41 666 — ровно размер куска одного потока. prange — обещание независимости; за нарушение компилятор не отвечает.
• Почему «тест сошёлся один раз» не доказывает отсутствие гонки и что доказывает?
  Гонка вероятностна: при удачном планировании потоков, малых данных или свободной машине результат может совпасть. Доказательство — анализ кода: читает ли итерация данные, которые пишет другая итерация; пишут ли разные итерации в одну ячейку (в том числе по косвенному индексу). Практическая страховка — много повторных запусков и сравнение.
• Как проверить, что prange-цикл действительно стал параллельным?
  Вызвать функцию (чтобы прошла компиляция) и спросить fn.parallel_diagnostics(level=1): параллельные циклы получают номер-пометку «#0» напротив строки, оставшиеся последовательными — нет. На больших уровнях отчёт показывает слияние циклов и параллеленные numpy-выражения.
• Почему threading не ускоряет вычисления и почему prange ускоряет?
  GIL: байткод Python исполняет один поток в каждый момент, потоки threading полезны только для ожидания (сеть, диск). Скомпилированный @njit-код байткодом не является — GIL на время его работы отпускается, и потоки prange считают на всех ядрах по-настоящему одновременно.

Источники

1. Automatic parallelization with @jit // Numba Documentation : [сайт]. — URL: https://numba.readthedocs.io/en/latest/user/parallel.html (дата обращения: 09.07.2026).
2. The Threading Layers // Numba Documentation : [сайт]. — URL: https://numba.readthedocs.io/en/latest/user/threading-layer.html (дата обращения: 09.07.2026).
3. GlobalInterpreterLock // Python Wiki : [сайт]. — URL: https://wiki.python.org/moin/GlobalInterpreterLock (дата обращения: 09.07.2026).