ソートの並列化
ソートが遅くて困っていたので、OpenMPを使ったBitonic Sortを書いたところ、std::sortよりも遅くてショックを受け、インターネットでいろいろ調べていたら、gccだとコンパイラのオプションだけで並列化できることを知りました。
Chapter 18. Parallel Mode
g++のオプションに
-D_GLIBCXX_PARALLEL -fopenmp
をつけると、_GLIBCXX_PARALLELが定義されてstd::sortが__gnu_parallel::sortになり、OpenMPも有効になって並列化されます。コレで十分でした。
試す。
#include <algorithm> #include <vector> #include <iostream> #include <time.h> #include <sys/time.h> #include <assert.h> static const int N = 1 << 25; unsigned long tick(void) { unsigned long t; struct timeval tv; gettimeofday(&tv, NULL); t = tv.tv_sec * 1000; t += tv.tv_usec / 1000; return t; } int main(void) { unsigned long t; std::vector<int> data; for (int i = 0; i < N; ++i) { data.push_back(std::rand()); } t = tick(); std::sort(data.begin(), data.end()); std::cout << tick() - t << "msec" << std::endl; for (std::vector<int>::iterator i = data.begin(); i != data.end(); ++i) { if (i != data.end() -1 && *i > *(i + 1)) { assert(0); } } return 0; }
Intel Core i7 930 @ 2.80GHz (4コア、HTで8コア)で試した。
% g++ sort.cpp -o sort -O2 % ./sort 3368msec % g++ sort.cpp -o sort -O2 -D_GLIBCXX_PARALLEL -fopenmp % ./sort 608msec
5倍以上速くなった。