ソートの並列化

ソートが遅くて困っていたので、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倍以上速くなった。