[c++] 文字列のソーティング

qsort と STL の sort では STL の方が速いよ、という事を以下の記事で読んで知ってました。たしかに整数の配列（正確には vector か）に対しては STL が速いのですが、文字列のソーティングに関しては事情が異なるようです。

C の qsort と STL の sort の速度比較 - bkブログ

最近になって文字列のソーティングをする必要に迫られ、最初は考えずにえいやっと std::sort を使っていたのですが、気になってベンチマークをとって見ると qsort の方が100倍速いという結果になりました。ついでに multikey-quicksort と比べてみると、qsort と同じか少し速いようです*1。

ソート方法	g++4.3.1
qsort	1.10秒
stl-sort-func	115.91秒
stl-sort-functor	115.80秒
mulikey-quicksort	0.80秒

ベンチマークには 1MB のテキストファイルを使いました。具体的には、手元にあった XML ファイルを head -c 1m したものです。
参照の局所性だとかテキストデータの性質とか考慮すべき点はたくさんありますが、これだけの差は容易にひっくり返らないのでは、と思います。

うーーん。どっか間違えているのかな。

#include <cassert>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include "mmap_file.hpp"

typedef char         Char;
typedef const Char*  String;

void swap(String& a, String& b) {
    if( &a == &b ) { return; }
    const String  temp = a;
    a = b;
    b = temp;
}

int qsort_cmp(const void* p1, const void* p2) {
    const String&  s1 = *(const String *)p1;
    const String&  s2 = *(const String *)p2;
    return strcmp(s1, s2);
}

bool stl_sort_func_cmp(const String& s1, const String& s2) {
    return strcmp(s1, s2) < 0;
}

struct stl_sort_functor_cmp {
    bool operator()(const String& s1, const String& s2) const { return strcmp(s\
1, s2) < 0; }
};

void do_qsort(String* v, const int v_num) {
    qsort(&v[0], v_num, sizeof(&v[0]), qsort_cmp);
}

void do_stl_sort_func(String* v, const int v_num) {
    std::sort(&v[0], &v[v_num], stl_sort_func_cmp);
}

void do_stl_sort_functor(String* v, const int v_num) {
    std::sort(&v[0], &v[v_num], stl_sort_functor_cmp());
}

void multikey_quicksort(String* begin_, String* end_, int offset) {
    if( begin_ >= end_ ) {
        // do nothing
    }
    else if( end_ - begin_ < 8 ) {
        qsort(&begin_[0], end_ - begin_, sizeof(&begin_[0]), qsort_cmp);
    }
    else {
        assert( begin_ < end_ );

        const String&  pivot = *(begin_ + (end_ - begin_) / 2);
        const char     pivot_char = pivot[offset];

        String*  p1 = begin_;
        String*  p2 = end_ - 1;

        while( p1 < p2 ) {
            if( (*p1)[offset] <  pivot_char ) { ++p1; }
            else if( (*p2)[offset] >= pivot_char ) { --p2; }
            else { swap(*p1, *p2); ++p1; }
        }

        p2 = p1;
        for( String*  p3 = p1; p3 != end_; ++p3 ) {
            if( (*p3)[offset] == pivot_char ) { swap(*p2, *p3); ++p2; }
        }

        if( pivot_char ) {
            multikey_quicksort(begin_, p1, offset  );
            multikey_quicksort(p1,     p2, offset+1);
        }
        multikey_quicksort(p2,     end_, offset  );
    }
}

void do_multikey_quicksort(String* v, const int v_num) {
    multikey_quicksort(&v[0], &v[v_num], 0);
}

typedef void (*SortFunc)(String* v, const int v_num);

void benchmark(const char* name, SortFunc func,
               const String text, const int text_size) {
    assert( text[text_size] == '\0' );

    const int  v_num = text_size + 1;
    String*  v = new String[v_num];
    for( int i = 0; i < v_num; ++i ) {
        v[i] = &text[i];
    }

    const double  start_time = clock();
    func(&v[0], v_num);
    const double  elapsed = clock() - start_time;
    printf("%-20s:\t%.2f\t[%d %d %d]\n", name, elapsed / CLOCKS_PER_SEC,
           v[v_num/4] - text, v[v_num/2] - text, v[v_num-1] - text);
}

int main(int argc, const char** argv) {
    assert( argc == 2 );
    const char*  filename = argv[1];

    const MmapFile  mmap(filename);
    const String  text = mmap.data();
    assert( text );
    const int  text_size = mmap.size();
    assert( text[text_size] == '\0' );

    benchmark("qsort",             do_qsort,              text, text_size);
    benchmark("stl-sort-func",     do_stl_sort_func,      text, text_size);
    benchmark("stl-sort-functor",  do_stl_sort_functor,   text, text_size);
    benchmark("mulikey-quicksort", do_multikey_quicksort, text, text_size);
    return 0;
}

*1:というか、「ついで」と書いておいてなんですが、この　mulkey-quicksort の実用上の性能を知りたいというのが本来の動機だったので、「ついで」でも何でもなくこれが本命だということをいま思い出しました。これも yak shaving なのでしょうか。