このサイトで掲載するソースリストは、Windows 上で動く Visual Studio 2005 に収録されている Visual C++ でコンパイルした結果について記事を掲載しています。Windows ですから、普及台数が極めて多いことになります。
2005 というと、この記事を書いている 2013 年からでも古いソフトになりますが、お仕事の都合で古い Windows や MS-DOS 関係のプログラムの修繕なども未だに頼まれることが多い関係で、古いものに対応できる 2005 を未だに使っているわけです。
また、すべての CPU のテストなども数が多くてできませんから、主にプログラム開発で使っている CPU と、執筆時点で最先端の CPU の２種類を代表としてとりあげています。どちらも Intel 製のマイクロプロセッサです。また、ソースプログラムでは、少しでも処理速度を速くするために、CPU 固有の XMM レジスターも登場します。
ですから、執筆時点では、Windows で Intel 製マイクロプロセッサーという２つの条件以外の環境では全くテストしていません。この２つの条件以外のシステムでは、処理速度が「速い」とか「遅い」という結果が逆になることもあるかもしれません。
Ｃ言語は、コンパイルして機械語を生成し、その機械語を実行します。重要なのは、ソースを実行しているのではなく、生成された機械語を実行していることにあります。
プログラムを作る人は、生成された機械語が、自分の希望する展開になっているかどうかを確認しながら作業を進めます。
というはずなんですが、残念なことに、ほとんどのプログラム製造者は、展開された機械語が速いのか遅いのかの興味も持たず、検証もせずにそのまま使っていることが圧倒的に多いということです。
速い機械語として展開するのか、遅い機械語として展開するのかはコンパイラの仕事であって、私の責任ではありませんと、責任転嫁しているということです。
ですから、ソートに関する書籍やインターネットの記事を見ても、この傾向は同じです。「Ｃ言語講座」のような意味を持つ個人のサイトだけでも、日本に限っても数十万サイトはあるようです。
ですが、記事の書き方はどれも同じです。××ソートの紹介というタイトルを書きソースを１種類だけ書いて説明し、この方法は速いとか遅いとか書いてあるわけです。
本当に１種類だけのソースで、特徴や特性が得られますか？ ソースの書き方に問題はありませんか？
ちょっと実験してみましょう。
バブルソートで、次の２つのリストを用意します。
Type A Type B if( Array[ ScanPtr ] > Array[ ScanPtr + 1 ] )
Swap( …, … );if( Array[ ScanPtr + 1] < Array[ ScanPtr ] )
Swap( …, … );
違う部分は簡単です。配列の低いアドレスを基準にするか、高いアドレスを基準にするかというだけの話です。
これを、執筆時点で時代の先端を走る Core i7 Extream Edition という、結構なお値段がする高速プロセッサーでソートしてみます。温度によって処理速度が変わる機構がありますから、比較実験ですからこの機構は解除し、定格クロックで動作させることにします。クロックは、3.33GHz ということになっています。
単純に数値を並べ替えるだけの仕様です。レコード数は 131,072 件です。
Type A Type B 25,319 ミリ秒 26,395 ミリ秒
Windows なので、マルチタスク（マルチプロセス、マルチスレッド）ですから、他のバックグラウンドの処理も少しは動いています。ですから、何回か測定しているとわずかに速度の違いがありますが、その違いは 15 ミリ秒ほどになります。それを考慮しても、Type A は 25 秒台、Type B は 26 秒台になります。何回やっても結果は同じです。
つまり、Core i7 Extream Edition のこの環境では、Type A はType B より１秒速く動作したという実績になります。
どうして２つのソースに差がでるか、あなたは説明できますか？ マイクロプロセッサーの特性を理解していない人は説明できないことでしょう。
でも、このお話は「序の口」です。次のお話が本題になります。
Core i7 Extream Edition は大変優秀な性能なんですが、やっぱりお値段がちょっと…。Core i7 どころか、マルチコア CPU 事態がお値段が高いので、実際には市場で圧倒的に多いのが廉価版の Celeron というプロセッサーで、しかもシングルプロセッサーというのが多くを占めます。個人でパソコンを買うときは、もう少し性能の良いマルチコアプロセッサーを書いう人が多いのですが、業務用端末としては価格の安い Celeron プロセッサーで十分です。メイン業務はサーバーで行いますから、端末としては「とりあえず動く」というレベルで十分です。ちゃんとインターネットも閲覧できますし、ワープロも使えます。この業務用端末として、数が多いというわけです。もちろん、Celeron にもマルチコア版のラインナップもあります。しかし、やはり売れ筋はお値段の安いほう。
では、その Cerelon で同じプログラムを動かしてみます。これは Pentium 4 CPU で動かすのと同じという言い方もできます。定格クロックは 1.6GHz で、メモリ速度も遅いので、先ほどの Core i7 よりは当然遅くなります。
Type A Type B 61,406 ミリ秒 48,266 ミリ秒
今度は 61 秒と 48 秒で、その差 13 秒で Type A ではなく、Type B が圧倒的に速くなりました。ソースの書き方で１秒、２秒違うということはよくある話ですが、これほど差が出ると真面目に考える必要があります。13 秒の差という言い方もできますが、実行時間が 78.6% に減ったという言い方もできます。
61 秒という数字ですが、この数字は極めてスタンダードな数字で、Ｃ言語だろうと、アセンブラでの直接記述だろうと、この程度の数字になります。コーディングミスでもなければ、怠慢しているわけでもありません。つまり、Type B の 48 秒という数字がむしろ「異常」という言い方もできます。しかし、これだけの性能差があるのなら、他の場面でも積極的に利用したくなります。ただし、この現象は最新プロセッサーでは処理が変更されています。
あなたはこの現象をちゃんと説明できますか？ 本物のプロなら簡単に説明できます。当たり前の話だからです。では、「Ｃ言語講座」とかいうサイトを開設している個人の方はこの説明をちゃんとできますか？ 説明ができるのなら、ソースリストが１種類しか掲載していないということはあり得ませんよね？ 記事を掲載するにあたって、いろいろなケースを試しているはずですから。
いや、個人だけではありません。中には大学の情報関連とか、コンピューター専門学校でも同じようなソートの解説記事があります。しかし単純に１種類だけを書いて、それがすべての結論であるかのような書き方をしています。
MOV 命令でアドレスを流すのと、CMP 命令でアドレスを流すときの、両者の違いを正しく説明できますか？ MS-DOS 全盛期の頃のプロセッサーとは考え方も動作も違うんですよ。これからプログラムを作ろうとする学生さんや、企業の新入社員さんに、正しい知識を教えていますか？ 注意事項を教えていますか？ これは応用じゃないですよ。基礎ですよ基礎。基礎中の基礎。だって、CPU の動作ですからね。それを教えないから、「動けば何でもいい」というプログラマを大量に生み出しているのではないですか？ 遅いプログラムにつき合わされて泣いている事務の女の子の姿を、あなたは想像できますか？ 代表で１種類の CPU を教えるだけでいいんです。 実戦配備になったときは、さすがに応援できないから、その時は自分で調べてねと言えばよいだけの話です。物事を考えられる人物を養成するのか、何も考えない安易な人物を養成するのか、考えたほうが良いのではないでしょうか？
新しいプロセッサが登場したときに、その特性のまとめを行っている人にとっては、このような現象は早々と情報収集をして対策を作っておきます。このような作業を行っている企業や学校などは信頼性が高く評価されます。
ところが、そのような地道な作業をしている人は残念なことに非常に数が少ないのが実態です。
「Ｃ言語講座」の類のソートの記事に関しては、これだけではありません。ここからこの範囲までをソートしてねという、範囲を指定するタイプのとき、その範囲を符号付き整数型である int 型で宣言している人が圧倒的に多いということです。ちゃんと意味を分かっている人は unsigned int で定義しますが、ごく少数で、ほとんどの記事は int 型です。もし、他人に何かを並び替えてねという本物の作業の時、マイナス何番目からマイナス何番目の範囲を並べ替えてくださいという依頼の仕方をしますか？
さらに、執筆時点で販売されている最先端のプロセッサでは、符号なし整数型は、符号付き整数型よりも高速動作するように設計されていたりします。ソートするデーターのキーの型が符号付き整数型で指定されている場合はもちろん符号付き整数型を使う必要があります。しかし、その場合でも、ここからここまでの範囲という添え字の範囲指定に符号付き整数型を使う必要はありません。
問題はまだ続きます。Ｃ言語の展開オブジェクトを使う場合、配列型のままで比較や転送を行った方が良いのか、ポインタ型で比較や転送を行った方がよいかという問題があります。スーパーコンピューターで、FORTRAN を使うときは配列型で記述すると高速なコードを生成してくれることが多い傾向にありますし、マイクロプロセッサでＣ言語を使う場合はポインタ型を使うと配列型よりも 30% 程度高速なコードを生成してくれるというのはよくある話です。
ところが、「Ｃ言語講座」の類はやっぱり配列型の１種類を書いているだけ。
しかも、たいてい変数名は i とか j が多くて、結局のところ FORTRAN 全盛期に移植されたコードをどこからか入手し、それをそのまま記事にして掲載しているだけの話で、マイクロプロセッサをきちんと理解しているとか、コンパイラを理解しているとかというと、少なからず疑問です。
このサイトをご覧の方は、標準装備の qsort 関数では遅くてイライラするなどの、何かの事情があってもっと速いものを探している方が多いことでしょう。あるいは、学生さんで、ソートについて勉強中なので、たまたま目にしたのかもしれません。あるいは、プログラムを作る仕事に就職してしまった社会人１年生が、研修の課題を出されて、本来なら自分で考えなければいけないのに、インターネットでググって簡単に済ませようとしているのかもしれません。
いずれにしても、書籍やインターネットで掲載されているソースリストをちょっと試しただけで、それがすべての結論であるかのような錯覚をしないことが重要です。本に書いてあるからそうだとか、国立の大学の先生が説明しているからそうだとかいう話ではありません。
どこからかソースリストを入手してきて、自分の環境に合うようにとりあえず移植。やってみた。動いた。だからこのリストで OK という簡単な結論になっていませんか？ 本当に CPU の性能にぴったりあっていますか？ コンパイラの展開コードは希望する内容にふさわしいものですか？
順方向スキャンが良いのか、逆方向スキャンが良いのか、配列型が良いのかポインタ型が良いのかなど、本当に速い処理が欲しいのなら、実際に自分自身でテストしてみることです。机上の理論で終わらせないこと。実際に動かすことが重要です。しかも、その結論は、あなたが使ったコンパイラで、あなたが使ったマイクロプロセッサの結果でしかありません。完成した機械語を、他のマイクロプロセッサで動かすと、逆に遅くなるかもしれません。もしかすると、５年後に登場した新型プロセッサでは全く別の現象が起きるかもしれません。
医薬品などで考えるとわかりやすいかと思います。何か新しいお薬を開発した。ちょっと試してみた。うまくいった。だから大量生産して大規模販売した。しかし、副作用が原因で多くの死者を出した。そんなときに、「いや研究中のテスト段階では最高性能でしたから何一つ問題ありません」という言い訳が世の中で通用しますか？
たかだがソートなので死者がでることはないでしょうけれど、かといって、ちょっと試した程度で安易に情報を紹介するのは考え物です。これが個人のブログで、「こんなことをやってみたらすごく速かった」という日記だったら問題ないことでしょう。しかし、「××講座」などと、いかにも専門でございます、私はパソコン博士ですと称して安易な情報をばらまいてているとなると、考え物です。
ですから、プロセッサの特性をよく勉強し、コンパイラの特性をよく勉強し、１種類だけで結論をだすのではなく、何種類かを実際に作成して評価したうえで処理をすすめていく習慣を身に着けることが重要です。また、得られた結論は、あくまでもその組み合わせの結果に過ぎず、他のシステムではどうなるかわからないという疑問を常に持ち続けることも重要です。
ソートの解説記事というと、単純に数字を並べ替えただけの記事が圧倒的に多いです。普通に考えると、32 ビット整数型の数値を並び替えるケースが多いという意味でもあります。このとき、ソートするデータのレコード長は、キー長そのものになります。
しかし、ソートする場面の現実は、単純に数字を並び替えるのではなく。レコード単位で並び替えます。キーだけを並び替えることはありません。キーの後ろにくっついている情報とあわせてソートします。
と言うかですね、数字だけを並び替えて、それが現実的に何の役に立ちますか？ というお話です。何の場面で使うのでしょうか。ご丁寧に、数字だけを並び替えた各種のソート技法を比較してグラフまで作成している人もいますが、それが現実的に何の役に立ちますか?
ソートの特性が比較回数と転送回数、転送サイズに大きく左右されることは考えるまでもありません。
ところが、数字だけを並び替えるようなリストだと、転送レートの評価が正しく行えません。転送方法によって、使用するレジスタの数が異なるために、速度の特性まで変わることもあります。たかだが４バイトの数字を並び替えただけでは、現実を語れません。
とは言ううものの、じゃぁ考えられるレコード構造を全部掲載するというのも無限にあるわけですから、とても書ききれません。
そこで、このサイトでは現実的に使うことが多い、４バイトのキー長と、それに続くポインタ格納域を持ったレコードを取り扱います。この仕様は使う場面が極めて多いからです。Ｃ言語の構造体だと、次のようになります。
struct SortRecStruct
{
DWORD Key;
void* Value;
};
展開されたアセンブルリストと比較しやすいよう、unsigned int ではなく、DWORD 型でキーを定義しています。たいして変わりませんが。
よくあるパターンとしては、大きなマスターレコードを直接ソートするのではなく、マスターレコードからキーの部分とそのキーがどこに格納されているのかを示すアドレス（ポインタ）を格納しておくわけです。マスターレコードの大きなサイズを並び替えるより、小さなインデックスレコードを並び替えるのはよくあることです。もしマスターレコードを並び替える事情があるのなら、インデックスレコードのソート結果に従った順番でマスターレコードを書き出せば、ソートしたことになります。このとき、もちろん入力と出力は別物になるので、名前の付け替えなどの後処理が必要になりますが。
この構造体だと、32 ビットの win32 環境ではレコード長は 4 + 4 バイトで、合計 8 バイトになります。64 ビットの x64 環境では、4 + 4 + 8 の合計 16 バイトになります。どうして 4 バイト多いのかはご自分で考えてください。
ですから、win32 では実行速度が速いのに、x64 では遅いという現象が普通に現れますが、これは転送サイズが異なるからという意味になります。ネイティブ 64 ビットの能力が著しく劣るというわけではありません。ただ、64 ビットモードは機械語の命令長も長くなり、実際に 32 ビットより遅くなるケースもちょくちょくとあるのも事実ですが。
メインプログラムからソートを呼び出す形式は、次のとおりとします。
dwStatus = xxSort( 配列トップアドレス、データの個数, アボートチェックアドレス );
まず、ソートの割には、DWORD 型の戻り値があります。エラーは３種類あって、いずれも Windows のエラーコードです。
なお、メインプログラムからの呼出し方法が、「何個ソートしてね」という形式は統一していますが、その先の内部処理で、「どこからどこまでの範囲」に置き換えているケースがほとんどです。これは、例えばクイックソートのレコード数が少なくなったときに、他のソートを呼び出すのにどの方法がよいのかを検証するため、ソースリストを使いまわせるように記述しているからです。また、処理技法によっては、高速性を生み出すために範囲指定に書き換えている場合もあります。
しかし、メインプログラムからの呼出しは、すべて同一形式とします。
あまり大きなデータをパソコンでソートすることはないと思いますが、x64 環境では大きなデータも取り扱えるよう、内部の添え字も 64 ビットで取り扱っています。これにより、32 ビット環境ではソートできない大きなデータも一応扱うことができます。
ただし実用的には、そんな巨大なデーター処理は、大型コンピューターで行った方が無理がないと思いますが。
ただパソコンでも、地図データーのシェープファイルなどは十分巨大なので、パソコン処理であっても使う場面があるかもしれません。
サンプルデータは８種類あります。
１ Random32
VC++ で、rand_s 関数を使って発生させた、32 ビット符号なし整数です。この関数は乱数らしく、毎回異なる値を発生させてくれますが、それでは比較実験になりませんから、別のプログラムで約１億３千万個の乱数を発生させ、それをファイルに書き込んであります。実験するときは、このファイルを読み込んで、先頭から何個を対象に使うということになります。
重複データーがあるのかないのか検証していませんが、たぶん、重複データーはないはずですし、あったとしても、ごく少数かと思われます。
２ Random32R
上記の Random32 と全く同じデータですが、初期の格納順序が逆になっています。
３ Random15
VC++ で、rand 関数を使って発生させた 16 ビット符号なし整数です。実際は、値の範囲は 0 から 32767 までなので、15 ビットになります。
発生する値の範囲の関係で、レコード数を多くすると重複データが必ず発生するという意味になります。
４ Random15R
上記の Random15 と全く同じデータですが、初期の格納順序が逆になっています。
５ Forward
先頭から、1、2、3 … と順番に書いています。重複データが無いという特徴があります。
６ Reverse
Forward の逆順格納です。やはり重複データが無いという特徴があります。
７ Constant
すべてのレコードが同一定数です。そんなデータが高頻度にあるとは思えませんが。
８ Med Killer
クイックソートで、メディアンキラーのデータを流して「おおっ、遅いぞ！」と喜んでいるマニアの方がおられますので、メディアンキラーのデータも用意しました。
前半は昇順データー、後半は降順データになっています。また、重複データという意味もあります。
速度の実績を掲載しているときの数値ですが、Windows の場合は 15ms 程度の誤差は普通に発生します。ですから、A と B と２つあったとき、結果の差が 15ms 程度のときは、２つは同じ速度とみなしてください。
あくまでも筆者の趣味の話ですが。
win32 では、関数を呼び出すとき、引数をスタックに積みます。x64 でも、引数の数が多いときはやはりスタックを使います。
標準の呼出し形式だと、関数から戻ってくると ADD 命令を使って引数に使ったスタックのサイズを再調整しますが、その ADD 命令を実行させる時間を省略したいという願望のため、呼出しは stdcall を使用しています。ただの、ケチな行動ですが。アセンブラ 100% のソフトでも流用しているという事情もあります。
参考までにテストプログラムで、「♪ドレミファソート」の場合を掲載します。
← Top Page ｜ Bubble 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 |