В продолжение выпуска 1.

Так вот наблюдательный опытный разработчик конечно же догадался что причиной замедления параллельной версии стала строка #pragma omp critical. Не поставить её было нельзя, т.к. запись происходит в общую, для разных потоков, память. Будет очень показательно взглянуть на картинку, которую нам показывает Intel Thread Profiler в случае цикла с critical:

Верхняя гистограмма показывает что бОльшую часть времени наша функция задействовала всего 2 ядра на машине. По нижней части картинки видно что каждый поток работает лишь небольшую часть времени, потом натыкается на critical секцию и останавливается, передавая управление другому потоку (жёлтые линии). И такая постоянная передача управления стоит совсем не дёшево (от того и замедление в 50 раз).
Но стандарт OpenMP позволяет в данном случае использовать более «мягкую» директиву #pragma omp atomic, но при этом никто не гарантирует что компилятор не заменит её на тот же critical. Давайте проверим компилятор от Майкрософт. Проведём эксперимент с немного изменённой функций:

компилируем, запускаем и получаем ~2.6 секунд (в некоторых запусках бывает заметно больше). Much better! Ускорение в 1.7 раза (на 8 ядрах) относительно однопотоковой версии. И давайте взглянем на картину, которую нам даёт тот же Intel Thread Profiler:

Видим, что теперь функция использует почти всегда все 8 ядер системы, хотя балансировка циклов оставляет желать лучшего, и отдельные потоки заканчивают работу намного раньше других, что приводит к неполной загрузке системы. Жёлтые линии на данной картинке — это запуски цикла, который у меня в тесте запускается 100 раз подряд для получения более точного результата измерения (на картинке представлен только небольшой кусок процесса выполнения программы).

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