セレクションソート(selection sort)は、大きな結果のものを基準に考えるときは、配列の中をスキャンして一番大きかったデータを末尾に設定し、末尾の範囲を1つ繰り下げて残りの中から再び一番大きなものを末尾に移動するという方法を行います。
小さな結果のものを基準に考えるときは、配列の中をスキャンして一番小さかったデータを先頭に設定するという、ちょうど逆の動きをします。
バブルソートよりも考え方がすっきりとしているような気がしますが。
セレクションソート単体で使うというケースはあまりありませんが、クイックソートの残りレコード数が少なくなったときに使われるケースもあります。動作がシンプルで、少ないレジスタ変数で動作し、スワップ回数が少ないので小さなレコード数の処理に向いています。
VC や VC++ の qsort 関数では、処理レコード数が少なくなったとき、オーバーヘッドの重いクイックソートのままではなく、セレクションソートを使っています。ソースリストではバブルソートと注釈がありますが、実際はセレクションソートです。
win32 環境での実行速度の例です。レコード数は 10 万件、数値の単位はミリ秒です。
Random32 Random32R Random15 Random15R Forward Reverse Constant Med Killer Type A(VC) 4508.43 4555.23 4508.43 4524.03 4508.43 4508.43 4664.43 4524.03 Type B(VC) 4399.23 4508.43 4508.43 4508.43 3400.82 3946.83 3416.42 4508.43 Type C(VC) 10530.07 10514.47 10514.47 10514.47 10514.47 10514.47 10498.87 10514.47 Type D(VC) 10514.47 10514.47 10514.47 10514.47 10514.47 10514.47 10514.47 10514.47 Type E(VC) 3057.62 3042.02 3026.42 3057.62 3026.42 3026.42 3010.82 3432.02 Type E(ASM) 3042.02 3042.02 3026.42 3042.02 3026.42 3026.42 3026.42 3432.02 Type F(VC) 10530.07 10514.47 10561.27 10514.47 10514.47 10498.87 10514.47 10514.47 Type F(ASM) 3042.02 3057.62 3042.02 3042.02 3026.42 3026.42 3026.42 3042.02
3秒台とか、4秒台の話をして「どうすれば速くなるか?」と考えたいのに、それを裏切るかのように 10 秒台が混じっています。
同様に、x64 環境での実行速度の例を掲載します。レコード長が 16 バイトになるので、 win32 より少し時間がかかります。
Random32 Random32R Random15 Random15R Forward Reverse Constant Med Killer Type A(VC) 4555.23 4555.23 4555.23 4555.23 4555.23 4539.63 4555.23 4648.83 Type B(VC) 4586.43 4555.23 4555.23 4570.83 4555.23 4555.23 4555.23 4555.23 Type C(VC) 10545.67 10514.47 10530.07 10514.47 10514.47 10530.07 10514.47 10514.47 Type D(VC) 10514.47 10467.67 10483.27 10530.07 10530.07 10514.47 10530.07 10530.07 Type E(VC) 3447.62 3400.82 3400.82 3416.42 3385.22 3432.02 3432.02 3712.82 Type E(ASM) 3400.82 3400.82 3400.82 3400.82 3385.22 3400.82 3400.82 3806.42 Type F(VC) 10576.87 10514.47 10530.07 10530.07 10514.47 10514.47 10530.07 10530.07 Type F(ASM) 3432.02 3400.82 3416.42 3416.42 3385.22 3400.82 3385.22 3416.42
やはり同じように、異常に速度が遅くなる場合があります。
Type E と Type F では、アセンブラで、「本来はこのような展開コードを生成して欲しい」という希望のものの数値を一緒に掲載しています。アセンブラでは同一内容で処理速度が速いのに、VC では異常に遅いという現象です。
ソースリストを掲載しますが、コピー & ペーストだと、インデントが壊れて汚くなっています。もう少しきれいなソースリストも用意しました。速度測定プログラムでのソースリストなので、処理を中断する Abort 処理が混じっていますから、削除してしまえばちょっとだけ処理速度が速くなります。スワップ処理に XMM レジスターを使うことで、ソート本体のレジスタ変数を少しでも確保して高速化する狙いがあります。
なお、アセンブラのソースは省略します。
static DWORD __stdcall SelectionSortAR(SortRecStruct* pArray, size_t pTop, size_t pBtm, bool* pAbort)
{ // forward scan
size_t sztMaxPtr, sztScan;
while( pTop < pBtm )
{
sztMaxPtr = pBtm; sztScan = pTop;
do
{
if( pArray[ sztScan ].Key > pArray[ sztMaxPtr ].Key )
sztMaxPtr = sztScan;
sztScan++;
}
while( sztScan < pBtm );
SwapUU( &pArray[ sztMaxPtr ], &pArray[ pBtm-- ] );
if( *pAbort ) return 1223;
}
return 0;
}
DWORD __stdcall SelectionSortA(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
return SelectionSortAR( pArray, 0, pRecCount - 1, pAbort );
}
static DWORD __stdcall SelectionSortBR(SortRecStruct* pArray, size_t pTop, size_t pBtm, bool* pAbort)
{ // reverse sccan
size_t sztMinPtr, sztScan;
while( pTop < pBtm )
{
sztMinPtr = pTop; sztScan = pBtm;
do
{
if( pArray[ sztScan ].Key < pArray[ sztMinPtr ].Key )
sztMinPtr = sztScan;
sztScan--;
}
while( sztScan > pTop );
SwapUU( &pArray[ sztMinPtr ], &pArray[ pTop++ ] );
if( *pAbort ) return 1223;
}
return 0;
}
DWORD __stdcall SelectionSortB(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
return SelectionSortBR( pArray, 0, pRecCount - 1, pAbort );
}
static DWORD __stdcall SelectionSortCR(SortRecStruct* pTop, SortRecStruct* pBtm, bool* pAbort)
{ // forward scan
SortRecStruct *RecMaxPtr, *RecScan;
while( pTop < pBtm )
{
RecMaxPtr = pBtm; RecScan = pTop;
do
{
if( RecScan->Key > RecMaxPtr->Key )
RecMaxPtr = RecScan;
RecScan++;
}
while( RecScan < pBtm );
SwapUU( RecMaxPtr, pBtm-- );
if( *pAbort ) return 1223;
}
return 0;
}
DWORD __stdcall SelectionSortC(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
return SelectionSortCR( pArray, &pArray[ pRecCount - 1 ], pAbort );
}
static DWORD __stdcall SelectionSortDR(SortRecStruct* pTop, SortRecStruct* pBtm, bool* pAbort)
{ // reverse sccan
SortRecStruct *RecMinPtr, *RecScan;
while( pTop < pBtm )
{
RecMinPtr = pTop; RecScan = pBtm;
do
{
if( RecScan->Key < RecMinPtr->Key )
RecMinPtr = RecScan;
RecScan--;
}
while( RecScan > pTop );
SwapUU( RecMinPtr, pTop++ );
if( *pAbort ) return 1223;
}
return 0;
}
DWORD __stdcall SelectionSortD(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
return SelectionSortDR( pArray, &pArray[ pRecCount - 1 ], pAbort );
}
これは、最小値または最大値を見つける if 文と、その結果最小値または最大値のポインタを代入する部分にあります。
if( RecScan->Key > RecMaxPtr->Key )
RecMaxPtr = RecScan;
この展開に、CMOVxx 命令を利用すると、処理速度が大幅に遅いプログラムになります。CMOVxx 命令は、本来は SSE2 とは関係のない命令ですが、コンパイラの最適化の方法を教えてあげる手段としては、SSE2 と同一扱いされています。
CMOVxx 命令を使わない展開の疑似コード CMOVxx 命令を使った展開の疑似コード CMP [ DestAddress ], EAX
JBE short @F
MOV MaxPtr, DestAddress
@@:CMP [ DestAddress ], EAX
CMOVA MaxPtr, DestAddress
CMOVxx 命令を使わない場合は、条件ジャンプを使って代入文をスキップするコードを使います。
一方で、CMOVxx 命令を使うと、条件ジャンプの必要もなく、1行減りますし飛び先ラベルも不要になります。
C言語では、ソースコード中にもアセンブラが書けるというのは普通にありましたから、CMOVxx 命令が登場した時に、喜んでこの命令を使った処理を書いた人は多いのではないでしょうか。
Intel さんの資料では、CMOVxx 命令を使うことで分岐が発生せず、コードも短くなると解説していますし、同じ Intel さんの「最適化の手法」という意味の資料でも必ずこの命令は取り上げられています。
ですから、多くの人は次のように考えて、この命令を多用したはずです。
分岐が発生するということは、それまで行っていた命令フェッチや読み取った命令のデコードが、全部リセットされてしまうので、遅くなる。分岐が発生しないことは、リセットされないという意味だから、実行速度は速いに違いない。だから CMOVxx 命令は有効だ。と考えたはずです。
ところで Intel さんの資料は、CMOVxx 命令を使うことで分岐は発生しないし、命令コードも短くなりますとは書いていますが、だから速度が速くなるとはどこにも書いてありません。つまり、利用者が勝手に速度が速くなると勘違いして使っているだけのことです。
これは、スーパースケーラーがどのような動きをするか理解できていれば簡単なことですが、なかなか理解している人が少ないのが現状です。このような処理速度が遅い例は他にもあって、シフト命令やローテート命令が登場する場合の同時並行動作の限定事項とか、マイクロプログラムで動作する命令を実行させるときの限定事項、キャリーフラグを含めた加減算の動作などがあります。
ですから、かつて MS-DOS 全盛期の時代にアセンブラで活躍したベテランさんが、久々に「俺もプログラムを作るぞー」と参加してしまうと、悲惨な結果をもたらすことがほとんどです。処理速度の遅いストリング命令や、LOOP 命令などを普通に使う習慣が残っているため、完成したプログラムは遅くてとても実用には使えません。C言語で生成させた機械語オブジェクトの方が圧倒的に速度が速いという事態が普通に起こります。今となっては不適切な LEA 命令の使い方をしたばっかりに、遅くなるということも普通にあります。
いずれにしても、このまま処理速度が遅いままというわけにはいきません。そこで、CMOVxx 命令を使わない命令コードを生成するように、ソースを書き換えてみることにします。それが、次の Type E と Type F です。
static DWORD __stdcall SelectionSortER(SortRecStruct* pTop, SortRecStruct* pBtm, bool* pAbort)
{ // forward scan
SortRecStruct *RecMaxPtr, *RecScan;
DWORD MaxKeyValue;
while( pTop < pBtm )
{
RecMaxPtr = pBtm; MaxKeyValue = RecMaxPtr->Key; RecScan = pTop;
do
{
if( RecScan->Key > MaxKeyValue )
{
RecMaxPtr = RecScan; MaxKeyValue = RecMaxPtr->Key;
}
RecScan++;
}
while( RecScan < pBtm );
SwapUU( RecMaxPtr, pBtm-- );
if( *pAbort ) return 1223;
}
return 0;
}
DWORD __stdcall SelectionSortE(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
return SelectionSortER( pArray, &pArray[ pRecCount - 1 ], pAbort );
}
static DWORD __stdcall SelectionSortFR(SortRecStruct* pTop, SortRecStruct* pBtm, bool* pAbort)
{ // reverse sccan
SortRecStruct *RecMinPtr, *RecScan;
DWORD MinKeyValue;
while( pTop < pBtm )
{
RecMinPtr = pTop; MinKeyValue = RecMinPtr->Key; RecScan = pBtm;
do
{
if( RecScan->Key < RecMinPtr->Key )
{
RecMinPtr = RecScan; MinKeyValue = RecMinPtr->Key;
}
RecScan--;
}
while( RecScan > pTop );
SwapUU( RecMinPtr, pTop++ );
if( *pAbort ) return 1223;
}
return 0;
}
DWORD __stdcall SelectionSortF(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
return SelectionSortFR( pArray, &pArray[ pRecCount - 1 ], pAbort );
}
このように、生成されたオブジェクトが期待通りになっているかどうか、適切に評価し、場合によってはソースの書き方も変える必要があります。セレクションソートではこの現象が特に起こりやすいので、使う場合には必ず検証作業を行わないと、思ったよりも速くならないプログラムになってしまいます。
特に、クイックソート内部の組み込み部分として採用するときには、速度が低下しているソースリストを使うと全く意味が無くなってしまいますから、十分に検証したものを使う必要があります。
CMOVxx 命令の実行速度が遅いのは、もしかすると数年後に登場するプロセッサーでは改善されているかもしれません。
しかし、どのような場合であっても、プロセッサーの特徴や、コンパイラの特徴を理解して、確実に作業を進める心構えが重要です。
← Gnome Sort | Min Max Sort →
contents |
Top Page caution Bubble Sort Odd Even Sort Cocktail Sort Gnome Sort Selection Sort Min Max Sort Insertion Sort Shell Sort Heap Sort Comb Sort Merge Sort Quick Sort Do-Re-Mi-Fa Sort chat |