TL;DR. Чтобы быть опытным разработчиком, вы должны признать, что параллелизм не всегда быстрее. Решения, включающие распараллеливание минимальных рабочих нагрузок, не обязательно могут быть быстрее, чем последовательная реализация. Сравнение последовательных и одновременных решений должно быть способом проверки предположений.

Многие разработчики ошибочно полагают, что параллельное решение всегда быстрее, чем последовательное. Это не может быть более неправильным. Общая производительность решения зависит от многих факторов, таких как эффективность нашей структуры кода (параллелизм), какие части можно обрабатывать параллельно и уровень конкуренции между вычислительными единицами. Этот пост напоминает нам о некоторых фундаментальных знаниях о параллелизме в Go; затем мы увидим конкретный пример, в котором параллельное решение не обязательно быстрее.

Перейти по расписанию

Поток — это наименьшая единица обработки, которую может выполнять ОС. Если процесс хочет выполнить несколько действий одновременно, он запускает несколько потоков. Эти нити могут быть:

  • Параллельный. Два или более потока могут запускаться, выполняться и завершаться в перекрывающиеся периоды времени.
  • Параллельно. Одна и та же задача может выполняться несколько раз одновременно.

ОС отвечает за оптимальное планирование процессов потока, чтобы:

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

ПРИМЕЧАНИЕ.Слово "поток" также может иметь другое значение на уровне ЦП. Каждое физическое ядро ​​может состоять из нескольких логических ядер (концепция гиперпоточности), а логическое ядро ​​также называют потоком. В этом посте, когда мы используем слово поток, мы имеем в виду единицу обработки, а не логическое ядро.

Ядро ЦП выполняет разные потоки. Когда он переключается с одного потока на другой, он выполняет операцию, называемую переключением контекста. Активный поток, потребляющий циклы ЦП, находился в состоянии выполняется и переходит в состояние работоспособен , что означает, что он готов к выполнению в ожидании доступного ядра. Переключение контекста считается дорогостоящей операцией, поскольку ОС должна сохранять текущее состояние выполнения потока перед переключением (например, текущие значения регистров).

Как разработчики Go, мы не можем создавать потоки напрямую, но мы можем создавать горутины, которые можно рассматривать как потоки уровня приложения. Однако в то время как поток ОС включается и выключается контекстом ядра ЦП самой ОС, горутина включается и выключается контекстом потока ОС средой выполнения Go. Кроме того, по сравнению с потоком ОС горутина занимает меньше памяти: 2 КБ для горутин из Go 1.4. Поток ОС зависит от ОС, но, например, в Linux/x86–32 размер по умолчанию составляет 2 МБ (см. https://man7.org/linux/man-pages/man3/pthread_create.3.html ). Меньший размер ускоряет переключение контекста.

ПРИМЕЧАНИЕ.Переключение контекста между горутиной и потоком происходит примерно на 80–90 % быстрее, в зависимости от архитектуры.

Давайте теперь обсудим, как работает планировщик Go, чтобы понять, как обрабатываются горутины. Внутри планировщик Go использует следующую терминологию (см. proc.go):

  • G — горутина
  • M — поток ОС (обозначает machine)
  • P — ядро ​​процессора (расшифровывается как процессор).

Каждый поток ОС (M) назначается ядру ЦП (P) планировщиком ОС. Затем каждая горутина (G) запускается на M. Переменная GOMAXPROCS определяет предел Ms, отвечающих за одновременное выполнение кода пользовательского уровня. Но если поток заблокирован в системном вызове (например, ввод-вывод), планировщик может раскрутить больше Ms. Начиная с Go 1.5, GOMAXPROCS по умолчанию равен количеству доступных ядер ЦП.

Горутина имеет более простой жизненный цикл, чем поток ОС. Это может быть одно из следующих действий:

  • Выполнение — Горутина запланирована на M и выполняет ее инструкции.
  • Runnable — Горутина ожидает перехода в состояние выполнения.
  • Ожидание — Горутина остановлена ​​и ожидает завершения чего-либо, например системного вызова или операции синхронизации (например, получения мьютекса).

Остался последний этап реализации планирования Go: когда горутина создана, но еще не может быть выполнена; например, все остальные M уже выполняют G. Что в этом случае будет делать среда выполнения Go? Ответ в очереди. Среда выполнения Go обрабатывает два типа очередей: одна локальная очередь для каждого P и глобальная очередь, совместно используемая всеми P.

На рис. 1 показана заданная ситуация планирования на четырехъядерной машине с GOMAXPROCS, равным 4. Частями являются логические ядра (Ps), горутины (Gs), потоки ОС (Ms), локальные очереди и глобальная очередь:

Во-первых, мы видим пять M, тогда как для GOMAXPROCS установлено значение 4. Но, как мы уже упоминали, при необходимости среда выполнения Go может создать больше потоков ОС, чем значение GOMAXPROCS.

P0, P1 и P3 в настоящее время заняты выполнением потоков среды выполнения Go. Но P2 в настоящее время простаивает, так как M3 выключен P2, и никакой горутины для выполнения нет. Это не очень хорошая ситуация, потому что шесть готовых к запуску горутин ожидают выполнения, некоторые в глобальной очереди, а некоторые в других локальных очередях. Как среда выполнения Go справится с этой ситуацией? Вот реализация планирования в псевдокоде (см. proc.go):

Каждое шестьдесят первое выполнение планировщик Go проверяет, доступны ли горутины из глобальной очереди. Если нет, он проверит свою локальную очередь. Между тем, если и глобальная, и локальная очереди пусты, планировщик Go может забрать горутины из других локальных очередей. Этот принцип в планировании называется кражей работы, и он позволяет недостаточно загруженному процессору активно искать горутины другого процессора и воровать некоторые из них.

Еще одна важная вещь, о которой следует упомянуть: до Go 1.14 планировщик был кооперативным, что означало, что горутина могла быть контекстно отключена от потока только в определенных случаях блокировки (например, отправка или получение канала, ввод-вывод, ожидание получения). мьютекс). Начиная с Go 1.14, планировщик Go теперь является вытесняющим: когда горутина выполняется в течение определенного периода времени (10 мс), она будет помечена как вытесняемая и может быть отключена в контексте, чтобы быть замененной другой горутиной. Это позволяет заставить длительное задание совместно использовать время процессора.

Теперь, когда мы понимаем основы планирования в Go, давайте рассмотрим конкретный пример: параллельная реализация сортировки слиянием.

Параллельная сортировка слиянием

Во-первых, давайте кратко рассмотрим, как работает алгоритм сортировки слиянием. Затем мы реализуем параллельную версию. Обратите внимание, что цель состоит не в том, чтобы реализовать наиболее эффективную версию, а в том, чтобы поддержать конкретный пример, показывающий, почему параллелизм не всегда быстрее.
Алгоритм сортировки слиянием работает, многократно разбивая список на два подсписка, пока каждый подсписок не будет состоять из один элемент, а затем объединить эти подсписки, чтобы в результате получился отсортированный список (см. рис. 2). Каждая операция разделения разбивает список на два подсписка, тогда как операция слияния объединяет два подсписка в отсортированный список.

Вот последовательная реализация этого алгоритма. Мы не включаем весь код, так как это не главное в этом посте:

Этот алгоритм имеет структуру, которая делает его открытым для параллелизма. Действительно, поскольку каждая операция sequentialMergesort работает с независимым набором данных, которые не нужно полностью копировать (здесь независимое представление базового массива с использованием срезов), мы могли бы распределить эту рабочую нагрузку между ядрами ЦП, раскручивая каждое sequentialMergesort. операция в другой горутине. Напишем первую параллельную реализацию:

В этой версии каждая половина рабочей нагрузки обрабатывается отдельной горутиной. Родительская горутина ожидает обе части, используя sync.WaitGroup. Следовательно, мы вызываем метод ожидания перед операцией слияния.

Теперь у нас есть параллельная версия алгоритма сортировки слиянием. Следовательно, если мы запустим бенчмарк для сравнения этой версии с последовательной, параллельная версия должна быть быстрее, верно? Давайте запустим его на четырехъядерной машине с 10 000 элементов:

Benchmark_sequentialMergesort-4       2278993555 ns/op
Benchmark_parallelMergesortV1-4      17525998709 ns/op

Удивительно, но параллельная версия почти на порядок медленнее. Как мы можем объяснить этот результат? Как возможно, что параллельная версия, которая распределяет рабочую нагрузку между четырьмя ядрами, работает медленнее, чем последовательная версия, работающая на одной машине? Давайте проанализируем проблему.

Если у нас есть срез, скажем, из 1024 элементов, родительская горутина запустит две горутины, каждая из которых отвечает за обработку половины, состоящей из 512 элементов. Каждая из этих горутин запустит две новые горутины, отвечающие за обработку 256 элементов, затем 128 и так далее, пока мы не запустим горутину для вычисления одного элемента.

Если рабочая нагрузка, которую мы хотим распараллелить, слишком мала, то есть мы собираемся вычислять ее слишком быстро, преимущество распределения задания по ядрам теряется: время, необходимое для создания горутины и ее выполнения планировщиком, намного больше. слишком много по сравнению с прямым слиянием небольшого количества элементов в текущей горутине. Хотя горутины легче и быстрее запускаются, чем потоки, мы все же можем столкнуться со случаями, когда рабочая нагрузка слишком мала.

ПРИМЕЧАНИЕ.Мы обсуждаем, как распознать, когда выполнение плохо распараллелено, в статье 100 ошибок Go, ошибка № 98: Неиспользование инструментов диагностики Go.

Итак, что мы можем заключить из этого результата? Означает ли это, что алгоритм сортировки слиянием нельзя распараллелить? Подожди, не так быстро.

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

Если количество элементов в срезе s меньше max, мы вызываем последовательную версию. В противном случае мы продолжаем вызывать нашу параллельную реализацию. Влияет ли такой подход на результат? Да, это так:

Benchmark_sequentialMergesort-4       2278993555 ns/op
Benchmark_parallelMergesortV1-4      17525998709 ns/op
Benchmark_parallelMergesortV2-4       1313010260 ns/op

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

ПРИМЕЧАНИЕ.Почему я установил пороговое значение 2048? Потому что это было оптимальное значение для этой конкретной рабочей нагрузки на моей машине. В общем, такие магические значения следует тщательно определять с помощью эталонных тестов (работающих в среде выполнения, аналогичной производственной). Также довольно интересно отметить, что запуск одного и того же алгоритма на языке программирования, который не реализует концепцию горутин, влияет на значение. Например, выполнение того же примера на Java с использованием потоков означает, что оптимальное значение ближе к 8192. Это показывает, насколько горутины более эффективны, чем потоки.

Заключение

В этом посте мы рассмотрели фундаментальные концепции планирования в Go: различия между потоком и горутиной и то, как среда выполнения Go планирует горутины. Между тем, используя пример параллельной сортировки слиянием, мы показали, что параллелизм не всегда быстрее. Как мы видели, развертывание горутин для обработки минимальных рабочих нагрузок (слияние только небольшого набора элементов) сводит на нет преимущества, которые мы могли бы получить от параллелизма.

Итак, куда мы должны идти отсюда? Мы должны помнить, что параллелизм не всегда быстрее, и его не следует рассматривать как способ решения всех проблем по умолчанию. Во-первых, это усложняет задачу. Кроме того, современные ЦП стали невероятно эффективны при выполнении последовательного и предсказуемого кода. Например, суперскалярный процессор может с высокой эффективностью распараллелить выполнение инструкций на одном ядре.

Означает ли это, что мы не должны использовать параллелизм? Конечно, нет. Однако важно помнить об этих выводах. Если мы не уверены, что параллельная версия будет быстрее, правильный подход может заключаться в том, чтобы начать с простой последовательной версии и строить оттуда с помощью профилирования (ошибка №98, Неиспользование инструментов диагностики Go) и бенчмарков ( ошибка №89, «Пишем неверные бенчмарки», также опубликовано здесь), например. Это может быть единственным способом гарантировать, что параллельная реализация того стоит.

Этот пост взят из моей книги 100 ошибок в Go и как их избежать, которая была выпущена в августе 2022 года (ошибка #56):

Книга «100 ошибок Go и как их избежать»показывает, как заменить распространенные проблемы программирования в Go идиоматичным, выразительным кодом. В нем вы изучите десятки интересных примеров и тематических исследований и научитесь выявлять ошибки, которые могут появиться в ваших собственных приложениях.

Сэкономьте 35 % с кодом au35har.

Между тем, вот репозиторий GitHub, в котором собраны все ошибки в книге: https://github.com/teivah/100-go-mistakes.