広く知られているinsertion sortのコードは駄目すぎる?

やねうらおさんによると、「広く知られているinsertion sortのコードは駄目すぎる」らしい。Wikipediaに載っているコード(2009.08.06版)を、

どこの馬鹿なアルゴリズムの教科書から引用してきたのかは知らないが、こんなものをサンプルとして掲載しないでもらいたい。

というのだから穏やかではない。

私の座右の書『コルメン』も、

一連の劣悪なコードはこいつが犯人かも知れない。

と非難されてしまっている。

実際のところ、どのくらいの性能差になるのか、実験してみた。

こんな感じ(codepad)。

C++の標準ライブラリ(std)のsortとWikipedia版、やねうらお版の比較。単位は秒。挿入ソートの2つ(つまりWikipedia版とやねうらお版)は、実行時間の比も計算した(1より小さい値はやねうらお版が速いことを意味する)。

size	repetition	std	wiki	yane	y/w
4	1048576		0.3512	0.1576	0.1333	0.8459
8	233016		0.1148	0.06757	0.07265	1.075
16	65536		0.111	0.02996	0.1191	3.976
32	20971		0.1388	0.1141	0.09537	0.836

Timeout

codepadはすぐにタイムアウトしてしまうから、ベンチマークにはちょっと使えない(そもそも、ほかにどんなプロセスが動いているかわからないし)。

手元のCore i7 940 2.93GHz、主記憶9Gのマシンで実行してみる。

GCC 4.4.2(64ビット)の場合(コンパイルオプションは「-O3」のみ)

size    repetition      std     wiki    yane    y/w
4       6291456         0.3001  0.1896  0.1957  1.032
8       1398099         0.1766  0.1374  0.1427  1.039
16      393216          0.1201  0.09756 0.09972 1.022
32      125829          0.1045  0.08267 0.08463 1.024
64      43689           0.08399 0.07897 0.08637 1.094
128     16047           0.07033 0.09022 0.1061  1.175
256     6144            0.06053 0.118   0.1466  1.243
512     2427            0.05325 0.1704  0.2192  1.287
1024    981             0.04746 0.263   0.3447  1.311
2048    405             0.04273 0.4241  0.5613  1.323
4096    168             0.03847 0.697   0.9245  1.326
8192    72              0.0356  1.187   1.582   1.333
16384   30              0.03148 1.978   2.623   1.326
32768   12              0.02696 3.157   4.208   1.333
65536   6               0.02857 6.37    8.425   1.323

配列のサイズが64くらいまでなら、std::sortを使うよりも挿入ソートのほうが速いようだ。その範囲では、Wikipedia版とやねうらお版にあまり差はない(Wikipedia版が若干速いか)。

インテルC++コンパイラ 11.0(64ビット)の場合(コンパイルオプションは「-fast」のみ)

size    repetition      std     wiki    yane    y/w
4       6291456         0.2103  0.2164  0.2285  1.056
8       1398099         0.1464  0.1455  0.1447  0.9947
16      393216          0.107   0.106   0.1072  1.011
32      125829          0.1034  0.08955 0.09303 1.039
64      43689           0.08693 0.08898 0.09369 1.053
128     16047           0.07405 0.1059  0.1113  1.051
256     6144            0.06446 0.1456  0.1503  1.032
512     2427            0.05672 0.218   0.2219  1.018
1024    981             0.05066 0.3439  0.3462  1.007
2048    405             0.04571 0.5608  0.5618  1.002
4096    168             0.04118 0.9253  0.9255  1
8192    72              0.03799 1.578   1.579   1
16384   30              0.03406 2.628   2.629   1.001
32768   12              0.02887 4.197   4.208   1.003
65536   6               0.0307  8.464   8.46    0.9995

GCCのときよりstd::sortが速くなるのが早い。サイズ64ならもうstd::sortでよいようだ。GCCの場合より、std::sortが有利になるのが少し早い。Wikipedia版とやねうらお版にあまり差はない(やはり、Wikipedia版が若干速いか)。

Visual Studio 2008(32ビット)の場合(Releaseモード。オプションはデフォルトのまま)

size    repetition      std     wiki    yane    y/w
4       6291456         0.329   0.184   0.171   0.9293
8       1398099         0.209   0.14    0.142   1.014
16      393216          0.136   0.114   0.111   0.9737
32      125829          0.105   0.1     0.098   0.98
64      43689           0.103   0.099   0.097   0.9798
128     16047           0.093   0.113   0.115   1.018
256     6144            0.083   0.141   0.155   1.099
512     2427            0.075   0.195   0.226   1.159
1024    981             0.066   0.295   0.35    1.186
2048    405             0.061   0.469   0.568   1.211
4096    168             0.057   0.77    0.937   1.217
8192    72              0.051   1.313   1.617   1.232
16384   30              0.045   2.207   2.72    1.232
32768   12              0.038   3.57    4.398   1.232
65536   6               0.04    6.966   8.513   1.222

配列サイズ64くらいまでは、挿入ソートがstd::sortより速い。その範囲では、Wikipedia版よりやねうらお版のほうが若干速いか。

いずれにしても、配列サイズが小さいなら、挿入ソートを試す価値はありそうだ。しかし、GNUやインテルのコンパイラをよく使う私には、挿入ソートの細かいチューニングは早すぎる最適化になりそうだ。

小さい配列限定のすごく速いソートなら、ソーティングネットワークはどうだろう。サイズ7の場合はこんな感じ(codepad)。batcherがソーティングネットワーク。単位は秒。codepadだと遅いか。

GCC 4.4.2(64ビット)では、ソーティングネットワークが速い。

std::sort: 0.411432
wikipedia: 0.3258
yaneurao: 0.331935
batcher: 0.28106

インテルC++コンパイラ 11.0(64ビット)の場合

std::sort: 0.324813
wikipedia: 0.331058
yaneurao: 0.298131
batcher: 0.228164

ここで使っている関数bathcersortは、CPANにあるAlgorithm::Networkで作った。次のようなコードでASCIIアートを描ける。

use Algorithm::Networksort qw(:all);
$inputs=7;
my @network = nw_comparators($inputs, algorithm => 'batcher');
print nw_graph(\@network, $inputs), "\n";
o--^--------^-----^-----------------o
   |        |     |                  
o--|--^-----|--^--v--------^--^-----o
   |  |     |  |           |  |      
o--|--|--^--v--|--^-----^--|--v-----o
   |  |  |     |  |     |  |         
o--|--|--|-----v--|--^--v--|--^--^--o
   |  |  |        |  |     |  |  |   
o--v--|--|--^-----v--|--^--v--|--v--o
      |  |  |        |  |     |      
o-----v--|--|--------v--v-----|--^--o
         |  |                 |  |   
o--------v--v-----------------v--v--o

仕組みを知りたいという向きにはKnuthの第3巻が、「サイズ7限定じゃ意味ないし、任意のサイズでできるようにしたらコンパイルできないじゃん」という向きには『LET OVER LAMBDA Edition 1.0』がおすすめ。

47561461474434133632

分散コンパイルのためのdistcc

とある事情でMySQLを何度もビルドしなければならなくなりました(『MySQLデータベース構築バイブル』を読んだからではありませんが、そういうことにしておいてもらってもいいです)。

利用できる最速のマシン(Core i7 GHz)でMySQL 5.4.3-betaをビルドするのにかかる時間は1分40秒ほどです。1回だけならいいのですが、何回もすることを考えると、少しでも早くビルドできる環境を用意しておきたくなります。

Windowsの場合は知りませんが、GNU/LinuxやMac OS Xでは、C言語とC++の分散コンパイルのためのdistccが簡単に利用できるので試してみました。

手順は以下の通りです。

  1. すべてのマシンで同じコンパイラを利用できるようにする
  2. distccのインストール
  3. 環境変数CC、CXXの設定
  4. ./configure
  5. 環境変数DISTCC_HOSTSの設定
  6. make -jジョブ数

もう少し詳しく説明します。

利用したマシンは以下の通りです(A, D, Eのネットワークは1G、それ以外は100M)。

  • A: Core i7 940 2.93GHz
  • B: Core i5 750 2.67GHz
  • C: Core2 Quad Q6600 2.4GHz
  • D: Core2 4300 1.8GHz
  • E: Athlon 64 X2 5400+
  • F: Pentium D 3GHz

クライアント側で必要なのはdistcc、サーバ側で必要なのはdistcc-serverだけなのですが、マシンをどのように利用するかが確定しているわけではないので、まとめて入れておきます。

yum install distcc*

本稿執筆時点では、パッケージで配布されているdistccのバージョンは2.18でした。Googleによって改良されたバージョン3系列のほうが、パフォーマンスはいいはずなのですが、私の環境ではそれを確認することはできませんでした。

今回利用したGCCのバージョンは4.4.2です。すべてのマシンで、同じフルパスで同じバージョンのgcc, g++を利用できるようにしておきます(binutilsも?)。その上で、クライアントで次のように環境変数を設定します。

export CC="distcc gccのフルパス"
export CXX="distcc g++のフルパス"

さらに、利用するサーバとジョブの数を設定します(クライアントはIPではなくlocalhostと書くべきです)。ジョブ数のデフォルトはIPに対しては4、localhostに対しては2なので、その場合は「/ジョブ数」は省略できます。「IPアドレス/ジョブ数,lzo」と書くとデータを圧縮するようになりますが、私の環境ではその効果は確認できませんでした。

#distcc Ver. 2の場合
export DISTCC_HOSTS="サーバ1のIP/ジョブ数 サーバ2のIP/ジョブ数 ... localhost/ジョブ数"
#distcc Ver. 3の場合
export DISTCC_POTENTIAL_HOSTS="サーバ1のIP/ジョブ数 サーバ2のIP/ジョブ数 ... localhost/ジョブ数"

すべてのサーバ用マシンで、次のようにしてサーバを起動します(受け入れるジョブの最大値を指定することもできますが、この例のように省略すると、CPU数+2になります)。サブネットは192.168.0.0/24のように指定します(毎回これを行うのが面倒なら、distccdが自動的に起動されように設定しておいてもいいでしょう)。このサーバがポート3632を利用できるようにファイアウォールを設定しておいてください(利用するポートを指定することもできます)。

distccd --daemon --allow サブネット --log-stderr

マシンBをクライアントにして、DISTCC_HOSTSを「AのIP/6 EのIP CのIP localhost」にしたときのビルド時間は1分17秒でした。マシンA単体でのビルド時間1分41秒、マシンD単体でのビルド時間6分54秒と比べると、「速くなってよかったね」という感じです。

投入するジョブの数は微妙な調整が必要です。デフォルトの「CPU数+2」が最適というわけではありません。また、明らかに遅いマシン(ここではマシンF)は入れない方がよさそうです。

Macでも試してみました。Macの開発環境にはdistccがはじめから含まれているので、準備の手間が一つ省けます。

手元のMacBook Pro (Core2 Duo 2.16GHz)単体では、ビルドに7分57秒かかりました(GCCのバージョンは4.2.1)。

MacPortsという常にソースからビルドするシステムがデファクトになっているのでとても困ったことなのですが、私のMacのビルドは遅いです(MacPortsの待ち時間は大嫌いです)。たとえば、CPUはこのMacBook Proより遅いはずのマシンD(上述)のビルド時間は6分54秒でした(ディスクの書き込み速度の差はあまり関係ないでしょう)。

このMacBook Proをクライアントに、Core2 Duo 2GHzのMacBookとMacMiniをサーバにして(DISTCC_HOSTSは「MacBookのIP MacMiniのIP」)ビルド(make -j8)した結果は5分53秒でした(localhostをDISTCC_HOSTSに追加したら遅くなりました)。

確かに速くはなりましたが、「MacPortsがすごく速くなるかも」という期待は裏切られた感じです。

もちろん、GNU/Linuxマシン上にクロスコンパイル環境を構築してサーバにすればよいというのはわかっているのですが、Appleが開発環境を微妙にいじっているせいで、クロスコンパイル環境の構築はちょっとやっかいだったりするのです(そのためのプロジェクトがあるくらいに)。

『ジェネレーティブプログラミング』『C++ Template Metaprogramming』で紹介されているテンプレート/メタプログラミングのコードを使えば、分散コンパイルのインフラ上で並列計算ができたりするわけですが、そういうネタはまた別の機会に。

追記:Cプリプロセッサメタプログラミングで、文字列系泥沼関数型プログラミングというのもすごいですね。

コールグラフを描く2つのツール(EgyptとCodeViz)

休日(でなくてもいいけれど)の読書の題材としてコンピュータ・プログラムを選んだとき、単にコードを読むだけでなく、何か図形的な補佐が欲しいと思うことがある。

オブジェクト指向の言語だとUML図が便利だが、別のパラダイムではあまり役に立たない。

たとえばC言語では、プログラムの構成要素である関数(というか手続き)の呼び出し合う関係を視覚化できると少しうれしい(「すごくうれしい」とまではいかない)。

次のようなコードがあったとする。

#include <stdio.h>

int fib(int n)
{
  if (n<3) return 1;
  return fib(n-2)+fib(n-1);
}

int main()
{
  int i;
  for (i=1; i<=10; ++i) {
    printf("fibonacci(%d) = %d\n", i, fib(i));
  }
  return 0;
}

2つの関数fibとmainの呼び出し関係は次のようになっている。

  • main→fib
  • fib→fib

このような、有向グラフをコールグラフと呼ぶ。

GNU Binutilsに含まれるgprofを使えばコールグラフを生成できるのだが、そのためには一度プログラムを実行しなければならず、得られるコールグラフも、実行時に呼び出された関数のみのものだという欠点がある。

ついでに、グラフがあればそれを描画したいというのが人情だから(グラフが大きいとあまり意味がないのだが)、下のような絵が描けるとうれしい。

というわけで、コールグラフを描画するためのツールであるEgyptとCodeVizを試す。

  • Egypt: Cのコードを解析してコールグラフを生成
  • CodeViz: CとC++のコードを解析してコールグラフを生成。パッチを当てたGCCを用意するため、導入に少し時間がかかる

準備

想定する環境はUbuntu。

共通の準備

2つのツールともグラフの描画まではやってくれない。どちらも描画はGraphVizに任せるようになっているため、まずはGraphVizをインストールする。

apt-get install graphviz

Egypt

Egyptのインストール手順は以下の通り。

wget http://www.gson.org/egypt/download/egypt-1.6.tar.gz
tar zxf egypt-1.6.tar.gz
cd egypt-1.6
perl Makefile.PL
make
sudo make install

Cygwinでは最後の「make install」で失敗した(というわけで想定環境はUbuntu)。

CodeViz

CodeVizのインストール手順は以下の通り。

wget http://www.csn.ul.ie/~mel/projects/codeviz/codeviz-1.0.11.tar.gz
tar zxf codeviz-1.0.11.tar.gz
cd codeviz-1.0.11/compilers
wget http://ftp.yz.yamagata-u.ac.jp/pub/GNU/gcc/gcc-3.4.6/gcc-3.4.6.tar.gz
cd ..
./configure --prefix=インストール先
make
sudo make install
export PATH=インストール先/gccgraph/bin:$PATH

使い方

Egypt

Egyptの使い方は以下の通り(詳しい使い方は「man egypt」)。

gcc -dr fib.c #fib.c.131r.expandができる
egypt fib.c.131r.expand > egypt.dot
dot -Tgif -Grankdir=LR egypt.dot -o egypt.gif

「-dr」はRTLを生成するためのオプション。「-Grankdir=LR」は階層を左から右に向かって描くためのオプション(デフォルトは上から下)。最後に紙に出力したいなら、「-Tps」としてPostscriptにするといいだろう。

CodeViz

CodeVizの使い方は以下の通り。

gcc fib.c #fib.c.cdepnができる
genfull #full.graphができる。詳しい使い方は「genfull --man」
dot -Tgif -Grankdir=LR full.graph -o full.gif

今読んでいるコード中にあるものだけに限定したい場合は、gengraphを使う(-fは最上位の関数を指定、–plainはdotファイルを出力するための、–no-externは外部のファイルを無視するためのオプション。詳しい使い方は「gengraph –man」)

gengraph -f main --plain --no-extern #main.plainができる。
dot -Tgif -Grankdir=LR main.plain -o main.gif

Startrek

グラフが少しでも大きくなると実用性に疑問が生じてくる。

Chris NystromさんのSuper Star Trek Classicコードで試す。このコードはBASICをそのままCに翻訳したものであるため、今日の基準では、読みやすいとは言えないだろう。それでも読みたいというときに、コールグラフが役立つはず。(Startrek自体に興味がある向きはWikipediaの記事を参照)

Egypt

CodeViz

Code Reading―オープンソースから学ぶソフトウェア開発技法 (単行本)コールグラフは扱われていないが、休日の読書のガイドにはDiomidis Spinellis『Code Reading』(毎日コミュニケーションズ, 2004)がおすすめ。(新版

プログラマの道具箱(深さ優先探索と幅優先探索) C++編

参考:数独の平凡な解法(C言語Mathematica

Mathematicaで実装した深さ優先探索と幅優先探索をC++に移植してみましょう。

深さ優先探索と幅優先探索

探索木のノードを表現する型をSTATUS、そのリストをFRINGE、FRINGEにノードを追加するメンバ関数をCOMBINERとします。

データ構造はツリーではなくリストを使います。候補ノードを、スタックで管理すれば深さ優先探索、キューで管理すれば幅優先探索になるわけですが、std::stackとstd::queueにおいて、要素を取り出すメソッド名が同じではないため多態性を利用できません。ですから、ノードはstd::listで管理し、要素はメンバ関数pop_front()で常に先頭から取り出すことにします。

要素を追加する際に、メンバ関数push_front()を使えば深さ優先探索に、push_back()を使えば幅優先探索になります。探索に使う関数search()は、引数としてこれらのメンバ関数へのポインタを取るようにしましょう。

道具箱には次のようなコードを入れておけばいいでしょう。

#include <iostream>
#include <list>

using namespace std;

typedef ... STATUS; //ノードのための型
typedef list<STATUS*> FRINGE; //ノードを管理するオブジェクトの型
typedef void (FRINGE::*COMBINER)(FRINGE::const_reference); //メンバ関数へのポインタ

//解を報告する手続き
void report(STATUS* s)
{
  ...
}

//解かどうかを判定する述語
bool goal(STATUS* s)
{
  ...
}

//探索を深める
void expand(FRINGE* fringe, STATUS* s, COMBINER combiner)
{
  ...
  STATUS* newStatus=new STATUS...
  ...
  (fringe->*combiner)(newStatus);
}

//探索の本体
void search(FRINGE* fringe, COMBINER combiner, bool findAll)
{
  if (fringe->size()!=0) {
    STATUS* s=fringe->front();
    fringe->pop_front();
    if (goal(s)) {
      report(s);
      if (!findAll) {
        while (!fringe->empty()) {
          STATUS* tmp=fringe->front();
          fringe->pop_front();
          delete tmp;
        }
      }
    }
    else expand(fringe, s, combiner);
    delete s;
    search(fringe, combiner, findAll);
  }
}

int main ()
{
  STATUS* s=new STATUS...
  ...
  FRINGE* fringeP=new FRINGE();
  fringeP->push_back(s);
  search(fringeP, &FRINGE::push_front, true); //depth-first search
  //search(fringeP, &FRINGE::push_back, true); //breadth-first search
  return 0;
}

数独を解く場合には、typedef int STATUS;でいいでしょう。関数については、実行結果を参照してください(実行する場合には、スタックサイズを大きくする必要があるかもしれません)。

コメントと空行を取り除くと、(Mathematicaの時は含めなかった)実行部分を含めて約100行です。

C++に関する必要な知識の大部分は、拙著『Microsoft Visual C++入門』にまとめてありますが、深さ優先・幅優先を指定するために必要なメンバ関数へのポインタの使い方は確認しておきましょう。

クラスFooのオブジェクトのメンバ関数へのポインタには、次のように名前(ここではBAR)を付けておくのが簡単です。

typedef 戻り値の型 (Foo::*BAR)(パラメータリスト)

Fooののメンバ関数funcへのポインタbarは、次のように取得できます。

BAR bar=&Foo::func;

次のようにして、クラスFooのオブジェクトfooのメンバ関数を、ポインタbarを使って呼び出します。

(foo->*bar)(引数リスト)

参考:プログラマの道具箱(深さ優先探索と幅優先探索) Mathematica編

関数printf()内の%lf

学生が書くC言語のプログラムに、「printf(“%lf”, x)」のような断片を見つけることがあります(ここでxはdoubleの変数)。

私:なんで%lfなの?
学生:doubleだからです。

確かにscanf系の関数では、代入先がfloatなら%f、doubleなら%lfを使います。しかし、printf系の関数の場合はそうではありません。対象がfloatでもdoubleでも%fを使います(正確に言えば、doubleには%fを使います。floatのための変換指定子はありませんが、%fを使えばfloatがdoubleにキャストされます)。

新・C言語入門 シニア編 (C言語実用マスターシリーズ) (単行本)

関数printf()の変換修飾子「l」の意味は次の通りです。

変換指定子がd、i、o、u、x、Xのとき対応する引数がlong型またはunsigned long型であることを示す。変換指定子がnのとき対応する引数がlong型へのポインタであることを示す。(『新訂新C言語入門シニア編』p.321)

変換指定子「f」に変換修飾子「l」は付かないのです。関数printf()内の%lfは、C90では未定義です。

間違って書く人が多かったためか、C99では%lfを使うことが許容されました。%fとして扱うというだけのことですが。

単純に「floatは%f、doubleは%lf」と憶えておけばよいことになったのですから、学生にとってはいい話かもしれません。しかし、こんな間違った憶え方をする前に、「どのように動いているのか」を考える癖をつけたほうがいいのではないでしょうか。

Javaでも1.5からprintfが使えるようになりましたが、”%lf”と書くと例外が発生します。

年配の先生から「使い分けなければならないハードもかつてはあった」ということを教えてもらいました。