Почему GCD увеличивает время выполнения?
Я пытаюсь изучить Grand Central Dispatch (GCD) и использую следующий код для тестирования:
С GCD:
#include <dispatch/dispatch.h>
#include <vector>
#include <cstdlib>
#include <iostream>
int main(int argc, char *argv[])
{
const int N = atoi(argv[1]);
__block std::vector<int> a(N, 0);
dispatch_apply(N,
dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0),
^(size_t i)
{
a[i] = i;
#ifdef DEBUG
if ( i % atoi(argv[2]) == 0)
std::cout << a[i] << std::endl;
#endif
});
return 0;
}
Без GCD:
#include <vector>
#include <cstdlib>
#include <iostream>
int main(int argc, char *argv[])
{
const int N = atoi(argv[1]);
std::vector<int> a(N, 0);
for (int i = 0; i < N; i++)
{
a[i] = i;
#ifdef DEBUG
if ( i % atoi(argv[2]) == 0)
std::cout << a[i] << std::endl;
#endif
}
return 0;
}
Результат теста с GCD:
$ time ./testgcd 100000000 10000000
4.254 secs
Тест без GCD:
$ time ./nogcd 100000000 10000000
1.462 secs
Я думал, что GCD должен сократить время выполнения, но результаты показывают обратное.
Я не уверен, что неправильно использую GCD.
Среда ОС — Mac OS X 10.8 с Xcode 4.5. Компилятор Clang ++ 3.1.
Аппаратное обеспечение — Macbook Pro с процессором i5, имеющим два ядра.
Для сравнения я использую OpenMP (также использующий GCC, поставляемый с Xcode 4.5 на том же ноутбуке):
#include <vector>
#include <cstdlib>
int main(int argc, char *argv[])
{
const int N = atoi(argv[1]);
std::vector <int> a(N, 0);
#pragma omp parallel for
for (int i = 0; i < N; i++)
a[i] = i;
return 0;
}
и w / wo (-fopenmp), у меня есть два исполняемых файла для тестирования,
с -fopenmp флаг во время компиляции:
$ time ./testopenmp 100000000
1.280 secs
без -fopenmp флаг во время компиляции:
$ time ./testnoopenmp 100000000
1.626 secs
С OpenMP время выполнения сокращается.
Решение
GCD не обязательно должен увеличивать время выполнения. Причина, по которой это происходит в вашем случае, заключается в том, что вы делаете это неправильно. Важно, чтобы вы знали, почему ваше приложение медленное в первую очередь. Итак, я пошел и запустил ваш код под многоядерным профилировщиком (Instruments.app), и вот что он показывает:
Как видите, график в основном желтый. Желтый означает, что поток ничего не делает и ожидает выполнения какой-либо задачи. Зеленый означает, что он выполняет задачу. Другими словами, так, как вы написали свой код, приложение тратит 99% своего времени на прохождение задач, и выполнение каждой задачи почти не занимает много времени — слишком много накладных расходов. Так почему это происходит?
Потому что вы запланировали около 100000000 задач для запуска. Выполнение каждой задачи имеет некоторые издержки, которые намного больше, чем назначение целого числа массиву. Основное правило — не планировать задачу, если ее сложность меньше, чем при межпотоковом обмене данными.
Так как вы это исправите? Запланируйте меньше задач, делайте больше в каждой задаче. Например:
int main(int argc, char *argv[])
{
const int N = atoi(argv[1]);
__block std::vector<int> a(N, 0);
dispatch_apply(4,
dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0),
^(size_t iN)
{
size_t s = a.size()/4;
size_t i = (s*iN);
size_t n = i + s;
//printf("Iteration #%lu [%lu, %lu]\n", iN, i, n);
while (i < n) {
a[i] = i++;
}
});
return 0;
}
Теперь профилировщик показывает следующее:
Запустите тест снова и GCD будет немного быстрее:
$ time ./test_nogcd 100000000 10000000
real 0m0.516s
user 0m0.378s
sys 0m0.138s
$ time ./test_gcd 100000000 10000000
real 0m0.507s
user 0m0.556s
sys 0m0.138s
Возможно, выполнение меньшего количества задач сделает это лучше? Попробуйте это. При таком простом рабочем процессе велика вероятность того, что вам будет намного лучше, если использовать однопоточную реализацию SIMD. А может и нет 🙂
Обратите внимание, что вам необходимо проявлять особую осторожность в некоторых ситуациях, например, когда общий размер не может быть разделен на N равных частей и т. Д. Я упустил все проверки ошибок для простоты.
Кроме того, существует множество нюансов, когда речь идет о распараллеливании задач на современном товарном оборудовании. Я бы порекомендовал вам ознакомиться с MESI, ложным разделением, барьерами памяти, кэшем ЦП, не обращающими внимания алгоритмами кэширования и т. Д. И помните — всегда используйте профилировщик!
Надеюсь, поможет. Удачи!
Другие решения
GCD не будет волшебным образом сокращать общее время выполнения, и его использование определенно имеет свою стоимость: подумайте, например, о том, что такие операторы как dispatch_apply_*и все закулисное управление, которое они подразумевают, должен стоит некоторое время. (Сейчас мне кажется, что 2,5 секунды — это слишком много для такого управления, но сейчас я не могу оценить достоверность вашего результата). Конечным результатом является то, что GCD может улучшить вашу производительность, если вы используете его правильно (в правильном сценарии) и если ваше оборудование позволяет это.
Возможно, особенность GCD, которая заставляет вас поверить, что это способность GCD выполнять задачу асинхронным способом в отдельном потоке.
Это само по себе и в обоих случаях не обязательно приводит к сокращению общего времени выполнения, но может помочь улучшить отзывчивость приложения, например, не позволяя пользовательскому интерфейсу зависать.
Кроме того, если у процессора больше ядер или у вас система с несколькими процессорами, а также потоки планируются на разных ядрах / процессорах, тогда GCD может улучшить общее время выполнения, потому что две (на самом деле, до количества ядер) разные задачи будут выполняться параллельно. В таком случае общая продолжительность двух задач будет равна большей продолжительности задачи (+ стоимость управления).
После того, как это прояснили, углубляясь в детали вашего примера, вы также можете заметить следующее:
-
вы планируете N задач в одном вторичном потоке: эти задачи будут выполняться последовательно даже в многоядерной системе;
-
единственный другой выполняющий поток, тот, который выполняет main, не делает ничего длинного, поэтому общая продолжительность вашей программы однозначно определяется продолжительностью задач в точке 1;
-
наконец, если вы примете во внимание характер задачи, вы увидите, что это просто задание, которое вы выполняете N раз. Теперь в случае GCD для каждого такого назначения вы ставите задачу в очередь, а затем выполняете ее во вторичном потоке; в случае не-GCD вы просто выполняете цикл for для выполнения N назначений, что дает вам самое быстрое время из всех. В первом случае за каждое назначение вы также платите за постановку в очередь + планирование задачи.
Возможно, это не самый важный сценарий, в котором вы можете измерить выгоду от GCD, в то время как он может быть хорошим для измерения стоимости GCD с точки зрения производительности (для меня это выглядит как наихудший сценарий).