Sqsort のベンチマークテストの要領

１．Sqsort の概略    http://ww51.tiki.ne.jp/~srr-cake/qsort/sqs18j/qiita.txt



２．http://ww51.tiki.ne.jp/~srr-cake/qsort/sqs18j/ から次の５つのファイルをダウンロードする。

    http://ww51.tiki.ne.jp/~srr-cake/qsort/sqs18j/benchmark 
    http://ww51.tiki.ne.jp/~srr-cake/qsort/sqs18j/TimSort.java   
    http://ww51.tiki.ne.jp/~srr-cake/qsort/sqs18j/Sqsort.c   
    http://ww51.tiki.ne.jp/~srr-cake/qsort/sqs18j/MainTim.java    
    http://ww51.tiki.ne.jp/~srr-cake/qsort/sqs18j/MainSqsort.java   



３．benchmark を実行する。実行結果は benchmark.txt へ書き込まれる。

    Sqsort.c は cpp で Sqsort.java へ変換してからコンパイルする。

　　Main*.java Sqsort.java TimSort.java は benchmark の中でコンパイル・実行される。
　　Main*.java の引数と出力の説明は、「４」を参照
。
    bench-sample.txt は benchmark.txt の例です。



４．ベンチマークテストを行うプログラム　Main＊.java

    Main*.java は getCurrentThreadCpuTime() を用いてCPU処理時間を測定する。
    Main*.java は次のパラメータを指定して実行する。

    引数１　キー値の種類  0:定数 -1:昇順 -2:降順 -3:ユニーク乱数 1:乱数 d>=2:乱数%d
    引数２　ソートする配列の要素数
    引数３　ソートの繰り返し回数（測定時間の精度向上のため）

    Main*.java 1回の実行で、実行結果を1行出力する。
    同じものをSystem.errとSystem.outに出力する。各行の例と意味を次に示す。

          TimSort       d=-3        e=10000      R=2000     cmp=240783126   C=8.22
     　プログラム名  キー値の種類  要素の個数  繰り返し回数　 比較回数    CPU処理秒数

    Sqsort は java で記述したソートなので、参照型の配列をソートします。
    なので、要素サイズの大小による比較は行っていません。





★Sqsortの改良

公開した Sqsort は部分配列の長さが n<=15 なら挿入ソート、n>=16 なら３点処理 を行う。

開発過程では下記のような処理も実験している。

       部分配列の長さ 対応するソートの種類
                 n=0   何もしない
                 n=1   必要なら要素を複写
                 n=2   
                  ：   挿入ソート
                n=15   
                  ：   精密３点処理
                n=50   
                  ：   ３点処理
               n=220   
                  ：   ９点処理
               n=880   
                  ：   ２７点処理

この改良は、Sqsortを言語Cで記述した場合や、javaの32bit環境では一定の性能を発揮する。
しかし、javaの64bit環境ではかえって遅くなるケースが多発した。
そのため、最もコンパクトな版を公開することとした。




★使用した環境

Windows＋cygwin
コンパイラ javac  AdoptOpenJDK                jdk-11.0.8.10-hotspot
64bit環境  java 　AdoptOpenJDK                jdk-11.0.8.10-hotspot
32bit環境  java 　AdoptOpenJDK                jdk-11.0.8.10-hotspot
64bit環境  java   Java SE Development Kit 15　jdk-15.0.2 



