Приобщаясь к параллелизму написал (в рамках С++11) один пользующейся популярностью (во всяком случае у меня) алгоритм transform - аналог std::transform, но выполняющийся параллельно.
Возможно это велосипед.. Знаю про существование Intel TBB, VC++ PPL, OpenMP но.. просто было интересно)

C++ (Qt)
#ifndef PARALLEL_H
#define PARALLEL_H
 
#include <algorithm>
#include <thread>
#include <memory>
#include <iterator>
#include <vector>
 
struct parallel
{
    template<class InputIt, class OutputIt, class UnaryOperation>
    static OutputIt transform(InputIt ifirst, InputIt ilast, OutputIt ofirst, UnaryOperation unary_op) {
 
        const size_t size = std::distance(ifirst, ilast);
        const size_t nthreads = std::min(size, static_cast<size_t>(std::thread::hardware_concurrency()));
        if (nthreads < 2)
            return std::transform(ifirst, ilast, ofirst, unary_op);
 
        const size_t group = size/nthreads;
 
        std::vector<std::shared_ptr<std::thread>> threads(nthreads-1);
        auto it = ifirst;
 
        for (auto & thread_ptr : threads) {
            std::advance(it, group);
            thread_ptr = std::make_shared<std::thread>([=]{ std::transform(ifirst, it, ofirst, unary_op); });
            ifirst = it;
            std::advance(ofirst, group);
        }
 
        for (auto & t : threads) { t->join(); }
 
        return std::transform(ifirst, ilast, ofirst, unary_op);
    }
 
    template<class InputIt1, class InputIt2, class OutputIt, class BinaryOperation>
    static OutputIt transform(InputIt1 ifirst1, InputIt1 ilast1, InputIt2 ifirst2, OutputIt ofirst, BinaryOperation binary_op) {
 
        const size_t size = std::distance(ifirst1, ilast1);
        const size_t nthreads = std::min(size, static_cast<size_t>(std::thread::hardware_concurrency()));
        if (nthreads < 2)
            return std::transform(ifirst1, ilast1, ifirst2, ofirst, binary_op);
 
        const size_t group = size/nthreads;
 
        std::vector<std::shared_ptr<std::thread>> threads(nthreads-1);
        auto it = ifirst1;
 
        for (auto & thread_ptr : threads) {
            std::advance(it, group);
            thread_ptr = std::make_shared<std::thread>([=]{ std::transform(ifirst1, it, ifirst2, ofirst, binary_op); });
            ifirst1 = it;
            std::advance(ifirst2, group);
            std::advance(ofirst, group);
        }
 
        for (auto & t : threads) { t->join(); }
 
        return std::transform(ifirst1, ilast1, ifirst2, ofirst, binary_op);
    }
};
 
#endif // PARALLEL_H
 

тест:

C++ (Qt)
#include <iostream>
#include <vector>
#include <cmath>
#include <chrono>
 
#include "parallel.h"
 
double func(const double & x) {
    return sin(x)*cos(x*x)*exp(-x*x*0.5)/(1.0 + x*x);
}
 
int main()
{
    const size_t N = 10000000;
 
    std::vector<double> v1(N, 2.0);
    std::vector<double> v2(v1);
 
    auto start = std::chrono::high_resolution_clock::now();
    parallel::transform(v1.begin(), v1.end(), v2.begin(), func);
    auto stop = std::chrono::high_resolution_clock::now();
 
    auto par_duration = std::chrono::duration_cast<std::chrono::milliseconds>(stop-start).count();
 
    start = std::chrono::high_resolution_clock::now();
    std::transform(v1.begin(), v1.end(), v2.begin(), func);
    stop = std::chrono::high_resolution_clock::now();
 
    auto seq_duration = std::chrono::duration_cast<std::chrono::milliseconds>(stop-start).count();
 
    std::cout << "par: " << par_duration << std::endl;
    std::cout << "seq: " << seq_duration << std::endl;
 
    return 0;
}
 
 

Критика приветствуется)


 

Не понял почему он не определен если каждая нитка пишет в свой участок?

- если size не кратен nthreads, то последние эт-ты не обрабатываются
- запуск нитки - удовольствие дорогое, поэтому заводят все нитки сразу, а в нужный момент "спускают с цепи"
- пока считается - все заморожено (запускающий стоит на join)

Давайте смотреть
Пусть size = 7, nthreads = 4. Запускаете 3 нитки (почему если есть 4 ядра?). group = 1, цикл выполняется 3 раза, обработано 3 (из 7), или как?

Не "запускают" а "спускают", т.е. снимают с мутекслв. Причем мутексы комбинированные честный/нечестный. Напр после выполнения расчетов нитки усыпляются не сразу, а какое-то время работают вхолостую (а вдруг сейчас еще расчет). Длительность этой прокрутки значительна, по умолчанию 0.3 секунды(!) в OpenMP. А запуск - это тонна работы для ОС

Для любых. Никто не против "lite" веши, пусть есть многочисленные аналоги. Но выходит "ни богу свечка ни черту кочерга". Для маленьких рачсетов - запуск сожрет все, а если расчет идет секунды - ни отменить, ни обновить UI.

[4 8]. А чего же всем по одной а главной аж 4 задачи? Это легко исправить

C++ (Qt)
size_t need = 0, fact = 0;
for (size_t i = 0; i < nthread - 1; ++i) {
 need = (i + 1) * num_Tasks / nthread;  // 1, 3, 5  
 num = need - fact;   // 1, 2, 2
 fact = need;
 std::advance(it, num);
 ...  
}
 

Атомарная переменная (отслеживающая число выполненных задач) здесь была бы к месту. Также лучше добавить флажок m_master (true для запускающей). Тогда "деревья не кажутся столь уж большими", напр

C++ (Qt)
double func(const double & x) 
{
    double result = sin(x)*cos(x*x)*exp(-x*x*0.5)/(1.0 + x*x);
    ++atomic_count;
    if (m_master)
      if (!UpdateUI(atomic_count))
        SetAbortFlag();
}

Нагрузку (result =) лучше вынести "хвунктором" Тут правда возникает мелкая проблема - главная закончила свои дела и ушла на join - заморозка. Ну это тоже решаемо

Господа, вы вообще знаете чем отличается OutputIterator от ForwardIterator?

Я подскажу, попробуйте код, в котором результат пишется в изначально пустой вектор с помощью std::back_inserter.

Понятно) Да, согласен - надо запрещать такие ситуации) Исправлю)
Спасибо)

Подумаю..

b-s-a имеет в виду, что вот такая ситуация:

C++ (Qt)
std::vector<int> v1(N);
std::vector<int> v2; // Пустой!
parallel::transform(v1.begin(), v1.end(), std::back_inserter(v2), func);
 

может привести к непредсказуемым последствиям)

Igros, а если тебе надо тупо вывести в поток через std::ostream_iterator? Как ты это сделаешь? Через дополнительный массив?

Исправил. Поставил статик асерт с проверкой на принадлежность к forward iterator type:

C++ (Qt)
typedef typename std::iterator_traits<OutputIt>::iterator_category iterator_category;
static_assert(std::is_base_of<std::forward_iterator_tag, iterator_category>::value,
                    "iterator must meet all the requirements for forward iterator");
 

Согласен, что вариант с lround - неправильный. Вот только стандартная библиотека здесь ни при чём..

Всё равно можно сделать это проще:
Полное число элементов всегда можно представить в виде:
size = m * (size/nthreads + 1) + (nthreads - m) * (size/nthreads)

m - это число нитей которые принимают интервал длиной size/nthreads + 1
(nthreads - m) - число нитей принимающих интервал длиной size/nthreads

Далее логика такая: сначала раздаём m потокам длинные интервалы, а всем оставшимся достаются нормальные size/nthreads интервалы.

Выглядит сейчас это так:

C++ (Qt)
...
        const size_t normal_group = size/nthreads;
        const size_t m = size - normal_group * nthreads;
        size_t i = 0;
        for (auto & thread_ptr : threads) {
            size_t group = (++i <= m) ? normal_group + 1 : normal_group;
            std::advance(it, group);
            ...
        }