Реализованы ли уже параллельные алгоритмы C ++ 17?

Вы можете направить https://en.cppreference.com/w/cpp/compiler_support на проверьте состояние реализации всех C++ функций. В вашем случае просто введите «Standardization of Parallelism TS», и вы обнаружите, что только компиляторы MSVC и Intel C++ поддерживают эту функцию.

Они есть в GCC 9, но TBB необходимо установить отдельно

В Ubuntu 19.10 все компоненты окончательно выровнены:

• GCC 9 по умолчанию , и минимально необходимая версия для TBB
• TBB (Intel Thread Building Blocks) находится на уровне 2019 ~ U8-1, поэтому он соответствует минимальным требованиям 2018 года.

так что вы можете просто сделать:

sudo apt install gcc libtbb-dev
g++ -ggdb3 -O3 -std=c++17 -Wall -Wextra -pedantic -o main.out main.cpp -ltbb
./main.out

и использовать как:

#include <execution>
#include <algorithm>

std::sort(std::execution::par_unseq, input.begin(), input.end());

см. также полный рабочий тест ниже.

GCC 9 и TBB 2018 - первые, которые работают, как указано в примечаниях к выпуску: https://gcc.gnu.org/gcc-9/changes.html

Параллельные алгоритмы и <execution> (требуется Thread Building Blocks 2018 или новее).

Связанные темы:

• Как установить TBB из исходного кода в Linux и заставить его работать
• проблема при связывании библиотеки tbb INTEL

Установка Ubuntu 18.04

Ubuntu 18.04 немного сложнее:

• GCC 9 можно получить из надежного PPA, значит не так уж и плохо
• TBB находится в версии 2017, которая не работает, и мне не удалось найти надежный PPA для этого. Компилировать из исходников легко, но нет цели установки, которая раздражает ...

Вот полностью автоматизированные протестированные команды для Ubuntu 18.04:

# Install GCC 9
sudo add-apt-repository ppa:ubuntu-toolchain-r/test
sudo apt-get update
sudo apt-get install gcc-9 g++-9

# Compile libtbb from source.
sudo apt-get build-dep libtbb-dev
git clone https://github.com/intel/tbb
cd tbb
git checkout 2019_U9
make -j `nproc`
TBB="$(pwd)"
TBB_RELEASE="${TBB}/build/linux_intel64_gcc_cc7.4.0_libc2.27_kernel4.15.0_release"

# Use them to compile our test program.
g++-9 -ggdb3 -O3 -std=c++17 -Wall -Wextra -pedantic -I "${TBB}/include" -L 
"${TBB_RELEASE}" -Wl,-rpath,"${TBB_RELEASE}" -o main.out main.cpp -ltbb
./main.out

Анализ тестовой программы

Я тестировал эту программу, которая сравнивает скорость параллельной и последовательной сортировки.

main.cpp

#include <algorithm>
#include <cassert>
#include <chrono>
#include <execution>
#include <random>
#include <iostream>
#include <vector>

int main(int argc, char **argv) {
    using clk = std::chrono::high_resolution_clock;
    decltype(clk::now()) start, end;
    std::vector<unsigned long long> input_parallel, input_serial;
    unsigned int seed;
    unsigned long long n;

    // CLI arguments;
    std::uniform_int_distribution<uint64_t> zero_ull_max(0);
    if (argc > 1) {
        n = std::strtoll(argv[1], NULL, 0);
    } else {
        n = 10;
    }
    if (argc > 2) {
        seed = std::stoi(argv[2]);
    } else {
        seed = std::random_device()();
    }

    std::mt19937 prng(seed);
    for (unsigned long long i = 0; i < n; ++i) {
        input_parallel.push_back(zero_ull_max(prng));
    }
    input_serial = input_parallel;

    // Sort and time parallel.
    start = clk::now();
    std::sort(std::execution::par_unseq, input_parallel.begin(), input_parallel.end());
    end = clk::now();
    std::cout << "parallel " << std::chrono::duration<float>(end - start).count() << " s" << std::endl;

    // Sort and time serial.
    start = clk::now();
    std::sort(std::execution::seq, input_serial.begin(), input_serial.end());
    end = clk::now();
    std::cout << "serial " << std::chrono::duration<float>(end - start).count() << " s" << std::endl;

    assert(input_parallel == input_serial);
}

На Ubuntu 19.10 ноутбук Lenovo ThinkPad P51 с процессором: процессор Intel Core i7-7820HQ (4 ядра / 8 потоков, база 2,90 ГГц, кэш 8 МБ), ОЗУ: 2x Samsung M471A2K43BB1-CRC (2x 16 ГБ, 2400 Мбит / с) типичный выход для входа со 100 миллионами номеров, которые нужно отсортировать:

./main.out 100000000

был:

parallel 2.00886 s
serial 9.37583 s

так что параллельная версия была примерно в 4,5 раза быстрее! См. Также: Что означают термины CPU связанный и связанный ввод-вывод означает?

Мы можем подтвердить, что процесс порождает потоки с strace:

strace -f -s999 -v ./main.out 100000000 |& grep -E 'clone'

который показывает несколько строк типа:

[pid 25774] clone(strace: Process 25788 attached
[pid 25774] <... clone resumed> child_stack=0x7fd8c57f4fb0, flags=CLONE_VM|CLONE_FS|CLONE_FILES|CLONE_SIGHAND|CLONE_THREAD|CLONE_SYSVSEM|CLONE_SETTLS|CLONE_PARENT_SETTID|CLONE_CHILD_CLEARTID, parent_tidptr=0x7fd8c57f59d0, tls=0x7fd8c57f5700, child_tidptr=0x7fd8c57f59d0) = 25788

Кроме того, если я закомментирую серийную версию и буду работать с:

time ./main.out 100000000

Я получил:

real    0m5.135s
user    0m17.824s
sys     0m0.902s

который еще раз подтверждает, что алгоритм был распараллелен с реального ‹пользователя и дает представление о том, насколько эффективно его можно распараллелить в моей системе (примерно в 3,5 раза для 8 ядер).

Сообщения об ошибках

Google, проиндексируйте это, пожалуйста.

Если у вас не установлен tbb, возникает ошибка:

In file included from /usr/include/c++/9/pstl/parallel_backend.h:14,
                 from /usr/include/c++/9/pstl/algorithm_impl.h:25,
                 from /usr/include/c++/9/pstl/glue_execution_defs.h:52,
                 from /usr/include/c++/9/execution:32,
                 from parallel_sort.cpp:4:
/usr/include/c++/9/pstl/parallel_backend_tbb.h:19:10: fatal error: tbb/blocked_range.h: No such file or directory
   19 | #include <tbb/blocked_range.h>
      |          ^~~~~~~~~~~~~~~~~~~~~
compilation terminated.

Итак, мы видим, что <execution> зависит от неустановленного компонента TBB.

Если TBB слишком старый, например по умолчанию Ubuntu 18.04, он не работает с:

#error Intel(R) Threading Building Blocks 2018 is required; older versions are not supported.

Intel выпустила параллельную библиотеку STL, которая соответствует стандарту C ++ 17:

• https://github.com/intel/parallelstl

Он объединяется с GCC.

Gcc еще не реализует Parallelism TS (см. https://gcc.gnu.org/onlinedocs/libstdc++/manual/status.html#status.iso.2017)

Однако libstdc ++ (с gcc) имеет экспериментальный режим для некоторых эквивалентных параллельных алгоритмов. См. https://gcc.gnu.org/onLineocs/libstdc++/manual/parallel_mode.html

Заставляем его работать:

Любое использование параллельных функций требует дополнительной поддержки компилятора и среды выполнения, в частности поддержки OpenMP. Добавить эту поддержку несложно: просто скомпилируйте приложение с флагом компилятора -fopenmp. Это свяжется с libgomp, библиотекой времени выполнения GNU Offloading and Multi Processing Runtime Library, присутствие которой обязательно.

Пример кода

#include <vector>
#include <parallel/algorithm>

int main()
{
  std::vector<int> v(100);

  // ...

  // Explicitly force a call to parallel sort.
  __gnu_parallel::sort(v.begin(), v.end());
  return 0;
}

Gcc теперь поддерживает заголовок выполнения, но не стандартную сборку clang из https://apt.llvm.org