分岐しないソート (のジェネレータ）

GCC

分岐しない4要素のソート、GCC/Linux/x86,x86_64,arm版


こちらに、「分岐しないソート」という記事があります。短いので読んでいただくほうがよいと思いますが、文章＆アセンブリ言語のコードの内容を要約すると、

4要素のソートは、頑張れば5回の比較と5回の交換でできるよ。さらに、交換を Pentium Pro で追加された命令であるCMOVcc(Conditional Move)で行うことにすれば、「cmp b, a して、 b < a のときだけ b と a をswap」という処理を分岐命令なしで行うことができるから速いよ。

となります。この、「4要素専用・VC++専用の分岐しないソート」を、いつものように(?) GCC向けに書き直してみました。こちら。

分岐しないN要素の odd-even mergesort、GCC/Linux/x86_64版

(x86_64のお勉強がてら、ちょっとコードを書いたので晒します)


さて、4要素固定だとちょっと私には使い道がないので、8,16,32,64,128...要素向けのソート関数も欲しいなっと。本当は、元のページで引用されている2000年頃のfj.comp.lang.cの議論を読むと8要素以上のアイディアがいろいろ書かれていてよさそうなんですが*1、今回は時間もないのでfjは見なかったことにして...

  • 1-2時間で実装できて
  • 要素数が128くらいまでの場合に速くて
    • std::sort(), std::stable_sort(), std::__insertion_sort() の3つに勝てればOKさ
  • 分岐しない :-)
    • 理由: 最速かどうかは知りませんが、なんとなく格好いいから

というのをでっちあげて使うことにしました。分岐しないのがいいなぁと思ってしまった関係上、ターゲットはx86かx86_64かARMになり*2、できあがるのはアセンブラで書かれたソート関数ということになります。今回はx86_64をターゲットにしました。x86_64アセンブラのお勉強がしたいので...。


また、分岐しないのがいいなぁと思ってしまった関係上、ソーティングのアルゴリズムは、「ソートする要素数が決まれば、比較＆交換処理を行うべき位置が事前にすべて決まるもの」になります。そういうアルゴリズムならなんでもOKです。「data-dependent なソート」とか「sorting networkを構成できるソート」とか呼ばれるもの? ですね（たぶん）。data-dependent なソートとしては、bubble sort, shell sort, insertion sort などがわかりやすいですが、ここでは

の2つを候補にしました。なぜかというと、これらのソートは比較回数が非常に少なくて済む（らしい）からです。bitonic sort よりも odd-even mergesort のほうが、さらに比較が少ないということですので、今回はそちらにします。グーグル先生に聞いた限りでは、ほかに良さげなものが見当たらなかったので。このソートを、上記ページを参考に、まず普通にC言語で実装してみると、次のようになります*3。

static void compare_and_swap(unsigned int* a, unsigned int* b) {
  if (*a > *b) {
    unsigned int tmp = *a;
    *a = *b;
    *b = tmp;
  }
}

static void odd_even_merge(unsigned int* d, int n, int skip) {
  int idx;
  if (n > 2) {
    odd_even_merge(d,        n / 2, skip * 2);
    odd_even_merge(d + skip, n / 2, skip * 2);
    for(idx = 1; idx <= n - 3; idx += 2) {
      compare_and_swap(&d[idx * skip], &d[(idx + 1) * skip]);
    }
  } else {
    compare_and_swap(&d[0], &d[skip]);
  }
}

void odd_even_mergesort(unsigned int* d, int n) {
  assert(n > 0 && __builtin_popcount(n) == 1); // nが2の累乗であるか確認
  if (n > 1) {
    odd_even_mergesort(d,         n / 2);
    odd_even_mergesort(d + n / 2, n / 2);
    odd_even_merge(d, n, 1);
  }
}


このソート関数の冒頭に、 compare_and_swap(a,b); している箇所があります。ここを、「compare a,b; conditional_swap a,b; のようなアセンブリ言語のコードをprintfする」処理に置換すれば、ソート関数が、「分岐しないでソートを行うアセンブリ言語のソースコードを吐くプログラム」に化けるわけです。次のような .s が出力されます。

.text
.globl odd_even_sort8

odd_even_sort_8:
   compare d0, d1    // 要素0と要素1を比較
   conditional_swap  // 要素0 > 要素1 なら入れ替え
   compare d2, d3    // 要素2と要素3を比較
   conditional_swap  // 要素2 > 要素3 なら入れ替え
   ...
   ret

bitonic sortで同じことをしたい場合は、こちらのBitonicSort関数を参考にするとよいでしょう*4。


これで、gen_sort.cpp ができました。実行すると Linux/x86_64 向けの .s ファイルを吐きます。ソート関数のオブジェクトサイズは、64要素用で20k, 128要素用で59k, 256要素用で160kになりました。後述するように、オブジェクトのサイズは重要です。

% g++ -o gen_sort gen_sort.cpp 
% for N in 4 8 16 32 64 128 256 512 1024; do ./gen_sort 0 $N > oem_sort_${N}.s ; gcc -c oem_sort_${N}.s ; done

% wc -c oem_sort_*.s | sort -n
    655 oem_sort_4.s
   1832 oem_sort_8.s
   8127 oem_sort_16.s
  28202 oem_sort_32.s
  85580 oem_sort_64.s
 238578 oem_sort_128.s
 630842 oem_sort_256.s
1626758 oem_sort_512.s
4058838 oem_sort_1024.s

% wc -c oem_sort_*.o | sort -n
    791 oem_sort_4.o
   1015 oem_sort_8.o
   2208 oem_sort_16.o
   6008 oem_sort_32.o
  20016 oem_sort_64.o
  58785 oem_sort_128.o
 159481 oem_sort_256.o
 411529 oem_sort_512.o
1026850 oem_sort_1024.o

はやさ


速いコードを書くノウハウなどまったくありませんので、このへんでやめとくほうがいいんですが...一応測定してみました。C++から呼ぶときのプロトタイプは extern "C" void odd_even_sortN(unsigned int* data); です。次の4種類のソートを各1000万回実行し、かかった時間を比べました。STLのソートにはちゃんと関数オブジェクトを渡しています。ソート対象データは /dev/urandom から適当に得ました。

  1. 分岐しない odd-even mergesort
  2. (念のため) 分岐しない bitonic sort
  3. std::__insertion_sort() (挿入ソート)
  4. std::sort()　(基本的にクイックソート)

環境は次の通り:

% uname -a
Linux ath64 2.6.16-1.2122_FC5 #1 SMP Sun May 21 15:01:10 EDT 2006 x86_64 x86_64 x86_64 GNU/Linux

% dmesg | grep CPU:
CPU: L1 I Cache: 64K (64 bytes/line), D cache 64K (64 bytes/line)
CPU: L2 Cache: 512K (64 bytes/line)

% rpm -q gcc libstdc++
gcc-4.1.0-3
libstdc++-4.1.0-3

結果:

% g++ -Wall -O2 -o benchmark benchmark.cpp oem_sort_*.o bit_sort_*.o
% ./benchmark
---------------------------------------------
       type               time        delta      
---------------------------------------------
null:                    8.440000    0.000000

odd_even_sort8:          8.540000    0.100000
bitonic_sort8:           8.580000    0.140000
__insertion_sort(8):     9.950000    1.510000
sort(8):                10.000000    1.560000

odd_even_sort16:         9.290000    0.850000
bitonic_sort16:          9.580000    1.140000
__insertion_sort(16):   11.910000    3.470000
sort(16):               12.010000    3.570000

odd_even_sort32:        11.910000    3.470000
bitonic_sort32:         13.620000    5.180000
__insertion_sort(32):   17.400000    8.960000
sort(32):               18.620000   10.180000

odd_even_sort64:        18.410000    9.970000
bitonic_sort64:         25.340000   16.900000
__insertion_sort(64):   33.280000   24.840000
sort(64):               33.170000   24.730000

odd_even_sort128:       35.050000   26.610000
bitonic_sort128:       203.250000  194.810000
__insertion_sort(128):  52.540000   44.100000
sort(128):              46.270000   37.830000

odd_even_sort256:      323.310000  314.870000
bitonic_sort256:       553.850000  545.410000
__insertion_sort(256):  91.670000   83.230000
sort(256):              70.230000   61.790000

ソートするデータの準備(/dev/urandom読みetc.)だけで合計8秒以上かかっています。速度比較は delta のほうで行うとよいかと思います。とりあえず128要素のソートまでは、今回の「分岐しない odd-even マージソート」が他の3つのソートを抑えて最高速です。

まとめ


~128要素程度の少ない要素のソーティング処理で、std::sort() がボトルネックになってしまった場合、std::sort() を「分岐しない odd-even mergesort」などに置き換えることで、性能の改善ができるかもしれません。

注意点


odd-even mergesortが256要素で、bitonic sortが128要素で急に遅くなったのは、*.o のサイズがCPUのL1命令キャッシュの容量(私のAMD64環境では、dmesgによると64kバイト)を越えてしまったからでしょうか。cachegrindで観察すると、これらの遅くなるソートから急に、L1 miss rate が 0.0% から 7.6% に跳ね上がりますので。

% valgrind --tool=cachegrind ./test
...
=2513= I1  miss rate:        7.67%

ご注意くださいませ。

TODOのようなもの

*1:C++のテンプレートでコンパイル時にsorting networkを構成する方法、少ない要素数のときに如何にうまい具合に複数のアルゴリズムを組み合わせるか、など

*2:CPUの都合のほか、私の知識の都合で

*3:Web上にCやJavaでの実装が見付からなかったので自分でぱっと書きました。間違ってたらご容赦

*4:注:わたしはちゃんと読んでいません