Как известно в С++17 добавили политику выполнения алгоритмов.
Написано, однако в книжке Уильямса, что это не требование, а разрешение.

И возникает естественный вопрос: а оно вообще на многоядерном процессоре параллельно работает ?
Как-то у меня не получается ускорить стандартный последовательный алгоритм — время получается практически то же самое.

И еще вопрос: вот хотелось бы заполнить вектор из 500 000 000 элементов случайными числами параллельно.

generate(std::execution::par, v.begin(), v.end(), gen);

Не возникнет ли здесь UB из-за ГСЧ ?
Например, если

 mt19937_64 gen(rd());

ведь внутренность ГСЧ явно не рассчитана на параллельное получение нескольких случайных чисел...

Что думаете ?

Здравствуйте, LaptevVV, Вы писали:

LVV>И возникает естественный вопрос: а оно вообще на многоядерном процессоре параллельно работает ?
LVV>Как-то у меня не получается ускорить стандартный последовательный алгоритм — время получается практически то же самое.

на msvc из коробки должно работать, на gcc/clang надо tbb подключать (-ltbb). Ну и проверять, что компилятор вообще это поддерживает https://en.cppreference.com/w/cpp/compiler_support/17.html#C.2B.2B17_library_features Хотя уже почти 10 лет прошло, пора бы и поддерживать.

LVV>И еще вопрос: вот хотелось бы заполнить вектор из 500 000 000 элементов случайными числами параллельно.
LVV>

generate(std::execution::par, v.begin(), v.end(), gen);

LVV>Не возникнет ли здесь UB из-за ГСЧ ?
LVV>Например, если
LVV>

 mt19937_64 gen(rd());

LVV>ведь внутренность ГСЧ явно не рассчитана на параллельное получение нескольких случайных чисел...

например обернуть в лямбду

auto gen = [] {
    static mt19937_64 rng(rd());
    static std::mutex m;
    std::lock_guard<std::mutex> lock(m);
    return rng();
};

LVV>>И возникает естественный вопрос: а оно вообще на многоядерном процессоре параллельно работает ?
LVV>>Как-то у меня не получается ускорить стандартный последовательный алгоритм — время получается практически то же самое.
SP>на msvc из коробки должно работать, на gcc/clang надо tbb подключать (-ltbb). Ну и проверять, что компилятор вообще это поддерживает https://en.cppreference.com/w/cpp/compiler_support/17.html#C.2B.2B17_library_features Хотя уже почти 10 лет прошло, пора бы и поддерживать.
Это с какого бодуна подключать tbb ?
Посторонняя библиотека, к стандартной отношения не имеет...
Вот жеж блин!
Впрочем, в minGW все равно не работает...


LVV>>И еще вопрос: вот хотелось бы заполнить вектор из 500 000 000 элементов случайными числами параллельно.
LVV>>

generate(std::execution::par, v.begin(), v.end(), gen);

LVV>>Не возникнет ли здесь UB из-за ГСЧ ?
LVV>>Например, если
LVV>>

 mt19937_64 gen(rd());

LVV>>ведь внутренность ГСЧ явно не рассчитана на параллельное получение нескольких случайных чисел...

SP>например обернуть в лямбду
SP>

SP>auto gen = [] {
SP>    static mt19937_64 rng(rd());
SP>    static std::mutex m;
SP>    std::lock_guard<std::mutex> lock(m);
SP>    return rng();
SP>};
SP>

Спасибо.
С мутексом — те же последовательные яйца, только вид сбоку...

Здравствуйте, LaptevVV, Вы писали:

LVV>С мутексом — те же последовательные яйца, только вид сбоку...

Тогда thread_local:

auto gen =  []() {
    static thread_local mt19937_64 rng(rd());
    return rng();
};

Здравствуйте, LaptevVV, Вы писали:

LVV>И еще вопрос: вот хотелось бы заполнить вектор из 500 000 000 элементов случайными числами параллельно.
LVV>

generate(std::execution::par, v.begin(), v.end(), gen);

LVV>Не возникнет ли здесь UB из-за ГСЧ ?
LVV>Например, если
LVV>

 mt19937_64 gen(rd());

LVV>ведь внутренность ГСЧ явно не рассчитана на параллельное получение нескольких случайных чисел...

ГСЧ может и не сломается (надо уточнить по спецификакции), но он, наверное, прикроет своё состояние мьютексом. И из-за этого будет работать последовательно, со скольких бы ядер ты его не позвал.

Поэтому тебе этих ГСЧ надо по штуке на поток, чтобы они параллельно работали, а не по-очереди.

И да. Понятия не имею, что там делают библиотечные параллельные алкогоритмы. Но я бы этот вектор из 500 000 000 элементов поделил бы вдоль на последовательные куски примерно одинакового размера, и к каждому куску поставил бы свой поток. А потоков взял бы для начала по штуке на ядро, а потом поиграл бы количеством потоков, причём и в сторону уменьшения тоже.

Тогда каждое ядро будет в память писать, в среднем, струёй. А это раз в 10 быстрее, чем произвольный доступ к памяти.

Здравствуйте, Pzz, Вы писали:

Pzz>И да. Понятия не имею, что там делают библиотечные параллельные алкогоритмы. Но я бы этот вектор из 500 000 000 элементов поделил бы вдоль на последовательные куски примерно одинакового размера, и к каждому куску поставил бы свой поток. А потоков взял бы для начала по штуке на ядро, а потом поиграл бы количеством потоков, причём и в сторону уменьшения тоже.

Именно так и работает OpenMP

В лабораторных условиях это всё замечательно параллелится.
А в боевом проекте OpenMP запускает грядку потоков, а внутри потока алгоритм запускает ещё потоки и ещё... ну и понеслась — в итоге запущены 100500 потоков и большинство стоит в системном шедулере
Тут надо бы начинать дирижировать потоками — заводить пулы потоков, задачи, зависимости между задачами (граф строить).
Какой-нить tbb будет полезнее.

Здравствуйте, sergii.p, Вы писали:


SP>например обернуть в лямбду
SP>

SP>auto gen = [] {
SP>    static mt19937_64 rng(rd());
SP>    static std::mutex m;
SP>    std::lock_guard<std::mutex> lock(m);
SP>    return rng();
SP>};
SP>

Мьютекс разве не съест все плюсы многопоточности, да ещё и прихватит в десятеро лишнего?

Имхо, статическую тред локал переменную надо использовать, без мьютекса, не?

Здравствуйте, Marty, Вы писали:

M>Мьютекс разве не съест все плюсы многопоточности, да ещё и прихватит в десятеро лишнего?

та да. Глупость предложил.

Здравствуйте, Stanislav V. Zudin, Вы писали:

SVZ>Тут надо бы начинать дирижировать потоками — заводить пулы потоков, задачи, зависимости между задачами (граф строить).
SVZ>Какой-нить tbb будет полезнее.

Я предполагаю, что хорошо сделанная генерация случайных чисел работает быстро. Быстрее памяти. Во всяком случае, если мы не стремимся к криптографической стойкости.

Поэтому тут имеет смысл оптимизировать скорость записи в память. А память, хоть и называется RAM, но гораздо быстрее работает при последовательном доступе (и упирается в количество каналов памяти, а их может быть сильно меньше, чем ядер; для настольной системы количество каналов памяти, скорее всего, находится в диапазоне 1-4, в зависимости от крутизны памяти и прочего чипсета).

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

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

Pzz>Поэтому тебе этих ГСЧ надо по штуке на поток, чтобы они параллельно работали, а не по-очереди.
Pzz>И да. Понятия не имею, что там делают библиотечные параллельные алкогоритмы. Но я бы этот вектор из 500 000 000 элементов поделил бы вдоль на последовательные куски примерно одинакового размера, и к каждому куску поставил бы свой поток. А потоков взял бы для начала по штуке на ядро, а потом поиграл бы количеством потоков, причём и в сторону уменьшения тоже.
Так это ручками писать нужно.
А в книжке Уильямся, на которую ссылается Джосатис в своей книжке по STL, пря написано, что используйте политику выполнения и будет вам счастье.
Но пока счастья нет.
Тут выяснилось, что надо -ltbb писать для gcc.
Но у меня пока minGW, поэтому до счастья я еще не добрался.
А как ручками писать параллельные — эт я знаю очень давно...
Но хотелось бы студентам лабы не только ручные давать.
Там еще и openmp есть.
И POSIX-треды. И библиотека taskflow
Pzz>Тогда каждое ядро будет в память писать, в среднем, струёй. А это раз в 10 быстрее, чем произвольный доступ к памяти.
Да, делал так. Еще на 32-битной машине матрицы размером 20000 на 20000

Здравствуйте, Pzz, Вы писали:

Pzz>И да. Понятия не имею, что там делают библиотечные параллельные алкогоритмы. Но я бы этот вектор из 500 000 000 элементов поделил бы вдоль на последовательные куски примерно одинакового размера, и к каждому куску поставил бы свой поток. А потоков взял бы для начала по штуке на ядро, а потом поиграл бы количеством потоков, причём и в сторону уменьшения тоже.

Мне одному кажется, что для таких задач в С++ давным-давно написано что-то вроде дотнетного Parallel.For? С разделением на куски и проч.

Здравствуйте, Слава, Вы писали:

С>Здравствуйте, Pzz, Вы писали:

Pzz>>И да. Понятия не имею, что там делают библиотечные параллельные алкогоритмы. Но я бы этот вектор из 500 000 000 элементов поделил бы вдоль на последовательные куски примерно одинакового размера, и к каждому куску поставил бы свой поток. А потоков взял бы для начала по штуке на ядро, а потом поиграл бы количеством потоков, причём и в сторону уменьшения тоже.

С>Мне одному кажется, что для таких задач в С++ давным-давно написано что-то вроде дотнетного Parallel.For? С разделением на куски и проч.

Да есть, и их много написано.
В конкуренции с OpenMP и TBB, ниши для параллельных алгоритмов STL я не вижу. И неудобнее, и "ручек настройки" меньше.

Здравствуйте, LaptevVV, Вы писали:

LVV>Что думаете ?

Параллельные алгоритмы, по крайней мере, в gcc и clang реализованы с помощью tbb/openmp. Если соответствующие либы не подключены, то будет использоваться последовательный алгоритм.

LVV>>Что думаете ?
__>Параллельные алгоритмы, по крайней мере, в gcc и clang реализованы с помощью tbb/openmp. Если соответствующие либы не подключены, то будет использоваться последовательный алгоритм.
То есть надо еще tbb скачать и установить ?
От жеж засада!
А я думал — это независмая библиотека.
Даже книжка есть отдельная...
Ок. Придется пробовать так.

Здравствуйте, LaptevVV, Вы писали:

LVV>А я думал — это независмая библиотека.

Она и есть независимая. Просто ее используют в качестве бэка. Вот так у clang:

#if defined(_PSTL_PAR_BACKEND_TBB)
using __par_backend_tag = __tbb_backend_tag;
#elif defined(_PSTL_PAR_BACKEND_OPENMP)
using __par_backend_tag = __openmp_backend_tag;
#elif defined(_PSTL_PAR_BACKEND_SERIAL)
using __par_backend_tag = __serial_backend_tag;
#else
#    error "A parallel backend must be specified";
#endif

У gcc тоже нечто подобное.