＊＊＊＊＊　クイックソート開発　の　概要　＊＊＊＊＊

1997年に当時の fj.sources にqsort(クイックソート)の
ベンチマークテストの依頼を掲載しました。

その結果(http://ww51.tiki.ne.jp/~srr-cake/qsort/qs6qs7-rslt.txt) ※１、
自作のqsort(qs6,qs7)の性能はともかく、コンパイラ付属のqsortの中に
まともな性能が出ないqsortが多数存在することが判明しました。

今回、より高速な qsort (qs9 と qs10) を開発しました。


１．各ファイルの概略

qs9e17.c     : 新しく開発したqsort qs9。
qs10a5.c     : 新しく開発したqsort qs10。-DMEMCPYで、要素の移動にmemcpyを使用。
mm88g.c      : 要素のスワップ/移動関数。8バイト整数対応。繰り返しの展開(8回分)を実施。
main_prog.c  : 比較回数・代入回数・処理時間などを計測して表示するプログラム。
benchmark.sh : ベンチマークテストを行うシェルスクリプト。
　　　　　　　 コンパイルオプション -DDEBUG を指定すれば、要素の代入回数を測定できる。



２．qs6 qs7 qs8 qs9 qs10 の概要

qsortにもいろいろな方式がある。
配列を２つに分割するキー値を持つ要素を分割要素と呼ぶ。
以下の例では、先頭の(5)が分割要素に選ばれたものとする。
各qsortは矢印左の配列を矢印右のようにする。「|」は分割した位置を示している。


２．１．処理の概要

従来型  565238 → 532|568   2番目の(5)が右に移動している。「(5)不移動」の実装は異常事態を招く。（※１）
ｑｓ６  565238 → 5352|68   従来型は2つの(5)が左右に別れるが、qs6では必ず片方に集める。次に 235|5|68 とする。
ｑｓ７  565238 → 55|32|68  すべての(5)を一旦左右に集める。普通は左右両端に(5)がくる。 次に 32|55|68 とする。
ｑｓ８  ｑｓ６とｑｓ７の混合処理を導入して、多くのケースで高速となるようにした。
ｑｓ９  565238 → 23|55|68  分割要素と同じキー値を持つ要素を中央に集める。移動できなくなった後に工夫あり。
ｑｓ10  ｑｓ９を使用して間接ソートを実行。（間接ソート：「元配列の各要素へのポインタ」の配列を別途に作り、
　　　　　　　　　　　　　　　　　　　　　　その配列をソートする。その後、元配列を正しく並べ替える。）


２．２．各qsortの特徴

従来型  少し遅い。異常事態を起こす間違った実装が過去にいくつもあった。（※１）
ｑｓ６  要素の比較回数が多く、移動回数が少ない。平均するとｑｓ７と同じか少し速い。
ｑｓ７  要素の比較回数が少なく、移動回数が多い。キーが２値(男女など)の場合、要素の移動回数が激増する。
ｑｓ８  下記のパラメータの設定をしなくても、既定値で十分な性能が出る。
        qsortでは、要素数・要素サイズ・比較関数の重さ・キー値の分布ごとに、最適なqsortは異なる。
        要素数・要素サイズは、ソートの開始時点で確定するのでアルゴリズムで対応可能である。
        しかし、比較関数の重さ・キー値の分布は、不明なままソートを実行することになる。
        ｑｓ８ではソート対象の性質が分かっていれば、qsort()を呼び出す前に下記のパラメータを設定して
        対処することが可能である。（または、適当なパラメータを多数試して、その結果で設定）
ｑｓ９  多くの場合、比較回数・移動回数が最小となる。
ｑｓ10  要素サイズ >= _QS_MID3(既定値400) のときは、自動的にｑｓ９＋間接ソートになる。
        また、「ポインタ配列」と「要素の移動のための領域」が別途必要となる。


２．３．大域変数パラメータ

_QS_MID1 要素の個数が n<=_QS_MID1(既定値140) のときに３点処理を行う。
_QS_MID2 要素の個数が n<=_QS_MID2(既定値900) のときに９点処理を行う。それ以外は２７点処理。
_QS_MID3 要素サイズsize>=_QS_MID3(既定値400) のときに間接ソートを追加。それ以外はｑｓ９だけ実行。
_QS_MVR  mm88g.cのmmswapで size%4==0 && size>_QS_MVR(既定値116) なら、８バイト整数でのswapに挑戦。



３．ベンチマークテストを行うプログラム　main_prog.c

main_prog.c は clock()関数を用いて実行時間を測定する。
簡易版の「ソートの正しさ検査」を行っている。正式な「ソートの正しさ検査」は別に実施している。
main_prog.c は次のパラメータを指定して実行する。

引数１　キー値の種類を指定する 0:定数 -1:昇順 -2:降順 -3:同値なし乱数 1:乱数 d>=2:乱数%d
引数２　配列の要素数
引数３　配列の要素サイズ(byte数)（4以上かつ4の倍数であること）（qs自体は1byte単位で指定可能）
引数４　ソートの繰り返し回数（繰り返し毎に配列の要素のキー値は異なる）
引数５　_QS_MID1 の値
引数６　_QS_MID2 の値　（main_prog.cでは_QS_MVR==116は変更できない）
引数７　_QS_MID3 の値
引数８　比較関数の重たさを調整する数値。大きいほど比較関数が重たくなる。  

main_prog.c 1回の実行で、実行結果を1行出力する。1行は14項目ある。例と意味を次に示す。

    qs9e17        d=-3         e=10000     s=8      10              R10000      M300:300:8:0:
　プログラム名  キー値の種類  要素の個数  大きさ  配列の大きさ/M  繰り返し回数　引数５〜８の値

    c=130260    1302608733    a=65855     658555016    i=196115   T=19.06   191  
　平均比較回数  全比較回数  平均代入回数  全代入回数  比較＋代入  処理秒数  平均処理時間(10μ秒単位)

これをstdoutに出力する。（前半の７つと最後の２つはstderrにも出力する）



４．開発時の性能測定の方法(main_prog.cの引数)

キー値の種類　：引数１を d=[ -3 10000 1000 300 100 30 10 3 2 ] の９通りで実施。
要素数　　　　：引数２を e=10000 固定で実施。(1000 10000などでも測定したが、大きな差はなかった)
要素サイズ　　：引数３を s=[ 8 20 40 100 200 500 1000 ] の７通りで実施。
繰り返し回数　：引数４を調整して、main_prog.cの１回の実行が３０〜５０秒で終了するようにした。
比較関数の重さ：引数８を m=[ 0 2 4 ] の３通りで実施。

　修正を重ねた数百種類のクイックソートのプログラムを、
　上記の、１８９（＝９ｘ７ｘ３）通り のパラメータで実行した。



５．その他

mm88*.cでは、sizeが4の倍数・8の倍数のとき、各々に合った高速化を行っている。
1の倍数のときの高速化も同じ方法で可能であるが、
　１）必要性が少ない　２）コードが大きくなり過ぎる
ために、mm88*.cでは1の倍数のときの高速化を行っていない。

ben_sample.txtでもわるように、８バイト整数がハードウェアで処理できるシステム(64bitモード)上で、
多くのコンパイラ標準qsortにおいて、配列の要素のsizeが4の倍数(20byteなど)のとき、
かなり遅くなる。ダミー4byteを加えてsizeを8の倍数(24byte)にすれば速くなる。
しかし、これでは4byte(配列全体の2割)の領域が無駄になる。
mm88*.cは、20byteのままで高速に動作するよう工夫されている。

配列の要素数・要素サイズ・キー値の種類　の違いにより
最適な _QS_MID1 _QS_MID2 _QS_MID3 の値は異なります。
各値を変更してqsort()を呼び出すことで、速度の向上が期待できます。
キー値の種類が少ない・要素サイズが大きい ときは、間接ソートなしのｑｓ９が高速です。
特に d<=10 size>=500 の場合は、_QS_MID3=size+1に変更してみてください。