Используем параллельные алгоритмы C++17 для улучшения производительности

Мы перевели пост из блога Microsoft, в котором разработчик рассказывает, как пользоваться параллельными алгоритмами, поддержка которых появилась в стандартной библиотеке C++17.

Как использовать параллельные алгоритмы

Чтобы использовать библиотеку параллельных алгоритмов, следуйте данным шагам:

1. Найдите вызов алгоритма, который вы хотите оптимизировать с помощью распараллеливания. На эту роль хорошо подходят алгоритмы, которые делают больше чем O(n) работы, например, сортировка, и занимают значительное количество времени при профилировании приложения.
2. Убедитесь, что код, используемый в алгоритме, безопасен для распараллеливания.
3. Выберите политику параллельного исполнения (они будут описаны ниже).
4. Если вы ещё этого не сделали, добавьте строку #include <execution>, чтобы сделать доступными политики параллельного исполнения.
5. Добавьте одну из политик в качестве первого параметра вызова алгоритма для распараллеливания.
6. Протестируйте результат, чтобы убедиться, что новая версия работает лучше. Распараллеливание не всегда работает быстрее, особенно когда используются итераторы непроизвольного доступа, когда набор входных данных мал или когда дополнительное распараллеливание создаёт конфликт внешних ресурсов вроде диска.

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

			// Компилировать с помощью:
//  debug: cl /EHsc /W4 /WX /std:c++latest /Fedebug /MDd .\program.cpp
//  release: cl /EHsc /W4 /WX /std:c++latest /Ferelease /MD /O2 .\program.cpp
#include <stddef.h>
#include <stdio.h>
#include <algorithm>
#include <chrono>
#include <random>
#include <ratio>
#include <vector>
 
using std::chrono::duration;
using std::chrono::duration_cast;
using std::chrono::high_resolution_clock;
using std::milli;
using std::random_device;
using std::sort;
using std::vector;
 
const size_t testSize = 1'000'000;
const int iterationCount = 5;
 
void print_results(const char *const tag, const vector<double>& sorted,
                   high_resolution_clock::time_point startTime,
                   high_resolution_clock::time_point endTime) {
  printf("%s: Lowest: %g Highest: %g Time: %fms", tag, sorted.front(),
         sorted.back(),
         duration_cast<duration<double, milli>>(endTime - startTime).count());
}
 
int main() {
  random_device rd;
 
  // Генерируем случайные числа:
  printf("Testing with %zu doubles...", testSize);
  vector<double> doubles(testSize);
  for (auto& d : doubles) {
    d = static_cast<double>(rd());
  }
 
  // Измеряем время, необходимое на их сортировку:
  for (int i = 0; i < iterationCount; ++i)
  {
    vector<double> sorted(doubles);
    const auto startTime = high_resolution_clock::now();
    sort(sorted.begin(), sorted.end());
    const auto endTime = high_resolution_clock::now();
    print_results("Serial", sorted, startTime, endTime);
  }
}
		

Параллельные алгоритмы зависят от доступного параллелизма оборудования, поэтому убедитесь, что вы проводите тесты на железе, производительность которого вам важна. Вам не нужно много ядер, чтобы показать прогресс, к тому же многие из алгоритмов построены по принципу «разделяй и властвуй», и поэтому не будут идеально ускоряться соответственно количеству потоков; но больше — всё равно лучше. В этом примере тестирование проводилось на системе с Intel 7980XE с 18 ядрами и 36 потоками. В этом тесте отладочная и релизная сборки программы показали следующий результат:

			.\debug.exe
Testing with 1000000 doubles...
Serial: Lowest: 1349 Highest: 4.29497e+09 Time: 310.176500ms
Serial: Lowest: 1349 Highest: 4.29497e+09 Time: 304.714800ms
Serial: Lowest: 1349 Highest: 4.29497e+09 Time: 310.345800ms
Serial: Lowest: 1349 Highest: 4.29497e+09 Time: 303.302200ms
Serial: Lowest: 1349 Highest: 4.29497e+09 Time: 290.694300ms
 
C:\Users\bion\Desktop>.\release.exe
Testing with 1000000 doubles...
Serial: Lowest: 2173 Highest: 4.29497e+09 Time: 74.590400ms
Serial: Lowest: 2173 Highest: 4.29497e+09 Time: 75.703500ms
Serial: Lowest: 2173 Highest: 4.29497e+09 Time: 87.839700ms
Serial: Lowest: 2173 Highest: 4.29497e+09 Time: 73.822300ms
Serial: Lowest: 2173 Highest: 4.29497e+09 Time: 73.757400ms
		

Теперь нам нужно убедиться, что вызов сортировки безопасен для распараллеливания. Алгоритмы безопасны для распараллеливания, если «функции доступа к элементу» — операции итерирования, предикаты и всё остальное, что вы можете попросить алгоритм сделать, — следуют обычному правилу для состояния гонки: «любое количество операций чтения или максимум одна операции записи». Более того, они не должны выбрасывать исключения (или выбрасывать достаточно редко, чтобы завершение программы не имело негативных последствий).

Политики исполнения

Теперь нужно выбрать политику исполнения. На данный момент стандарт включает в себя параллельную политику, обозначаемую как std::execution::par, и параллельную непоследовательную политику, обозначаемую как std::execution::par_unseq. В дополнение к требованиям первой, вторая требует, чтобы функции доступа к элементам допускали гарантии прогресса слабее параллельного выполнения. Это значит, что они не должны устанавливать блокировку или делать ещё что-то, что потребует от потоков конкурентного исполнения. Например, если алгоритм работает на графическом процессоре и пытается установить спинлок, поток, который держит этот спинлок, может помешать выполнению других потоков, и спинлок не будет снят. Больше о требованиях можно прочитать в разделах [algorithms.parallel.defns] и [algorithms.parallel.exec] стандарта C++. Если у вас есть сомнения, используйте параллельную политику. В этом примере мы используем оператор «меньше» для типа double, который не устанавливает никаких блокировок, и тип итератора, предоставленный стандартной библиотекой, поэтому мы можем использовать параллельную непоследовательную политику.

Обратите внимание, Visual C++ реализует параллельные и параллельные непоследовательные политики одинаковым образом, поэтому не стоит ожидать лучшей производительности при использовании par_unseq, хотя могут существовать реализации, которые однажды смогут использовать эту дополнительную свободу.

В пример сортировки чисел мы теперь можем добавить #include <execution>. Так как мы используем параллельную непоследовательную политику, мы добавляем std::execution::par_unseq в вызов алгоритма (при использовании параллельной политики нужно было бы использовать std::execution::par). Теперь for-цикл в main() выглядит так:

			for (int i = 0; i < iterationCount; ++i)
{
  vector<double> sorted(doubles);
  const auto startTime = high_resolution_clock::now();
  // Тот же вызов sort, что и выше, только с par_unseq:
  sort(std::execution::par_unseq, sorted.begin(), sorted.end());
  const auto endTime = high_resolution_clock::now();
  // Обратите внимание, что в выводе это параллельные результаты
  print_results("Parallel", sorted, startTime, endTime);
}
		

Тестируем:

			.\debug.exe
Testing with 1000000 doubles...
Parallel: Lowest: 6642 Highest: 4.29496e+09 Time: 54.815300ms
Parallel: Lowest: 6642 Highest: 4.29496e+09 Time: 49.613700ms
Parallel: Lowest: 6642 Highest: 4.29496e+09 Time: 49.504200ms
Parallel: Lowest: 6642 Highest: 4.29496e+09 Time: 49.194200ms
Parallel: Lowest: 6642 Highest: 4.29496e+09 Time: 49.162200ms
 
.\release.exe
Testing with 1000000 doubles...
Parallel: Lowest: 18889 Highest: 4.29496e+09 Time: 20.971100ms
Parallel: Lowest: 18889 Highest: 4.29496e+09 Time: 17.510700ms
Parallel: Lowest: 18889 Highest: 4.29496e+09 Time: 17.823800ms
Parallel: Lowest: 18889 Highest: 4.29496e+09 Time: 20.230400ms
Parallel: Lowest: 18889 Highest: 4.29496e+09 Time: 19.461900ms
		

Для этих входных данных программа сработала быстрее. Как вы будете тестировать программу зависит от выбранных вами критериев. Распараллеливание добавляет некоторую нагрузку и будет работать медленнее, чем последовательная версия, для малого числа N в зависимости от памяти и эффектов кеша, а также других факторов, специфичных для конкретной нагрузки. Если в этом примере установить значение N равным 1000, параллельная и последовательная версии будут работать примерно с одной скоростью, а если изменить значение на 100, то последовательная версия будет в 10 раз быстрее. Распараллеливание может оказать положительный эффект, но важно понимать, где его применять.

Текущие ограничения MSVC-реализации параллельных алгоритмов

Мы написали параллельную версию reverse(), и она оказалась в 1.6 раза медленнее последовательной версии на тестовом оборудовании даже при больших значениях N. Также мы протестировали другую реализацию, HPX, и получили схожие результаты. Это не значит, что добавление параллельных алгоритмов в STL было ошибкой со стороны комитета по стандартизации C++. Это просто значит, что оборудование, на которое нацелена наша реализация, не заметило улучшений. В результате мы предоставляем сигнатуры для алгоритмов, которые просто переставляют, копируют или размещают элементы в последовательном порядке, но не распараллеливаем их. Если нам покажут пример, в котором параллелизм будет работать быстрее, мы посмотрим, что можно сделать. Затронутые алгоритмы:

• copy()
• copy_n()
• fill()
• fill_n()
• move()
• reverse()
• reverse_copy()
• rotate()
• rotate_copy()
• swap_ranges()

Реализация некоторых алгоритмов будет закончена в будущем релизе. В Visual Studio 2017 15.8 мы распараллелим:

• adjacent_difference()
• adjacent_find()
• all_of()
• any_of()
• count()
• count_if()
• equal()
• exclusive_scan()
• find()
• find_end()
• find_first_of()
• find_if()
• for_each()
• for_each_n()
• inclusive_scan()
• mismatch()
• none_of()
• reduce()
• remove()
• remove_if()
• search()
• search_n()
• sort()
• stable_sort()
• transform()
• transform_exclusive_scan()
• transform_inclusive_scan()
• transform_reduce()

Цели разработки MSVC-реализации параллельных алгоритмов

Хотя стандарт определяет интерфейс библиотеки параллельных алгоритмов, он ничего не говорит о том, как нужно распараллеливать алгоритмы или даже на каком оборудовании это нужно делать. Некоторые реализации C++ могут распараллеливать с помощью графического процессора или другого вычислительного оборудования при наличии такового. В нашей реализации нет смысла распараллеливать copy(), но есть смысл для реализации, которая нацелена на графический процессор или подобный ускоритель. Далее мы перечислим аспекты, которые ценим.

Сочетание с платформенными механизмами блокировки

Ранее Microsoft поставляла фреймворк для распараллеливания, ConcRT, который использовался в некоторых местах стандартной библиотеки. ConcRT позволяет разнородным нагрузкам прозрачно использовать доступное оборудование и позволяет потокам доделывать работу друг друга, что может увеличить общую производительность. В сущности, когда поток с рабочей нагрузкой ConcRT уходит в спящий режим, он приостанавливает выполнение текущей задачи и запускает другие готовые задачи. Такое неблокирующее поведение уменьшает переключение контекста и может обеспечить большую производительность, чем пул потоков Windows, используемый в нашей реализации параллельных алгоритмов. Тем не менее, это также означает, что нагрузка ConcRT не сочетается с примитивами синхронизации операционной системы вроде SRWLOCK, NT-событий, семафоров, оконных процедур и т. д. Мы считаем, что это неприемлемый компромисс для реализации «по умолчанию», используемой в стандартной библиотеке.

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

Производительность в отладочных сборках

Мы заботимся об эффективности отладки. Решения, которым нужен включённый оптимизатор для нормальной работы, не подходят для использования в стандартной библиотеке. Если добавить вызов Concurrency::parallel_sort в предыдущий пример, то мы увидим, что параллельная сортировка ConcRT немного быстрее в релизе, но при этом почти в 100 раз медленней во время отладки:

			for (int i = 0; i < iterationCount; ++i)
{
  vector<double> sorted(doubles);
  const auto startTime = high_resolution_clock::now();
  Concurrency::parallel_sort(sorted.begin(), sorted.end());
  const auto endTime = high_resolution_clock::now();
  print_results("ConcRT", sorted, startTime, endTime);
}
		

			C:\Users\bion\Desktop>.\debug.exe
Testing with 1000000 doubles...
ConcRT: Lowest: 5564 Highest: 4.29497e+09 Time: 23910.081300ms
ConcRT: Lowest: 5564 Highest: 4.29497e+09 Time: 24096.297700ms
ConcRT: Lowest: 5564 Highest: 4.29497e+09 Time: 23868.098500ms
ConcRT: Lowest: 5564 Highest: 4.29497e+09 Time: 24159.756200ms
ConcRT: Lowest: 5564 Highest: 4.29497e+09 Time: 24950.541500ms
 
C:\Users\bion\Desktop>.\release.exe
Testing with 1000000 doubles...
ConcRT: Lowest: 1394 Highest: 4.29496e+09 Time: 19.019000ms
ConcRT: Lowest: 1394 Highest: 4.29496e+09 Time: 16.348000ms
ConcRT: Lowest: 1394 Highest: 4.29496e+09 Time: 15.699400ms
ConcRT: Lowest: 1394 Highest: 4.29496e+09 Time: 15.907100ms
ConcRT: Lowest: 1394 Highest: 4.29496e+09 Time: 15.859500ms
		

Сочетание с другими системными программами и библиотеками параллелизма

Планированием в нашей реализации занимается системный пул потоков Windows. Пул потоков использует информацию, недоступную стандартной библиотеке, например, какие ещё потоки выполняются в системе, каких ресурсов ядра они ожидают и т. д. Он решает, когда создать больше потоков и когда их завершать. Он также используется совместно с другими системными компонентами, включая те, которые не используют C++.

Для получения дополнительной информации о том, какие оптимизации делает пул потоков, посмотрите доклад Педро Тейшеры, а также официальную документацию для функций CreateThreadpoolWork(), SubmitThreadpoolWork(), WaitForThreadpoolWorkCallbacks() и CloseThreadpoolWork().

Прежде всего, параллелизм — это оптимизация

Если в ходе тестов параллельный алгоритм не даёт преимуществ для разумных значений N, то мы его не распараллеливаем. Мы считаем, что в два раза большая скорость для N = 1,000,000 и на три порядка меньшая для N = 100 является неприемлемым компромиссом. Если вам нужен «параллелизм любой ценой», существует множество других реализаций, которые работают с MSVC, включая HPX и Threading Building Blocks.

Аналогично, стандарт C++ позволяет параллельным алгоритмам выделять память и выбрасывать std::bad_alloc, когда они не могут получить к ней доступ. В нашей реализации мы возвращаемся к последовательной версии алгоритма, если нельзя получить дополнительные ресурсы.