Почему компиляторы не любят параллельный код?

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

За последнее время мне довелось наблюдать несколько таких попыток, в которых параллельный код был написан при помощи библиотеки Threading Building Blocks (TBB). К удивлению экспериментаторов, их простые параллельные программы порой не только не показывают ускорения по сравнению с обычной, последовательной версией, но даже и проигрывают в скорости! И далеко не всегда автор может (или хочет) разобраться, что к чему.

Разбираться приходилось мне, как одному из разработчиков TBB. А поскольку мне уже не раз предлагали вести сетевой журнал-блог на Intel Software Network, я в конце концов решил попытаться, и начать с анализа таких вот примеров. Они, с одной стороны, просты и понятны: не каждый готов начать параллельные эксперименты со сколь-нибудь сложной программы, а написать цикл, суммирующий элементы вектора – дело недолгое. С другой стороны, они весьма познавательны, причём порой именно в силу простоты.

Начну как раз с суммы элементов вектора. Вопрос о том, почему столь простая программа медленнее в параллельной TBB версии, чем в не-параллельной, возник на форуме TBB (см. тему “performance of parallel_for”). Я приведу здесь лишь часть кода:


#define REAL double 
#define MAX 10000000
class SumFoo {
REAL *a;
REAL sum;
...
void operator()(const blocked_range<size_t>& r) {
REAL *arr = a;
for(size_t i=r.begin(); i!=r.end(); i++) sum+=arr[i];
}
};
void ParallelSumFoo(REAL a[], size_t n, size_t gs) {
SumFoo sf(a,n);
parallel_reduce(blocked_range<size_t>(0,n,gs), sf);
...
}
class SerialApplyFoo {
REAL *a;
size_t len;
double sum;
public :
SerialApplyFoo(REAL *array, size_t length) : a(array), len(length){
sum = 0.0;
for(size_t i=0; i<len; i++)
sum += a[i];
}

};
int main() {
task_scheduler_init init;
REAL *array = new REAL[MAX];
...
SerialApplyFoo sf(array, MAX);
ParallelSumFoo(array, MAX, GRAINSIZE);
...
}


На двухъядерном процессоре Intel® Core® 2 Duo, вместо ожидаемого двукратного ускорения, параллельный код работал почти вдвое медленнее, чем последовательный; на моём ноутбуке, к примеру, 0.08 сек против 0.044. В чём дело?

Прежде всего, давайте посмотрим, а что произойдёт, если параллельный код запустить последовательно, в одном потоке. С TBB это можно сделать двумя способами: либо явно указав количество потоков (в нашем случае, один) конструктору объекта инициализации библиотеки task_scheduler_init, либо установив параллельному алгоритму так называемый «размер зерна» (grain size) равным количеству итераций цикла. Я воспользуюсь первым способом:

    task_scheduler_init init(1);

 


Результат может показаться неожиданным: 0.21 сек, почти впятеро медленнее, чем исходный последовательный код! Такое замедление явно не из-за использования TBB. Неудивительно, что и на двух ядрах нет выигрыша.

Всё дело в оптимизации, проводимой компилятором. Цикл суммирования в последовательной версии очень прост для оптимизации; компилятор знает о нём всё, начиная от константной длины (передача через аргумент для компилятора не помеха), заканчивая тем, что результат sum должен быть виден только по выходу из конструктора. Поэтому он может сгенерировать очень эффективный машинный код, к примеру, вот такой (я использовал Visual Studio* 2005):


            fldz 
    lea      eax, DWORD PTR [edi+010h]
           mov      ecx, 0x2625A0h
main+0x105: fadd     QWORD PTR [eax-16]
add      eax, 0x20h
sub      ecx, 0x1h
fadd     QWORD PTR [eax-40]
fadd     QWORD PTR [eax-32]
fadd     QWORD PTR [eax-24]
jnz      main+0x105


0x2625A0 – это 2500000, четверть длины массива. Компилятор развернул четыре итерации цикла в одну, снизив расходы на обслуживание цикла. Промежуточные результаты вычислений накапливаются в регистре процессора, и только конечный результат будет записан в память. На каждую итерацию исходного цикла ровно одна операция чтения данных из памяти.

В случае использования TBB для компилятора всё не так просто. Начало и конец цикла определяются полями объекта, переданного по ссылке, длина цикла во время компиляции неизвестна, результат накапливается в поле данных “живого” объекта. Компилятор вынужденно более консервативен, и результат не замедлил сказаться:


execute+0x57: fld      QWORD PTR [edi] 
add      ecx, 0x1h
fadd     QWORD PTR [edx+08h]
add      edi, 0x8h
fstp     QWORD PTR [edx+08h]
cmp      ecx, DWORD PTR [esi+08h]
jnz      execute+0x57


Здесь одна итерация цикла обрабатывает один элемент, но при этом задействует 3 операции чтения (!) и одну – записи. Помимо элемента данных, каждый раз подгружаются из памяти значение конца цикла для сравнения и промежуточная сумма, которая затем сохраняется и на следующей итерации подгружается снова.

Изложив всё это в форуме, я добавил, что тест «отдаёт предпочтение» последовательному коду, и этим, боюсь, направил автора не в ту сторону. В попытке улучшить тест, автор ввёл чтение размера массива с клавиатуры и заменил в не-параллельном коде объект на функцию:


REAL SerialSum(REAL *a_, unsigned long int start, unsigned long int end) { 
REAL sum = 0.0;
for(unsigned long int i=start; i<end; i++)
sum += a_[i];
return sum;
}


Первое изменение делает тест более реалистичным и несколько усложняет развёртывание цикла; второе никак вообще не влияет, потому что в новой функции промежуточная сумма накапливается в локальной переменной, которая точно так же может храниться в регистре процессора. А чтобы решить проблему, надо в параллельный код внести изменения, которые помогут компилятору применить оптимизацию, а именно – использовать в operator() локальные переменные:


    void operator()(blocked_range<size_t> &r) { 
REAL local_sum = 0;
const size_t end = r.end();
for(size_t i=r.begin(); i!=end; i++)
local_sum+=a[i];
sum += local_sum;
}


И вот какой получен машинный код:


              fldz 
execute+0x58: fadd qword ptr [edx]
add edx,8
sub ecx,1
jne execute+58h
fadd qword ptr [edi+8]
fstp qword ptr [edi+8]


Последние две инструкции – добавление локального результата к полю sum. Как и в последовательном коде, мы получили одно обращение к памяти на итерацию, и это сразу сказалось на скорости: теперь параллельный код выполняется 0.033 сек на двухъядерном процессоре. Ускорение достигнуто, но с коэффициентом 1.33, а не 2. Почему? В этом попробуем разобраться в следующий раз.

Вывод: при разработке тестов на производительность, да и просто программ, необходимо учитывать, что использование классов и функций TBB усложняет компилятору работу по оптимизации, что особенно негативно сказывается на простых алгоритмах. Грамотное использование локальных переменных способствует лучшей оптимизации и быстродействию параллельного кода.

For more complete information about compiler optimizations, see our Optimization Notice.