2005年10月 1日

C の qsort と STL の sort の速度比較

一般に C の qsort より STL の sort の方が高速と言われています。 qsort が要素の比較のたびに関数を呼び出す必要があるのに対し、 STL の sort は比較関数をインライン化できるのが主な理由です。

…ということを、知人に話したところ、実際に比べたことあるのか、と突っ込みを受けたので、実験してみました。

 

1600万要素の int の配列をソートする実験を行ったところ、関数オブジェクトを用いた STL の sort は qsort より 3.6～3.8 倍ほど高速という結果が出ました。STL の sort には関数ポインタまたは関数オブジェクトを比較関数として渡せますが、関数ポインタ渡しの方はインライン化が効いていないようです。

ソート方法 g++ 3.3.5icc 9.0
qsort 9.22秒 8.82秒
STL sort (関数渡し) 5.62秒 5.09秒
STL sort (関数オブジェクト渡し) 2.56秒 2.31秒

STL は知れば知るほどよくできていると感心します。Effective STL の46項には今回と同様の実験が取り上げられています。 Effective STL には他にも、イテレータの無効化やコンテナ操作の性能など、 STL を使う上で注意すべき点が詳しく解説されています。

実験に使ったプログラムは以下の通りです。 $((2**24)) はコマンドラインで 2の24乗を計算する表記です。bash や zsh で使えます。

実行結果

% g++ -O2 -o sort sort.cpp
% ./sort $((2**24))
qsort: 9.22
stl-sort-func: 5.62
stl-sort-functor: 2.56

% icc -O2 -o icc-sort sort.cpp
% ./icc-sort $((2**24))
qsort: 8.82
stl-sort-func: 5.09
stl-sort-functor: 2.31

コード

#include <assert.h>
#include <stdlib.h>
#include <time.h>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

// a と b がともに正の整数と分かっているので引き算で OK
int qsort_cmp(const void* a, const void* b) {
    return *(int *)b - *(int *)a;
}

int stl_sort_func_cmp(const int& a, const int& b) {
    return b > a;
}

// functional の greater<int> を通常は使う
struct stl_sort_functor_cmp {
    bool operator()(const int& a, const int&b) const { return b > a; }
};

void do_qsort(vector<int>& v) {
    qsort(&v[0], v.size(), sizeof(&v[0]), qsort_cmp);
}

void do_stl_sort_func(vector<int>& v) {
    sort(v.begin(), v.end(), stl_sort_func_cmp);
}

void do_stl_sort_functor(vector<int>& v) {
    sort(v.begin(), v.end(), stl_sort_functor_cmp());
}

typedef void (*SortFunc)(vector<int>&);
void benchmark(const char *name, SortFunc func, const int size) {
    vector<int> v(size);
    for (vector<int>::iterator i = v.begin(); i != v.end(); ++i)
        *i = rand();
    double start_time = clock();
    func(v);
    double elapsed = clock() - start_time;
    printf("%s: %.2f\n", name, elapsed / CLOCKS_PER_SEC);
}

int main(int argc, char **argv) {
    assert(argc == 2);
    const int size = atoi(argv[1]);
    benchmark("qsort", do_qsort, size);
    benchmark("stl-sort-func", do_stl_sort_func, size);
    benchmark("stl-sort-functor", do_stl_sort_functor, size);
    return 0;
}