<<20092011>>

2010-1-11[月] 安定ソートについてのメモ(sort test その5)

しつこくソートネタ.遣り残してた、というか、自分としては本題だった 安定ソート についてのメモ.

安定ソートだと、ソート対象の値が、同じ値だったときに元の順番を維持した状態でソートできる.

安定ソート としては 挿入ソートマージソートビン(バケット)ソート基数ソートバブルソート 等がある. アルゴリズムとかの詳しいことは wikipediaとか、 このへんとか、 適当に検索するなりして調べて.

今回のテストルーチンは、 マージ基数quick (y)その他のソートテスト本体 で一組.
[ソース,exe,実行結果ログのzip]

本題以外のソートも混ざってて、ごちゃごちゃしてるけれど、 本命は、マージソートと基数ソート.

マージソートは

  • 最内側(一定個数以下)のソートとして挿入ソートを使っている.
  • おそらく、汎用的な安定ソートルーチン(std::stable_sortとか)だと、
  • 数が少ないときは挿入ソート、多くなればマージソート、って感じだと思う. (追記:実際はも少しいろいろやってるかも)
  • データの個数の半分のサイズの作業メモリ(外部メモリ)が余分に必要になる.

基数ソートは

  • 速いけれど、使える局面が限られる.
    ソートキーを(符号無)整数値に変換できないといけない.
    今回のテストは基数ソートしやすいテストデータにしている.
  • 比較を単純化するため、テストデータは、負数無し(0と正数)にしている.
  • このテストルーチンでは基数ソートの基数は8bit(0~255)で扱っている.
    なので、
  • int(4bytes)だと4分割して4回処理することになるし、 double(8bytes)だと8分割して8回処理することになる.
    (分割した処理ごとに範囲チェックをしてるので、入力が0~255ですめば1回+αの処理ですみバケットソートに近くなる)
  • 浮動小数点数データについては、今時の一般的なIEEE な仕様であることを前提に、
  • ビットイメージをそのまま符号無整数値として扱っている.
  • データの個数分の作業メモリ(外部メモリ)が余分に必要になる.


実行結果

とりあえず、その実行結果としては、

 【phenom2 945 vista64 vc2008:32bit】  【phenom2 945 vista64 mingw】  【vaio-c1 win2k vc2008】  【玄箱HG debian4 gcc4.1.2】

(※他のコンパイラでの結果等はzipに同根)

いくつか抜粋してみると、(単位はμ秒)

phenom2 945(vista64)+vc2008(32bit)で int 配列をソートした場合.

個数100個1024個10000個100000個1000000個10000000個
回数(結果は平均)( 1000回)( 98回)( 10回)( 1回)( 1回)( 1回)
バブル SORT 12.4401557.466150125.77015098726.584------
挿入 SORT 3.148267.28824947.2702500147.295------
vector insert 9.242192.0699526.0991133735.433------
std::stable_sort 3.48352.740739.9829859.912119201.8821492833.656
マージ SORT 2.40342.339564.8137241.42391783.5231102430.407
基数 SORT 5.77834.457312.8893309.77837145.294406029.607
QUICK SORT(非安定) 2.10433.574439.8055471.64566066.008794235.790

phenom2 945(vista64)+vc2008(32bit)で double 配列をソートした場合.

個数100個1024個10000個100000個1000000個10000000個
回数(結果は平均)( 1000回)( 98回)( 10回)( 1回)( 1回)( 1回)
マージ SORT 3.78064.883865.57811134.446141526.0181726543.597
基数 SORT 14.11690.035841.4278860.623106789.9691096515.828
QUICK SORT(非安定) 3.68557.659750.5429295.246113065.8371363336.262

玄箱HG(PowerPC 266MHz)+gcc4.1.2で、int配列をソートした場合.

個数100個1024個10000個100000個1000000個
マージ SORT 36.000448.9807600.00096000.0001344000.000
基数 SORT 68.000285.7144400.00072000.0001024000.000
QUICK SORT(非安定) 28.000367.3475600.00064000.000836000.000


表のstd::stable_sortはコンパイラ付属のstlライブラリを使った場合. たぶんマージソート(with挿入ソート)がベースだろうと思うけれど(追記:実際はも少しいろいろやってるよう)、 実装の違いからか、ちょっと差が現れている模様. (vcのには勝ってるけど、gccのには量が多いと負ける)

quick ソートは安定ソートではないけれど、実行速度の比較のために並べている. (※実行ログでは、quick(+挿入) になっているモノ)

基本的にマージソートはクィックソートより遅くなるが、 基数ソートは条件が揃えばクィックソートよりも速くなりえる.

だいたい説明サイトの説明にあるとおりの状況、かな. (どの程度の性能差があるかを見てみたかったので今回のテスト)

ただ、基数ソートは仕組み上、ソート値のビット数が多い(値の範囲が広い)場合、処理が重くなるので、 int(4bytes)だと飛びぬけて早いのに、double(8bytes)だと微妙な差になっている.

また、phenom2(3GHz 2次cache 512KBx4 3次 6MB)環境だと、 テストで使ったデータ数やデータサイズ・CPU(キャッシュ容量)が 基数ソートに有利に働いた面もあるようで、 クィックソートよりも十分早くなれるが、 玄箱HG(PowerPC 266MHz cache:16+16KB)の場合は 1024個,10000個では速そうだけど、 それ以上ではクイックソートのほうが速くなっていて、 基数ソートが必ずしも速いというわけでない模様.


基数ソートは、個数が少ないときは、処理のオーバーヘッドが大きすぎて割にあわない. もっともクィックソートにしろマージソートにしろ、数が少ないときは実質、挿入ソートになっているので、 実際に基数ソートを使う場合も一定数以下はマージソートを使う、のようにするだろう.

ただ、他の実行環境(CPU)やソート対象のサイズ等により、効果的な境界値が大きくばらけるので、 汎用的な決めうちは、やりにくい.

基数ソートは条件揃えば倍速以上になるとはいえ、 手間を思うと、よほどのことがないかぎり、 安定ソートはマージソート、 非安定ソートでよければクィックソート、 でいいかな、というのが結論.というか、普通を再確認しただけとも.


upper_boundを用いた vector への insert

先の結果のvector insertの行は、vector<Hoge> hoge_vec; でデータを保持しているとき、

hoge_vec.insert(std::upper_bound(hoge_vec.begin(),hoge_vec.end(), val), val);

のような感じに安定ソート状態を維持したまま新規の値 val を挿入するもの.

テストルーチンでは、他のソートと関数仕様あわせたため、(実使用からすれば) 余分なアロケート時間やコピー時間が混ざっていて、 他のソートと比較するのにはフェアな状態ではない.

が、回数に対する時間の増え方からすれば、効率はあまりよくないだろう.

これを用いるメリットは、

  • データ追加の機会がまばらにあって、かつ、絶えず整列状態を維持しないといけないとき
  • 余分な作業メモリ(外部メモリ)を必要としない

といったところか.

作業メモリについては、挿入ソートも作業メモリ不要なので、追加回数しだい... どちらにしても、量が多いときの速度ペナルティが大きいので、数があるときは メモリの折り合いつけてマージソートとかを使うほうがよいだろうけど.


しかし、余分に作業メモリ(外部メモリ)が必要になる、というのは、 場合(ターゲット環境)によっては面倒かもしれない.
というか、std::stable_sort で勝手にアロケータを使われること、 が環境によってはつらかった.

なので、最大数わかってる場合に固定の作業メモリを与えられるマージソート・ルーチンがほしい、というのが、今回のテストルーチン作成の理由のひとつ(実際に使う機会があるかは別として)

あと、後述のSmpClassの例からすると登録順番も保持し比較対象にすることでクィックソート(std::sort)を用いるというのも、動的アロケート回避、という意味では有りな選択かもしれない.


※ 基数ソートで、符号無し整数として比較を行っているけど、他のソートは 型どおりに行っている.
当然、条件を満たした状態だから、他のソートでも符号無し整数で比較することは可能なので、 そのように比較すれば、他のソートもも少し早くなるはず. (面倒だからやりなおさないけど)

Class/Structのソート

テストルーチンで、SmpClass を使ったものについて.
(前回のスマートポインタのソートの補足というか書き漏れ)

[1] SmpClass1           [2] SmpClass2          [3] SmpClass3
8バイトの構造体.        SmpClass3へのポインタ  128バイトの構造体.
class {                 (4バイト)              class {
    float    key_;      ※比較はSmpClass3の        float    key_;
    unsigned no_;         ものを使う               unsigned no_;
};                                                 unsigned rsv_[30];
                                               };

のようなデータのソートを行ってみる.
[1]については、テストの都合unsigned no_ になっているが

class {
    float  key_;
    Hoge*  pHoge_;
};

のようなソートキーと実体へのポインタの組み合わせ、を想定している.
(面倒なので話を32bit環境に限定)

また、quickソートにおいて、登録順も比較対象にすることで[1]と同様の安定ソートを実現するため

[4] SmpClass4
12バイトの構造体
class {
    flaot    key_;     // 比較対象
    unsigned no_;      // 比較対象
    unsigned rsv_[1];  // Hoge* pHoge;のようなのを想定.
};

も用意.
これらのデータをソートした結果は(phenom2 945 vc2008環境)

10000個の場合 (単位:μ秒)

[1](8bytes)[2](ポインタ)[3](128bytes)[4](12bytes)
マージ SORT 1188.4891362.14213398.148---
基数 SORT 364.0762304.5256199.210---
QUICK SORT 893.4451171.8676468.636954.360

100000個の場合 (単位:μ秒)

[1](8bytes)[2](ポインタ)[3](128bytes)[4](12bytes)
マージ SORT 15242.09124420.003179135.267---
基数 SORT 4175.60147205.162107197.703---
QUICK SORT 10910.04626117.91473457.52011795.913

のような感じ.

[1]の場合はソート対象のコピー量は増えるけれど比較コストは増えない. [2]のようにポインタだけの場合はコピー量は最小になるけれど メモリにあるポインタを経由して比較用のキーにアクセスするため 比較時間(コスト)が増加する. で、CPUキャッシュ等の都合から、今時の環境だと[1]のほうが有利なことが多そう.

なので、[1]のようにできるならば、そうしたほうが構造体等のソートは 速くなると思われる.
(実体の並べ替えが必要な場合は、まずポインタをベースにこれでソートしておいて、 その結果を元に(作業メモリ使って)コピーし直しても元が取れそう)

で、どうせ、ソート用のテーブルを作るならば、登録順番も控えることで クィックソートを使えるようにするのも一考.

ソート対象が8バイトから12バイトに増えるが、 マージソートや基数ソートは 余分に外部メモリを必要とするので、 メモリ使用量的には同等か有利ということになる. (マージソートだと総数の半分、基数ソートだと総数分)

今回の例では、基数ソートに対しては全くだけれど、マージソートと比べるとよい結果となっている. もっとも[4]はIEEEなfloatの正数であることを前提にキーと登録順を合わせた64bit整数にして 比較を軽くしているので、このように出来ず比較コストが上がると、また違う結果になるだろう.

(今回の場合マージソート側は floatのまま比較しているのでフェアでないかも.試しにキーをビットイメージのunsiged値にしたところ[1]の結果は10000回1170.596μ秒, 100000回13034.268μ秒. 多少縮むが、一応上記を書き換える必要はなさそ)


バケット(ビン)ソート

基数ソート以上に利用条件厳しいけれど、条件があえばバケット(ビン)ソートのほうが当然速い. で、一応、用意してみた(これ)
といっても工夫してないので整数のみの対応.

基数ソートのようにgetkeyを与えられるようにすればいいのだけれど、 ただ、基数ソート・ルーチンは、 入力の値がすべて0~255までなら1回+αで処理打ち切ることになりビンソートに近い状態になるので (多少オーバーヘッドが多いけれど)、 その結果をみれば大体の雰囲気はつかめると思う.

ということで、乱数の値を0~255にして試した結果は、コレ
…他のテスト(SmpClass)は整数型にしてなかったので、結局intテストしか意味がなかった.

抜粋すると、

100個1024個10000個100000個1000000個
QUICK SORT 2.11032.696359.9203716.04540616.405
マージ SORT 2.43342.029497.8855679.42366518.720
基数 SORT 2.08911.584106.1381293.11114738.046
BACKET SORT 1.8459.29981.253859.95611884.890

のような感じ.場合によっちゃ、やっぱりバケットソート専用も意味あるかな.

その他諸々

当然、それなりに測定誤差がある.
細かい数値ままにしてるけれど、上位1,2桁ぐらいの感覚でみるのがよさそう.

前回以降にCPUを換装してしまい、今回分と前回分を単純に比較できなくなってしまったので、 テストでは、安定ソートだけでなく、前回試した他のソートもいくつか試している.
ついでに前回やりそこねてた シェルソートも追加(思ったより速い処理だった).
std::vectorと同様に無理やり multisetに挿入した場合も追加 (安定なわけじゃないし、ソートとしてはやっぱり遅いけれど)

前回のテストでは、quick_sortのtemplate版が内部でイテレータのアドレス比較してて 実質、配列のソートにしか対応してなかった. で、オフセット値を用いて修正してみると、 Bidi版と大差なくなってしまった. 厳密にはBidi版のほうがまだ1変数多くなるので、比較処理によっては差がありえるけど、 これくらいなら利便のほう優先して、今回のテストのquickソートは前回のBidi版をベースにした.
(けど、classのソート等で、一旦、ポインタを集める場合は配列になるだろうで、 それなら配列版のほうがよいという考えも)

前回の結論に基づき、quickソート内部の挿入ソートを Bidirectional Iterator を 受け付ける形でやねう版にしてみたはいいけど、性能出なかった. よくよく考えれば、 やねう版挿入ソートは、無駄な代入を減らせる可能性が高まる代わりに、比較回数が1回増えてる. 比較処理がコピーよりも十分にコストが安いことが前提なわけで、 比較のコストが高くなる場合は当然不利だ. ただ、元のソースは、ループで1回無駄に比較をしている状態でもあるので、その1回分の比較を 回避することで改善した...が、ソースが結構酷い状態に.
改善できたといっても普通のとどっこいどっこいな結果だったので、 結局、マージソートともども、普通のを用いることにした.

基数ソートルーチンは、実は dmc でコンパイルすると int 版の結果が不正になってしまっていた. こちらのバグかもしれないけれど、深く追求せず. 他にも玄箱でTYPE_SMPCLASS=4でコンパイルするといくつかのソートで実行結果が不正になるが、これも放置.

このテストのクィックソート等再帰を用いた処理は当たり所が悪いとスタック溢れがあるよう. (乱数を0~255にしたら駄目なモノがあった... 個数減らして回避. 追記:下記に修正版)

open watcom c++ (v1.8)の場合、std::stable_sort, std::upper_bound が未実装だった. 辻褄あわせして通したけれど、他にもテンプレートの特殊化ができなかったり、と、 まだ使うにはつらい感じ.

今回linux環境で使ったタイマーはwinに比べての精度がよくなさそう(4ミリ秒単位くらい?). ただ、他のプロセスの時間を含まない値なので、そういう面では楽かも.

追記

実際のstl(stlport)のものをみると std::sortやstd::stable_sortはも少しいろいろ工夫してるよう. (std::sortは、イントロソート等工夫してるらしく)
(もちっと、ちゃんと調べてから書くんだったと後悔...)

このテストのquick sort は、中間値のコピーをローカル変数にとるため値のサイズが大きいと再帰中のスタック消費がはげしくなってしまっていた.
(merge_sort 同様に)再帰関数から該当部分を関数分離してスタック消費をおさてみたのがこれ
一応上記で溢れた件は大丈夫になったが、実使用で気になる差ではないけれど、やっぱり計測上は若干遅くなった.
まあ、これをしても量と当たり所が悪いと溢れるだろうで、スタックのこと思えば素直にstlを使う、と.




2010-1-26[火] xorshift乱数のメモ

XorShift乱数は、こちらとかのように短い関数で紹介されるけれど、たいていシード固定で書かれていて、シードを外部から与えたい場合はどうしたら、と悩んでしまう. もちろん、ちょっとぐぐったらシード設定できるソース載せてるサイトあるし、 おおもとのpaper に all 0でなければよいようなことかいてあるようだけど、 どの程度適当でよいのか不安にもなる. で、今さらながら2chの擬似乱数2 をみたら76に解説&seed設定付ソースがあった. シードは極端な設定をすると不自然な部分列が出力されるからMTのを参考にしたとある. ありがたく、これ流用させていただくことに... と、よくよくみれば、ここの初期化とほぼ同じ(改良版)のよう.

その他、検索したときのサイトメモ.

mt-lite実行速度に xorshiftを含む各種乱数の速度比較あり.

良い乱数・悪い乱数に XorShiftと他の乱数との速度比較とかSSE2使ったバージョンとかがある. 同サイトの こちらにもいろいろなコンパイラでの測定比較あり.

xorshift.pdf 上記サイトで、"問題があると書かれている" とあったのでみた(翻訳ソフトでわからないなりに). 元のpaperより突っ込んだ性能テストをして、通過しないテストがいくつか(も)あるよう. (XorShiftは3つのシフト数の有効な値の組み合わせがいくつか(も)あるけれど、 組み合わせによって性能にばらつきがあるよう) あと改良版として256ビット版が載ってる. (周期のビット数だけでなく、計算でのシフト数も増やして精度をあげている)

XorShift乱数の速度

擬似乱数2の 42 に 周期 32,64,96,128,160,192 ビット版のソースがあったので、 ちょっと速度比較してみた.

ソースは コレコレコレ. (zip)

96ビット版が要修正だったり64ビット版は出力も64ビットだったり だったので 結局 paper みて修正. あと、xorshift.pdfの256ビット版追加. (シード設定可のクラスにしたりでエンバク不安あり. 64,96,160版はA,B,Cの選択がこれでよいのか自信なし).
で paper の160のソース、>>Aになっているけど <<Aの誤記だと思われる. 他と比べてもだし、別のチェックで結果がメタメタになった.

結果は以下. 環境は基本Phenom2 3GHz (玄箱HGは PowerPC 266MHz).
100000000回実行の平均. 単位:ナノ秒.

 vc9
(32bit)
vc9
(64bit)
mingw
g++3.4.5
mingw
g++ 4.4.0
dmc8.51owc 1.8bcc 5.8.2玄箱HG
g++4.1.2
XorShift 32 3.4112.6623.3292.99710.4803.3555.01023.100
XorShift 64 2.0162.1671.8421.9965.1593.0003.73434.700
XorShift 96 2.3354.3451.6672.0415.7733.0233.51238.500
XorShift 128 2.3313.9632.4191.9955.4443.2303.68546.200
XorShift 160 2.3344.2062.3382.0266.2313.0023.18746.200
XorShift 192 2.5843.8742.8762.3368.1153.1573.56646.200
XorShift 256 7.3976.2646.3276.49117.2246.1847.197134.800
線形合同法の乱数 1.5091.3361.6645.7843.5811.3293.15423.200
clib rand 18.55914.17415.08014.7206.5345.2363.231461.900
MT Rand 5.4525.6797.9965.86931.2999.2898.280127.200

下3つは比較用. MT乱数(mt19937ar-cok.c)と 線形合同法を使った乱数とC標準ライブラリのrand()を使ったもの.

コンパイラごとに癖はあるけれど、大筋は似た傾向.

paperの例では1.8GHzで4~6ナノ秒とあったので、 3GHzの環境(vcやg++)で 2~4ナノ秒は、そんなものかもしれない.
なお、これら(の速い値)はインライン展開されている(はず). 関数呼び出しになっている場合は、(vcにて) 3~6ナノ秒台だった (テストルーチンで乱数をファンクタにせずワンクッション関数を噛ましてたとき)

全体に周期32ビット版は他より遅くなっているのは、たぶん(アウトオブオーダーとかのレベルの)命令の並列化ができないためだろうか.

速度的には、 大筋ビット数が増えれば遅くなるけれど、32-192の範囲では 増える周期(質の改善)に比べ時間の増加はさほどでもないので、 どうせなら128でなく160や192あたりを使うのも手かもしれない.

256ビット版はプログラムが少々複雑になっているせいか 時間増加のよう. 128ビット版にくらべ2~3倍... MTと対して変わらない速度(場合によっては負ける)なので出番はないだろう.

でinline展開で速いのはいいけれど、 ビット数が大きいほど(ささやかとはいえ)コードサイズが膨れやすくなるので、 乱数の質が高くなくていいなら、ビット数少ないのを選ぶのもよいかもしれない.
でも線形合同法でいいなら、(inline展開されたら)そっちのほうが速いか.

サイズきになるならinlineしない形に書いて160,192あたりを... もっとも、このソースの64,96,160(,192)は使ったパラメータがほんとにこれがいいのかわかっていないので 結局 128 を選んでおくのがベターな気はする.


あと、XorShiftの件とはずれるが、vcやg++でのcライブラリの rand()の速度が遅いのは、 マルチスレッド対応のオーバーヘッドのためだろうか. インライン展開された線形合同法の乱数の10倍前後なのは ペナルティが大きいとも、10数ナノ程度ならば大抵たいしたことないとも、どちらとも. 結局使用量/使用箇所しだい、だけれど、どっちにしろ精度のことを思えば、 とっとと XorShiftなりMTなり用意して用途別にインスタンスを管理したほうが、 楽になれると思う.

(参考サイトにある SIMD版のSFMTとかが使える環境なら, そっちのほうがいいだろうな)


追記

乱数の精度の評価についてはさっぱりなんですが (自分が使った処理において出目に不都合があるかどうかくらいなら、ともかく)、 同根のtest2をしたときの結果はあまりよいという感じではなかった.(この場合のテストとして適切かどうかもわかってないけど)

まあ、たいていの場合の乱数の利用頻度や精度を思うと 普通は MT を選んどくのが無難だと思う.

この程度の速度差(時間差)やプログラムサイズ差が ネックになるような利用頻度(仕様)やターゲット環境なんて ゲームでもまずないだろうし.
どちらかというとライブラリ化でのオーバーヘッドのほうが 気になる可能性があるかも. (この程度のサイズのルーチンなんだから、わざわざメーカー提供のライブラリ使わなくてもいいよね、とか)




2010-2-4[木] sprintf,string,stream のメモ.

去年だか一昨年ぐらいから、もうそこそこパワーあるのだから、と、 ターゲット環境でc++で string 系を使ってたのだけど、 そのとき不精して、デバッグログでも使い始めたら やたら処理落ちする箇所の原因になってしまったことがある.

ログといっても シリアル とか USB とか LAN とか経由しない、 数十KBのメモリに溜め込むだけの処理だったんで、 開発中は release コンパイルでも有効にしていて、 多少重くなるといってもI/Oからまないから大事ないと思って 見過ごしてしまっていたのだった. たしかに想定してた使用量を超えたルートができていたけれど、 それ以上に酷い重さに化けていた.

もちろんログをとってることが問題ではなくて、 string系の文字列をつかって記述で楽して

dbgmsg = strFmt("%s (%d) :",fname,line) + msg + '(' + a + ")\n";

のような感じに + 等使って、テンポラリ変数発生、メモリーアロケート発生、 が山ほど起きていたのが敗因. (↑は今適当に書いたので実際のじゃない)

文字列専用にアロケータ用意してフラグメンテーション対策はほどこして いたけど、当然速度的にはよろしいもんじゃなく. わかってみればあたり前だけど、思い込んだら、でなかなか気づけなかった.

そのときは、デバッグログからstring系一層してsprintf系で やりすごしたのだけど、 たとえば + でなく += を使えばテンポラリ無くなり アロケート頻度は落ちるし、 キャパシティをある程度コントロールしてアロケート発生させなければ、 書式なしの文字列連結ならsprintfより速くなる 可能性だってあるはず.

文字列連結を一個一個指定することになって記述が面倒だけど ... iostream系の << なんかはやってること的には += と似たようなものの はずなんだよね.

などと思うと、stream関係って、実は速度的に 悪いもんじゃないかも、って気がしてきたのだった.

て、ことで、例のごとく、ちょっと計測してみた.


test1:

    sprintf(buf, "%s(%d) : test> %s", fname, line, msg);

sprintf だとこんな感じになる処理を、ポインタ操作+mem系, str系, std::string, stringstream, strstream, カスタムstream 等で書いて計測.
表示ルーチンぽくしているが、計測では表示しないので、文字列生成が主な時間.

ソースはこれ, これ, これ

数値→文字列化を持っていない処理では、ltoaを用いて文字列化している.

CharAryStream は、固定サイズのchar配列に結果を書き込むだけにしたカスタムstreambufを使ったもの.
strstreamとほぼ同じだが、その存在を失念していた.で、気づいて計測しなおしたが、vc9付属のはバグがあるようなので、CharAryStreamも残してるしだい(endsの件もあるし).

string, stringstream, CharAryStream では、ローカル変数として関数内に持つ場合と、static変数にして、初期化を一度きりにしたものを試してる.
stringの場合はローカルでの使い方が普通だろうが、streamに関しては static かはともかく、まとまった出力をしている間は1つのインスタンスをずっと使いまわすようなコードになると思うので.

ということで、phenom2 3GHz環境で、vc9 と mingw g++4.4.0 での結果.
100000回の平均. 単位:μ秒.

  vc9[A]vc9[B]mingw[A]mingw[B]
sprintf 0.5401.1710.5071.036
ポインタ操作+memcpy+strlen 0.0580.2130.0740.221
strcpy+strcat 0.0870.3670.0830.298
std::stringで'+'使用 0.7272.0330.9641.270
std::stringで領域予約で'+=' 0.3390.4860.4100.544
std::string↑の変数をstatic化 0.2060.3470.1220.278
stringstreamローカル変数 2.2153.1002.1232.141
stringstream static変数 1.4602.2670.7740.852
strstreamローカル変数 1.8912.3611.3491.400
strstream static変数 0.530---0.3460.408
CharAryStream ローカル変数 1.8622.1990.9841.047
CharAryStream static変数 1.0111.3940.2860.342

[A][B] は、test_sprintfに与える引数の文字列長の違い. 文字列長が違うと、差のありようもかわるので. (一例の結果だけみて、何倍の差があるとか早とちりしないように:)

やっぱり、ポインタ活用や、strcatを用いたものはそこそこ早く. アロケートの(ほぼ?)発生しない stringの '+=' やstream系の<<も まあ早く.
(てか g++ の strstream や CharAryStream の速度ならば、 もう Cできりきりに書かなくていいやん、と)

stringstream も、多少気になるかもだが(毎度ローカル変数生成のような)下手な 書き方さえしなければ、悪い速度じゃなさそう. (VCの stream 実装がいまいちぽいが)

というか、そもそも printf 系の処理はそんな速いものでもなく...


あと、vcでの strstream は [B]の段階で[A]の文字列のままだった. seekp(0,ios::beg)が効いていない模様. 仕様把握してないので言い切れるか微妙かもだが、バグだろう. 速度的には、自前のCharAryStream と大差ないし、 strstreamを追求したいわけじゃないので放置.


test2 : 浮動小数点数を使ってみる

sprintf(buf, "%s(%d) : test (%7.5f,%7.5f)%c %s"
           , fname, line, d1, d1, ch1, msg);

s_stringstream << fname << '(' << line << ") : test (" 
               << d1 << ',' << d1 << ')' << ch1 << ' ' << msg;

double を使ってみた例. ↑で%7.5fにしてるのはstreamでのデフォルトに合わせるため.
面倒なんで sprintf, CharAryStream, stringstreamだけ、だが、vcのstlの出来がいまいちっぽいのでSTLport(5.2.1)もためしてみた.

ソースはこれ

で結果( 100000回の平均. 単位:μ秒 )

 vc9mingwvc9+STLport
sprintf 2.5832.0622.460
CharAryStream 5.0474.1222.164
stringstream 5.8463.9952.553

vc,mingwとも stringstreamがsprintfの倍くらいにばけてる. test1の結果からすると、必要以上にオーバーヘッドがある気分.
stringstream のかわりに CharAryStream(strstream) を使うのは 若干の固定費削減って感じで劇的は無し、というとこか.

で、STLport版、sprintfと大差なく... なんか速い.
仕様のオーバーヘッドじゃなくて実装の差、てことになる、か.

細かいことはあとにして、とりあえず、次.

test3 : 幅指定等

sprintf(buf, "%-24s(%10d) : test %#016llx\n", fname, line, val);

s_stringstream << setw(24) << left << fname << right
               << '(' << setw(10) << line
               << ") : test "
               << setfill('0') << setw(16) << hex << showbase << val
               << '\n';

真打:-)
printf系で楽に書ける書式が、どうしようもなく面倒になることがstream系を使いたくない 大きな理由だけれど、まあ stream への愚痴は後回しで、

ソースはこれ

で結果(100000回の平均. 単位:μ秒).

  vc9mingwvc9+STLport
sprintf 1.2351.1991.183
CharAryStream 2.1580.5290.647
stringstream 2.9391.4741.105

stream、記述のゴツさに、つい比例してしまいそうな印象をもってしまうが、 書式解析がコンパイル時の型チェックでまかなわれているため、 sprintfより速くなる、可能性がある ... vc標準は無視、したいなぁ:)

stringstreamは STLport が がんばっている、って、ことだろうけど.
(string側の出来もいいってことかな?)


test1改 : アロケート頻度.

test1 において、お手軽な範囲で、無理やり、include関係での malloc や new を乗っ取って、使用数を計測してみた. (ソースこれ追加)

ライブラリ.lib 部分になっているのは手がだせてないので、不正確すぎて、判断するには危険だが、大雑把な目安にはなるかも、で.

といっても、ヘッダのみなんで、vcは値でたけど、mingwはひっかからず.

以下vcでの1回表示のときの、表示部分でのmalloc:freeの呼び出し数.

  [A]malloc:free[B]malloc:free
std::stringで'+'使用 2:211:11
std::stringで領域予約で'+=' 1:11:1
std::string↑の変数をstatic化 0:00:0
stringstreamローカル変数 14:68:8
stringstream static変数 3:25:5
CharAryStream ローカル変数 3:33:3
CharAryStream static変数 0:00:0

vc の string 処理は 16バイトまでならstring内にバッファがあるため、 文字列長でアロケート回数が変わる.

stringstream の[A](初回)の値が多かったりfree数が合わないのは、 ライブラリ側の処理とか、あと、バッファ以外にも、 stream処理のサブクラス等の初回生成が含まれているためだろうか.

処理順の都合、stringstreamでアロケートされているけど、 CharAryStream, stringstreamの順に計測すると、CharAryStream側の 回数増えたりするので、可能なものは共通化されてるよう.

で、stringと CharAryStream のstatic変数版が 0回になっているので アロケートを極力回避しようと思えばできる、って感じ.
(面倒なんで表にしてないけれど、double使った test2 でも 0回)

stringstream は、static版でも アロケートが発生しているので、 vc版の測定結果が遅い原因だろう.

逆にいえば、g++や STLportのものは、メモリーアロケート発生させてない、 ということでよいか.


test1 追加 : WTL::CString, STLportのstd::string, の追試

やっぱり STLportのstd::stringが気になったので、test1の追試. ついでに WTL::CString の結果も. (test1書き直し面倒なんで... vc9,mingwの測定値が若干違うのも面倒で)

STLportは v5.2.1 (staticリンク), WTLは8.1のもの.

  vc9[A]vc9[B]mingw[A]mingw[B]vc+stlp[A]vc+stlp[B]
std::stringで'+'使用 1.1761.9930.9651.1970.3260.907
std::stringで領域予約で'+=' 0.4940.4400.4120.5480.2810.480
std::string↑の変数をstatic化 0.1710.3310.1260.2900.1270.355
WTL::CStringで+使用 0.8080.946----
WTL::CStringで+=使用 0.3240.463----
WTL::CString Format使用 0.8751.314----

STLport std::string の '+' での結果がこれって、何だ? って感じだ.

STLportはメモリー確保関係工夫してるようなことどっかに書いてあったと思うけど、 いいなあ.


WTL::CString は ある意味順当かな. std::string のシガラミないし設計の方向性が違い (1core環境じゃ)軽めの処理だろうで. (参照カウンタのわりと素直?な実装だし)

static 変数版を試してないのは実装的にメリットないからだけど、 かわりに Format メンバーを使ったものを併記.
Format()の実装はソースみると自前でprintf系実装しているのではなく、 ラッパー. メモリー確保のために、そこそこformat解析してサイズを求めているので、 速度的には確実に sprintf より遅くなるのだけど.(使い勝手のものだから).


結、というか、雑感

たったこれだけのお試しで結論するのも不味いという気もなくはないし、 使い慣れてない iostream系は何かぽかってないか不安もあるけど、 とりあえず.

iostream系は、それだけなら速度パフォーマンスのそう悪い仕組みでない、といったところか.
併用される他の要因で結果的に遅くなりやすいかも、だけど.

でも、実装は工夫が必要なんだろう. vcやg++のものが工夫が足りてない、というより、 STLport ががんばっているんだろうし.

stream よりも string のほうが速度ペナルティが多くなりそうだ. += じゃなくて + で楽したいんだし.

少なくとも string 使ってる奴が速度パフォーマンスを理由に stream系にケチをつけちゃいけないだろう(自戒:)

ただ stringstream は 無様に思えてきた.

strstream は完全に捨て去る必要ないよなあ、で.
strstream は ends の手間が嫌らしいだけで、 str()時、あるいはc_str()なりを新設して、取り出し時に '\0'を付加する モードさえあれば、かなり状況改善されてたんじゃなかろうか. 原理主義的な人たちは滅ぼしたい代物だろうけど、 C文字列を無視できない人間に stream 系売り込むにはベターな存在だったのかも.

vc標準の奴の性能があれなんで躊躇しちゃうけど、 速度を気にするならstrstream(かその代用品)使うのも手かも、と.
※test2,test3はコンストラクタを追い出した状態の結果なので、 コンストラクタの頻度があがるとtest1でのローカル変数版の結果に近づく わけだから気をつける必要はある.


printf系は速くないってのを再認識かな.
書式解析やargvな処理を思うと原理的に... 実装の差もあるだろうけど (大昔のbc遅い実装だった覚えが). 今回は vc, mingw ともprintf系は MS の実装が使われてるはずなので 違うsprintfだとまた違う印象になった可能性もあるだろう.

まあ速くないといっても、この程度の差で困ることは今時まず無いので 気にしないか. (printf系の使用を避けて速度アップを実感できたのは8bit,16bit機時代くらいか).

今回の結果はまさに50歩100歩といったところだし.
ただ、メモリーアロケートの発生をさけた結果なので、 それが頻発する状態はやっぱり気にしたほうがいいとは思う.

デバッグ処理で極力メモリーアロケートなんて起きて欲しくないわけだし.

もちろん、printf系だって全くメモリーアロケートしないかというと 実装しだいだし書式によってはありえるのだけれど. ただ通常極力しないように作られてるし、 デバッグで通常出す程度ならまず起きないし、で.


あと今回は文字列処理をメインにしてたから、ためせてないけれど、 コンソール出力等でiostream系が遅くなる(かもしれない)要因の一つは endl 時にバッファフラッシュの動作が含まれていることだと思う. これも今時のPCでは気にするほどのこともないだろうけど. でも、'\n'と endl を意図的に使い分ける意味もある、ってのは 忘れずに、と.



今回のソース関係のzip : [download]





2010-2-5[金] Win環境でのSTLport 5.2.1のインストールのメモ.

前回の試しで、STLportの結果がよさげだったので VC以外のコンパイラでも試してみたくなり、とりあえず dmc 用を インストールしてみようとしたのだけどハマった。

VC用はググればインストール例あるし configure.bat --help やって、指示通りにすればできるようで一番お手軽だった模様.

まあ付属ドキュメント読まずに適当にやるでは不味かった. 読めば書いてた. でも英語なんで翻訳ソフトでちまちま... 悔しいので適当に気になるところだけ訳ぽくしてみた (わからないところを雰囲気で適当にしてたりするので、ちゃんと元のを参照のこと)
README.windows, README.msvc, README.mingw, README.dmc, build_system.txt,
(最近の修正が反映されてない文章もままあるので注意)

ようは、mingw,dmc,bcc 用を作る場合は、Msys 環境が必要. またmsys版でなくMingw32版のgnu make が必要そう. →dmc,bccが目的でもmingw入れちまうが吉かも.

  • コマンドライン版コンパイラが使えるコンソール窓を用意.
  • msys環境(sh)環境へ遷移(msysフォルダ下のmsys.bat実行)
  • STLport-5.2.1を展開したフォルダ直下の configue 実行
  • build/lib フォルダ下で ming32-make 実行. (できたライブラリを STLport-5.2.1/libへコピー)
  • build/test/unit フォルダ下でming32-make実行.
  • build/bin のテストexeを実行.
  • stlportを使うコンパイラ環境の設定.

て感じか.

以下、作業メモ. ただし、あまりうまくいってません。


※watcom c++ 用の build 環境は用意されていない模様.
(古い記述からするとターゲット名vc6で出来そうに思えたけど結局駄目だった)
※追記: openwatcom の wiki で stlport 5.1.5 のコンパイル済みのモノが実験物として置かれている模様. (ただ dll版のみの様)

http://www.openwatcom.com/index.php/User:Cmeerw


※2013-05追記: やり残し感を成仏させるため今更ながら コッチ で watcom , dmc 向けの修正をしてみました。

mingw,dmc,bcc共通

といいつつ基本 dmc しか作業できてないので...

configue実行だけど、MSys環境で

configure --use-compiler-family=???

な感じで ??? に gcc, dmc, bcc を設定.('='も忘れずに、と). 必要に応じてその他オプションも併記して.

configureやったあとに build/lib/ で

mingw32-make -f ???.mak clean
mingw32-make -f ???.mak depend
mingw32-make -f ???.mak ターゲット名

のような感じでメイク.
(bccの場合はmakeのほうがよい? 少なくともcleanは mingw32-make でエラーでて make を使えばokだた)

ターゲット名で install を指定すればallコンパイル&libへのコピーだが、dmcではエラー. また、all は dll(shared)版しかコンパイルしないようなので、結局自分の必要なものを 指定するのが無難そう. (このへんコンパイラごとに事情が違う)

mingw32-make -f ???.mak release-static dbg-static stldbl-static

な感じに、必要なものを列挙してメイク(指定できるものはコンパイラごとに事情が違う).
できた obj/???/*.lib を STLport-5.2.1/lib/ とかにコピー.


あと、テストのコンパイルだけど、日本語環境だとソース中のフランス語文字が壊れたSJIS扱いで怒られるかもで、

ctype_facets_test.cpp 430 付近の'で囲まれた文字を'\xE7'に書き換え

ておく(怒られたのは vc だっけ)

build/test/unit/ に移って

mingw32-make -f ???.mak

で、STLport-5.2.1/bin/にテストプログラム生成、 できた exeを全て実行、出力でエラーがなければok ...なんだが、 エラーでてるかも. ロケール関係ぽいので、とりあえず、あきらめ.


stlportのヘッダや出来たlibを利用するる場合は、 各IDEやコンパイラごとの環境設定するなり、 makefileやプロジェクトファイルごとに設定するなり.


適当に端折ってるので、不味かったらいろいろ試す、で.
ちゃんと使う場合は、configure時のオプションや、 ソースのconfigヘッダ等で、いくつか環境にあわせた設定をしたほうがそさそうです.
(テスト試すところまでで、力尽きた)

dmc

dmcは、ビルドする前に、 dm/bin/ にある link.exe, lib.exe をコピーして
dm_link.exe, dm_lib.exe
を作り、pathの通ったところにおいておく必要がある.

また、makefile の修正が若干必要かもで、
build/makefile/gmake/dmc.mak 111行付近の -p128 を書き換えて

release-static : AR += -p256

のようにする. (256は適当にえらんだ. これでもおこられるならさらに大きくか)

リンク時に文字化けした警告がでてるのが気になるが、libできてるようなんで 気にしないでおく.

ただコンパイル途中で

nbytes=65664, ph_maxsize = 65520
Internal error: ph 1854

なんてエラーがでるかもだが... 出たらあきらめ orz
(-HPでおおきな値設定しても駄目だった)
test/unit でのメイクの hashテストか何かで発生した.
ので、test/unit未確認.

stldbg-shared のコンパイルでも出るかもだが、 dll版は興味ないので放置した (先に static 版のコンパイルをしてあると コンパイル通ったかもだが、それでいいのかで)


コンパイル環境の設定については、dm/bin/sc.ini の INCLUDE,LIBの先頭に

INCLUDE=c:\STLport-5.2.1\stlport;…元の文字列…
LIB=c:\STLport-5.2.1\lib;…元の文字列…

みたいな感じに追記するのも手.
(CD版の dmc の場合、DMが配布している4.5.? の stlport が入っているかもだが、 バージョン違ってファイル名等微妙に違うので、下手に上書き等はしないのが無難)

あるいは、己は、元のと新規とを使いわけたいので 元のsc.iniでは行末に置かれていた %INCLUDE%と%LIB%を先頭にもってきて

INCLUDE=%INCLUDE%;…その他の元の文字列…
LIB=%LIB%;…その他の元の文字列…

のようにして、コンパイラ環境設定のバッチで INCLUDE,LIBの設定を切り替えるようにしてみた.


で、とりあえずいけるはずなんだが... 試しにコンパイルしてみたら .lib が見つからないと怒られた. リンク時の引数で stlport_static.lib とかを指定したらとりあえずリンクできたが、 自動リンクされなかった. ヘッダみるかぎり.libは自動リンクされるはずなんだが. なにか設定抜けてそうだが未調査.

mingw

とりあえず上記でstatic版のみ作れた. dll版は、 リンクエラーがでたので放置. (使ったmingw環境の設定等があわなかったのか?)

test/unitのはコンパイルできて実行できたと思う.

できたlibを使ってのテストは何もしていない状態.
(パスとかオプション設定とか README.mingwみてると面倒そうなんで)

bcc

bccの場合は bcc32.cfg と ilink32.cfg の -L に psdk のpath(???/lib/psdk とか)が 抜けていたらそれを追加.

とりあえずdll版は作成できるけど、tlibで怒られてしまいstatic版は作れてない(未調査) でもって bcc v5.5.1 のせいかテストでコンパイルできず.. 面倒になったので挫折. (readme.bccもちゃんとみてないので)

その他のテキスト

インストールに関係ないけど、気になった文章の適当訳も.

README.utf8, stlport_namespaces.txt,


Academic Free License ("AFL") v. 3.0 なファイル

makefile 弄ってたらふと、ファイル先頭に、ライセンスとして Academic Free License 3.0 となっていて、検索すると、stlportヘッダフォルダでも
 type_traits

ファイルが、このライセンスになっていた.

これは c++0xから増えるヘッダで、v5.2.1では、これ単体で, 他の部分では Boost 発祥の type_traits がincludeされているため、 このtype_traitsファイルさえ使わなければ、気にしなくていいのだけど...

最近の STLportの git リポジトリからとってきたものをみると、 他のソースもこの type_traits ファイルinclude するようになっていて 結構影響する状態のよう.

実質が今のライセンスと かわるのかどうか...

Wikipediav2.0の和訳をみてると、 微妙に面倒くさそうに思える...(読解力無くて読み違えてるかも...)


[2011/01/07追記] 最近の開発版のソースを覗くと、type_traits を含めAFL3.0のファイルは無くなったようで、stlportのLICENSEのみでよさそう。




2010-2-13[土] unittestの作成メモ

D言語の unittest に触発されて、 C++用に真似たものを作ってみたことがある.

使い方はこんな感じ

// テスト例
#include "unittest.h"

class Foo { 略 };

UNITTEST(Foo_Test) {
    Foo foo;
    assert(foo.hoge() == 1);
    略
}

// 起動ルーチン
#include "unittest.h"

int main() {
    UNITTEST_RUN_ALL();
    略
}

  • unittest.hをincludeして
  • UNITTEST()でテストを書き
  • main()の初っ端で UNITTEST_RUN_ALL() を呼び出す.
  • テスト実行の有無は、コンパイラオプションでのUSE_UNITTESTマクロの定義の有無

といった感じでヘッダファイル一つですむ. そのヘッダの中身は

#ifndef UNITTEST_H
#define UNITTEST_H
#include <cassert>

#ifndef UNITTEST_MAX
 #define UNITTEST_MAX   256     ///< 登録できるテストの数
#endif

#ifndef USE_UNITTEST            // テストしないとき.

#define UNITTEST_RUN_ALL()
#define UNITTEST(T)     template<typename D> void uniTTesT_dmy##T()

#else   // テストするとき.

#define UNITTEST_RUN_ALL()  uNITtEST_Mgr<>::runAll()
#define UNITTEST(T)                             \
    class T {                                   \
    public:  T() {uNITtEST_Mgr<>::add(&test);}  \
    private: static void test();                \
    };                                          \
    static T uNITtEST_vAr_##T;                  \
    void T::test()

template<int N=UNITTEST_MAX>
class uNITtEST_Mgr {
    static unsigned tblNum_;
    static void*    tbl_[N]; //関数ポインタの配列だとvcが落ちたorz.
public:
    static void add(void (*fnc)()) {
        if (tblNum_ < N)
            tbl_[tblNum_++] = (void*)fnc;
        else
            assert(0 && "too many UNITTEST.");
    }

    static void runAll() {
        for (unsigned i = 0; i < tblNum_; i++)
            ((void (*)())tbl_[i])();
    }
};
template<int N> unsigned uNITtEST_Mgr<N>::tblNum_=0;
template<int N> void*    uNITtEST_Mgr<N>::tbl_[N];

#endif  // USE_UNITTEST
#endif  // UNITTEST_H

テストしないときは、
UNITST_RUN_ALL()マクロは 空なので main()で何も実行されず、
UNITST_TEST(T) マクロは 関数テンプレートを定義するが 使われず実体化しないので、コードは生成されない。

テストをするときは、
uNITtEST_Mgrクラスが定義されてる。
こいつはstaticメンバーだけで構成していて、 テスト関数へのポインタの配列とその数、 テスト関数をポインタ配列に登録するadd()関数、 登録された関数をすべて実行するrunAll()関数、 がある.

UNITST_TEST()マクロは、ファイルstaticのclass変数を定義にすることで main()実行前にコンストラクタが実行され、 そのコンストラクタ内でテスト関数へのポインタを UnitstMgr::add()で登録している.

グローバル変数のコンストラクタの実行順番は不定なので、Mgrの管理する変数はそれらよりも先に初期化されている必要がありstatic変数にしている(ので登録可能なテスト数/配列サイズも固定)

そして main()関数の開始時点で、uNITtEST_Mgrにテストがすべて 登録済みなので、UNITST_RUN_ALL ( UnitstMgr::runAll ) を実行すれば、テストが全て実行される.

わりと単純にすむ、というか、すませてる.
main()で1文とはいえテスト用に呼出す必要あるし、 テストの最大数を決め打ちする必要があるのは無粋だけど.


まあ、実際に使おうとすると、assertだけでなく、各種チェック用のマクロがそこそこほしくなるし、多少なりとはいえ、経過メッセージをだしたりエラー数カウントしたりしだすと、すぐ1桁以上大きくなってしまったけれど.

[これ]


こんな "オレ仕様" でなく CppUnit なり Google の gtest なり boost のモノなりを 使い慣れたほうが生産的だろうけれど、 慣れる以前に面倒そうで手が出せず、 こんなものを作ってしまった、と (ターゲット環境で使えるものがほしかったてのもあり)

ただ色々付け加えた後に、ひさしぶりに元の(上記の)ソースみると、 蛇足だったかなあ、という気にもなる.

※そういや、グローバルのコンストラクタって処理順保証なしだから マルチスレッドでばらばらに実行される可能性ってあるのかな? (当然そうだと今のままでは破綻)




2010-3-9[火] マイナーなCコンパイラをちょっと触る

フリーでwin環境用exeが作れる、ちょっとマイナーな Cコンパイラをちょろっと触ってみた、というかインストールしてみた時のメモ.

試したのは LLVM-gcc, PCC, LCC, TinyCC, COINS。

(マイナーというと語弊のあるモノもあるけど win環境用のcコンパイラとしては、で)

LLVM-gcc

(※追記:LLVM-gccでllvmを使う場合-emit-llvmオプションとつけないとダメだったよう)

(wikipedia)

LLVM&clang は、 そのvmな仕組みとか、 オプティマイズ等の実力とか、 使用用途(appleの動向)とか、 GPL(v3)より緩いライセンスがらみとか、 いろいろ話題で今後の発展に期待大なコンパイラ(vm)、 だけど、 win環境で試すには、 mingw-msys 環境に追加する方法になっていて、 ちょっとまだ敷居が高い感じ。

また、残念ながら win 環境向けにはまだ clang バイナリは無いようなので、試せるのは gccフロントエンドのモノのみ。 (追記:clangのほうは自分でコンパイルすれば使える..ということでさらに敷居が高い)

ただ llvm-gcc側にコンパイル環境として(mingw-gccをベースにした)必要なものは一通り入っているので、mingwコンパイラをインストールしておく必要はない(あってもかまわないけど)。

設定としては、まず msys 環境が必要。 mingw本家TDM等から適当なのをインストール。
うちは 猫研pack のtdm-gcc環境を使ってるのでそこに寄生。
ここでは c:\msys にmsysがあるとする。

LLVMのダウンロード頁から以下の2つを取得

    • LLVM Binaries for Mingw32/x86 (試した時は、v2.6)
    • LLVM-GCC 4.? Front End Binaries for Mingw32/x86 (試した時は gcc-4.2)

ダウンロードしたファイルを適当な場所、たとえば
  x:\llvm-2.6 x:\llvm-gcc-4.2
に解凍したとする。(来月には2.7が出るみたいだけど、今はまだ)

msys込みで、パスを設定。

set "path=x:\llvm-2.6;x:\llvm-gcc-4.2\bin;c:\msys\bin;%path%;"

あとは、llvmc 、または、llvm-gcc, llvm-g++ を用いて、 適当なソースをコンパイル、といった感じだろう。 (※簡単にヤッたら間違ってた。追記参照)

mingw 環境のコンパイラだけ置き換えた状態のようなんで、 使い方は mingw(gcc)。 win-apiアプリの コンパイルもできるよう。 (簡単な窓を出すだけのhelloプログラムは動いた)。

速度等はろくに調べていないけれど、xorshiftのときのサンプルをコンパイルしてみたところ、inline展開が働いた時のスコアは結構よいほうだった。 ただ、inline 展開をあきらめるのがvcやg++4.4より早いようで、xorshift128あたり から関数呼出になってスコア落ちた。gcc3.4.5同様素直な感じなのかな、と。

追記: llvmとしてコンパイルするにはオプションが必要のよう. でもってコンパイラ環境がうまく設定されていないのか、一度にコンパイルできず.こちら等を参考にして

llvm-gcc -O2 -DNDEBUG --emit-llvm -S test.c
llvm-as test.s
llc test.s.bc
llvm-gcc -o test.exe test.s.s

llvm-gcc -DNDEBUG -O2 --emit-llvm -S test.c
llvm-as -o tmp.bc test.s
llvm-ld -o tmp.2.exe tmp.bc
llc tmp.2.exe.bc
llvm-gcc -o test.exe tmp.2.exe.s

て感じにしてみる(後者のほうが全体に対するオプティマイズが効くかも)

※ llc で -march=x86 を付けるとwin用でなくなるみたいでマズイのだった.

※追記 こっちでLLVM-Clangを使ってみた。


PCC(Portable C Compiler)

(wikipedia)

かって(ANSI-C以前)の Cの標準だったろう Cコンパイラで、 最近はこちらでC99化していってるらしい。 (こちらもGPLv3の影響で脚光を浴びてるかんじ?)

もともと移植性のいいモノなためか、ちゃんとwin32版も用意されている。
コンパイラ以外はgnuツールなりmingwツール/ライブラリが採用されているようだ。

こちら から、 pcc-20090818-win32.exe をダウンロード。実行してインストール。

とりあえず通常のプログラムフォルダ c:\Program Files (win64なら c:\Program Files (x86)) にインストールしたとする.
※ひょっとすると、win64でも(x86)ついてなかったかもしれないので注意.

コマンドプロンプト窓でコンパイラを使う場合は、

set "path=%ProgramFiles%\pcc\bin;%path%"

を先に実行。この状態で pcc を用いてコンパイル。

pcc --help でヘルプ表示すると ld の分しか表示されず涙目だけど、 元はunix系のccそのものだろうから、そのあたりを見ればいいのか。 (基本部分はgccが同じにしてるはずだろうからgccのを試せばよいのかも)

mingwベースなんで、winプログラムも同様。とりあえず窓helloは、

pcc w_p_smp1.c -l gdi32

でいけた。

なお、出来たexeは mingw 同様 msvcrt.dll に依存している。


PCC コンパイラのコンパイル

当初 win32バイナリの配布に気づかず、ソースにwin32用バッチがあったので コンパイルしてみてた。 ので、そのメモも。
ソース修正は1行挿入のみだけど環境設定がちょっと面倒だった。

ソースについては、こちらから pcc-cvs-100306.tgz、こちら から pcc-libs-cvs-100306.tgz をダウンロード。 展開してできたフォルダを x:\pcc, x:\pcc-libs とする。
(どうも毎日バックアップされてるもののようで日による差分は不明、最新版とればいいんじゃね、で)

ソース修正は pcc/os/win32/config.h の31行目付近の

#if !defined(vsnprintf)
#include <stdio.h>     //この一行を追加.
#define vsnprintf _vsnprintf
#endif

をコメントのように#include <stdio.h> を追加するだけ。 (あとからstdio.hがincludeされるとvsnprintf置換でバグになるため)

面倒なのは bison や flex を使うのでそれらを用意する必要があること。 幸い猫研パックのmsys に入ってるので、msys環境を用いれば済みそう。

と実際にためすと、flex がハング。msys-regex-1.dll が無いと怒られる。mingwのダウンロード頁 から regex の dll 版をダウンロードして解凍(lzmaというあまり普及していない形式なので解凍ソフト(7z)も入れたり). とりだせた msys-regex-1.dll を msys\bin にコピーしたらok。(ああ、うちのmsysはちょっと古くパックの_a004のモノなので最新で直ってる可能性あり)

vc2008 でコンパイルする場合は

call "%VS90COMNTOOLS%vsvars32.bat"

をしておき(2005なら%VS80…,2003なら%VS71…だろう)

x:/pcc/os/win32 へカレントディレクトリを移動し、

build /cl /pccsrcdir x:\pcc /pcclibssrcdir x:\pcc-libs

を実行。うまくいけば pcc.exe (とmkext.exe) が出来ているハズ。

※bison等のツールの具合によっては、build /cl のみでコンパイルできるかもだが、己の使ったバージョンの場合、bisonに(相対パスの)ファイルが見つからないと怒られた。で、絶対パス指定してみたら回避できた、という状態。

できたexeを試す場合は、配布バイナリをインストールした環境のpcc.exeと置き換えてみれば、で。


また pcc 自身でもコンパイルできる。この場合は、インストールしたpcc環境のbinへパスを通した状態で

build /pcc /pccsrcdir x:\pcc /pcclibssrcdir x:\pcc-libs

を実行.

もし pccのインストールディレクトリを c:\program files\pcc 以外にしていた場合は、build オプションとして /pccdir c:\hoge\pcc のようにインストールしたpccフォルダを追加する必要がある。win64の場合 (x86)付なので指定が必要だろう(/pccdir "%ProgramFiles%" かな)。

LCC

LCC は、こちら が大本。 コンパイラ作成の教材のような感じで、 配布されているものは、ソースのみでバイナリなし。

ただ、これをベースに使える環境にしたパッケージがいくつかあるようで

といったものがある。


こちら にlcc対応のデバッガが公開されてる。

LCC-WIN32

LCC-WIN32 は結構昔からあって、 昔試した時点で、IDE環境完備でデバッガ等の出来もよく、 言語仕様拡張や生成改善等もされていて で独自発展していたのだけれど、 今、サイトをみると頁はあるけれどコンパイラ等へのリンク等がことごとく切れてる。 一応、去年の秋はまだダウンロードできてたのだけど。 開発会社のトップページを みると権利関係が別の会社に移譲されたようなことが書いてあるようで... 現状フリー配布はなくなったってことなのかな(LCC-WIN32系のサイトをあたれば、FTPからのダウンロードがまだできるかもだけど、リンクしないでおく)。


Pelles C

PellesC もLCC-WIN32同様に IDE完備の開発環境になっている。 IDE上でSJIS入力できたり、char文字列中に表やソで\含文字を使っても 実行で文字化けせず表示されてちょっと感動。 デバッガもそこそこいい感じ。ただwatchポイントは貼れず(LCC-WIN32は出来てた)。 プロジェクト設定は DEBUG/RELEASE切り替え等はできないようで、 プロジェクトのオプション設定でコンパイラ頁とリンカ頁のデバッグ設定をそのつど 切り替えないと駄目なよう(たぶん。でも、その程度)。

当然Winアプリ作れる。(ウィザードもあり)
(あとWinCE用の開発環境にもなっている)

コマンドプロンプトで使用するときは、まず、

set "PATH=%ProgramFiles%\PellesC\bin;%PATH%"

を実行。cc を用いて

cc hello.c

といった感じ。win窓helloなら

cc /Ze w_p_smp1.c user32.lib gdi32.lib

で、とりあえず。


LCC コンパイラのコンパイル

大本のLCCはソースしかないけれど、win32様のコンパイルバッチが入ってたので 試してみた... が、少々修正する必要があった。 のでそのメモ。

試したのは v4.2 のもの。tar.gz, tar.Z, zip の3つの圧縮ファイルがあるけれど、 基本同じものだけど、ソースの改行コードが違うかも。 winなら zip のモノを選ぶのが吉。

※実は tar.gz のを使った。lburg/lburg.c ファイルのみ改行コードが lf(\0a) でなくcr(\0d) だったためコンパイラに怒られた。lfに置換して済ましたけれど、zipのを展開したらcrlfでそもそも出会わないはずの不具合だったorz

win向けにコンパイルするのには、makefile.nt を使う。 使用するコンパイラは vc. ただちょっと古いバージョン(vc6ぽい) 向けみたいでvc2008にはすでにないオプションが使われていたり。

makefile.nt の9行目付近からの

CFLAGS=-DWIN32 -Zi -MLd -Fd$(BUILDDIR)^\
LD=cl -nologo
LDFLAGS=-Zi -MLd -Fd$(BUILDDIR)^\

の部分を

BUILDDIR=.
CFLAGS=-Doutp=outP -DWIN32 -Zi -MT -Fd$(BUILDDIR)^\
LD=cl -nologo
LDFLAGS=-Zi -MT -Fd$(BUILDDIR)^\

のように修正.
-Doutp=outP として、マクロ置換しているのは、関数宣言された名前を変数名としてつかったといって怒られたため、その回避。 (outpはx86系のout命令をc用にした名前として昔からある...のでビルトイン関数かなにかの影響だろうか... とりあえずのお試しで回避できたため原因追求せず)
(-MTにしてるから-Ziいらないけど、面倒なので残したまま。逆に-MTdにするでもいいが後述の修正箇所の.lib名もそれにあわせる必要あり)

あと、etc/win32.c の

  • 8行目付近

    #define LCCDIR "\\progra~1\\lcc\\4.1\\bin\\"

    の内容を、実際にlcc.exeをインストールするフォルダに変更.
    とりあえず、お試しなので "x:\lcc42" で作業しているとして、そこを設定。


  • 20行目付近の "libc.lib""libcmt.lib" に修正する。

win32.c を見ての通り、結構、環境をハードコーディングしているので、 本格的に使うならば、いろいろ修正したほうがよさげな雰囲気。
また、この内容から、コンパイラ以外のリンカやライブラリ等は VCに寄生するスタイルのよう。

とりあえず、staticリンクライブラリが使えるエディションならコンパイル可能になったはず。

dllランタイム版でコンパイルする場合は、上記までの修正に対してさらに、

  • makefile.nt の CFLAGS,LDFLAGS の -MT-MD に変更
  • cpp/unix.c の memmove関数の定義を #ifndef _MSC_VER で挟む.
  • etc/lcc.c の extern int getpid(void);宣言を #ifndef _MSC_VER で挟む.
  • etc/win32.c の "libcmt.lib"(元"libc.lib") を "msvcrt.lib" に変更.

を施す。

で、vc2008を使ってコマンドプロンプトでコンパイル

call "%VS90COMNTOOLS%vsvars32.bat"

を実行(2005なら%VS80…,2010なら%VS100…って感じか)

作業場所が x:\lcc42 フォルダだとして、そこに移動して

nmake -f makefile.nt clean
nmake -f makefile.nt all

を実行. 上手くいけばlcc.exe,cpp.exe等が作られてる(ハズ)。

お試しは

extern int printf(const char* fmt, ...);
int main(int argc, char* argv[]) {
    printf("hello world\n");
    return 0;
}

を hello.c としてセーブ.

lcc hello.c

でコンパイル。 うまくいけば a.exe ができるので、a.exeを実行してhello worldが表示できたらokと。
※ リンカー等はvcのモノを使うので、vcコンソール環境が使える状態で使うこと.

なお、#include をせずに直接 extern でprintfを宣言してるのは、#include <stdio.h> をすると cpp.exe 実行中に帰ってこなくなったため... 追求するのは面倒なので、お試しとしては、これで終わりにしておく。


TinyCC

TinyCC は小さいCコンパイラ。 (コンパイラ本体のc,hソース行数は3万行弱)。

けど、文法は、ほぼフルスペックのC89+α(C99の一部)。 (浮動小数点数も構造体もビットフィールドもあるし long long もある, らしい)

とりあえず、サイトからwin用のバイナリを取得して、適当な フォルダに展開。とりあえず、c:\tcc にいれたとする。

set "PATH=c:\tcc;%path%"

でパスを通して、あとは tcc hello.c のようにしてコンパイルするだけ。 winアプリも出来るよう(examples/hello_win.c )
※ランタイムとしてmsvcrtを使用の様.

すごく、あっさり使えてしまう代物のよう。


※実は試すまで、この作者のotcc の延長のモノかと思ってた。 舐めてました。すみません。 otccのほうはwin用でなくlinux用の 1000行に満たない小さいソースのKR-C系ミニ言語. 実行ファイル生成. (IOCCC 2002優勝らしく. 配布ではちゃんと可読なバージョンもあるのでそれをみるのも吉. それどもトリッキーですが)

TinyCC コンパイラのコンパイル

mingw-gcc を用いる。
mingw-gcc を使える状態にしておいて、 サイトから取ってきたソースのzipを x:\tcc-0.9.?? にでも展開する。

x:\tcc-0.9.??\win32 フォルダに移動して、 build-tcc.bat を実行する。exeができたら吉。


COINS

COINS についてはリンク先の概要をみるなりして。 コンパイラ研究のインフラとしてのCコンパイラが配布されてるよう。 ライセンスはApache Licene Version 2.0

モノは java で作られていて、また win環境では cygwin を使う ので、予め、それらがインストールされている必要がある。

javaに関しては、コンパイラをコンパイルするのでなければ jdk は必要でなく jre がインストールされていればよさそう。何かの折にjre6がインストール済みなのでそれを利用。
c:\Program Files (x86)\java\jre6 にインストールされているとする。

cygwin は gcc等の基本的な開発ツールがインストールされていればよく。 かなり昔にインストール済みなので、新規インストールについては他のサイトを適当にみてもらって。 と自分の環境はしばらく更新してなかったのでsetupで更新... したら、どうも最新のcygwin環境だとCOINSはちょっと不具合がでるようで対処が必要になる.後述)
cygwin は c:\cygwin にインストールされているとする。

COINSコンパイラのインストールや使い方については、こちらこちら やその他諸々を参考に...

ダウンロードはCOINSのダウンロード頁 から、 こちらのサイトの助言にしたがい 国際(en)版をダウンロード。 (jp版は euc が使われているためツールによっちゃwin環境では不味い場合があるらしい... なおjp版だけならSourceForgeの頁 からもダウンロードできる)。
己が入手したのは coins-1.4.4.3-en.jar

ダウンロードしたファイルを(jarだけど)zipファイルとして適当なフォルダに解凍。
とりあえず、 x:\coins\ に解凍したとして、
  x:\coins\coins-1.4.4.3-en
ができているとする。

※この中には classes\ フォルダがあり中身が生成済みだったので、今回はそれをそのまま使うことにした。ソースのみ配布のバージョンなら当然再コンパイルが必要。


最新のcygwin での不具合回避のため、c:\cygwin\bin 中から gcc-3.exe cpp-3.exe
gcc.exe cpp.exe に変名して x:\coins\bin\ フォルダ作ってコピー.

こちらで紹介されてる不具合回避方法だとCOINS以外で不味い場合もあるかも(?)なので、また、今回はhello world のみの簡易なお試しなので暫定的な回避にした。


コンパイルでのコマンドプロンプトでの記述が長くなるので、次の一行をバッチにしておく。

java -class x:/coins/coins-1.4.4.3-en/classes coins.driver.Driver -coins:target=x86-cygwin,assembler=as %1 %2 %3 %4 %5 %6 %7 %8 %9

名前は coins_tc.bat として x:\coins\bin\ にセーブ。


コマンドプロンプト窓(dos窓)をあけ、pathを設定する。

set "PATH=x:\coins\bin;c:\cygwin\bin;%ProgramFiles%\java\jre6\bin;%PATH%"

※不具合回避で置換すべきexeのあるフォルダがpath検索で先に見つかるように設定。

hello.cとして以下を適当なフォルダに作成しておく.

#include <stdio.h>
int main() {
    printf("Hello World!\n");
    return 0;
}

先のバッチを使い

coins_tc.bat -o hello.exe hello.c

のようにコンパイル。出来た hello.exe を実行して、hello world が出力されたらok.

cygwin ツールを cygwin 環境以外で使うため、パス関係の警告がいろいろ出るけど無視。

もし cygwin 環境で実行したいならば、この(上記path設定の)状態で

bash --login -i

を実行。カレントがhomeに移動してるので、お試しフォルダへ再度移動。
そこで coins_tc.bat -o hello.exe hello.c を実行すれば、パス名警告は減る(無くなる)かも。


コンパイルして出来上がったexeは、cygwinのgccのライブラリをリンクしているだろうで、当然、その制限をうける。


(※だめもとでmingw環境でコンパイルしたらやっぱり駄目だった。リンク関係でいろいろ無いと怒られる。けど、そのへんの問題だけなのかも?)


その他

  • hello world頁をどうこうしようと思ってやり始めたが面倒になってあきらめ... が、折角試した分くらいは、で書いたのがこの頁。
  • vc,bcc,dmc,watcom はとりあえず、いろんなサイトあるし。
  • Fail-Safe Cというモノもある模様。win用はなさそう?で、cygwinで試しみるも失敗。(どちらかというとocaml関係に振り回される時間のほうが多くorz)
  • COINSしたくてcygwinも使ったが、cygwinだとunix系のモノが試せてしまい、前行のようにダークサイドへ突入...で疲れたので止め。ポート済み以外はみないですまさないと... TenDRAはないのかな。
  • 試して無いけどwinで動くcインタプリタとして Ch とか CINTとか
  • Under C++ とか、 その他諸々以外とある模様。





2010-3-12[金] ちょっと速度比較

前回触った LLVM-gccやpcc,coins (で作ったプログラム)の速度が気になったので、 手持ちのCコンパイラ(vc意外はフリーのもの)で適当に実行速度を計ってみた。

(3/14修正: cygwinの計測が間違って別のmingwでの結果になってました).
(3/15修正: llvm-gccは生成方法を間違えていたためやり直しました. また他と比較しずらいので clangの結果も含めました)

試したコンパイラは全てwin環境用で

コンパイラ 生成にかかわるオプション補足
vc9sp1 64bit -GR- -Ox -DNDEBUG -MT
vc9sp1 32bit -GR- -Ox -DNDEBUG -MT
cygwin gcc 3.4.4 -O2 -DNDEBUG bashでなくcmd.exe上で実行.
mingw32 gcc 3.4.5-O2 -DNDEBUG
mingw32 gcc 4.4.0-O2 -DNDEBUG
LLVM-gcc 2.6 -O2 -DNDEBUG -emit-llvm 実際には一度に作れず複数工程になる
clang -O2 -DNDEBUG -emit-llvmせずで、おそらくclang単体での生成
Open Watcom 1.8 -Ot -O3 -DNDEBUG -finline-functions
-frerun-optimizer -floop-optimize
-funroll-loops -finline-math
dmc 8.51 -o -DNDEBUG
pcc-20090818-win32-O3 -DNDEBUG
COINS 1.4.4.3-en -O2 -DNDEBUG bashでなくcmd.exe上で実行
BorlandC 5.5.1 -O2 -Ox -RT- -d -dc -DNDEBUG
PellesC 6.00.6 /Zx /Ze /Ox -DNDEBUG
TinyCC 0.9.25 -DNDEBUG オプティマイズは無い

正直、オプションが、どの適度適切かは不明。 Watcomはつけすぎてるけど、基本はデフォルトに近い状態。
浮動小数点関係は、設定しだいで結構違うだろうけど不精してせず(watcom以外)。

試したテストプログラム

バイリニアによる画像拡大 乱数で生成したピクセルで埋め尽くされた640x480の32ビット色(ARGB)画像を1920x1080へ拡大する処理。10回の平均値。
安易インタプリタでのスクリプト実行 400行ほどのおもちゃのインタプリタ言語で、 5000*5000ループの適当なサンプル実行. (仕組みが手抜すぎて実際的な比較向けではなかったかも)
クィックソート 以前試したCでかかれたQUICKソートと、Cライブラリのqsort互換のクィックソートルーチン のテスト.
とりあえず、この頁の結果には int 1000000個をソートしたときの時間を記入.
Dhrystone 2.1 整数演算用ベンチマーク. Wikipedia等みて. モノは、こちらの記事から リンクされているモノを使用. ソースは2.1のモノだけ使用(コンパイル楽なため). けど、Old-Cスタイルでエラーだすコンパイラ対策でANSI-Cスタイルに修正したり ヘッダ依存関係調整したり. 使用時はループ回数を100000000回にして実行.
Whetstone 浮動少数点演算用ベンチマーク. wikipedia等みて. こちらのサイトの BenchNT.zip に入っていたソースを利用. こちらもコンパイラごとの調整のための修正あり.

download:上記のソースのzip

たくさんやるのも面倒なので、これだけ(これだけでも結構しんどく)。 自分が大雑把に雰囲気をつかむため、なので、あまり適切でないサンプルかも。 1core 1threadな簡易な処理だけだし。 Dhrystone,Whetstoneは一応してみたけど、あまりピンときていない (処理内容わかってないからだろうけど).


実行環境は vista64(PhenomIIx4 3G)、通常のデスクトップでDOS窓とエディタ程度だが、サービスや常駐モノはある程度残った状態で実行.(テスト中の 1core がフル稼働で、あとの処理は他のcoreが大筋まかなってるだろうと期待. 以前別の計測にてsafemodeで起動して計測したほうが安定していた感じはあったけれど、酷すぎるほどの差もなかったので楽してる)

実行結果 は (3/14 一部計測し直し. cygwin計測ミス、安易インタプリタのclang対処反映)

コンパイラBilinear 拡大(ミリ秒)安易 インタプリタ(秒)quick sort(μ秒)QSORT(μ秒)Dhrystone/secWhetstone (MWIPS)
vc9sp1 64 87.525.21443939856142146413465.753
vc9sp1 32 189.224.71445269039115300362284.091
cygwin 344262.020.22030060900102082482108.046
mingw 345 245.025.4191666155698931541456.068
mingw 440 265.025.31911885483102732691554.432
LLVM-gcc(sse2)105.827.61987135860(25056376)1525.463
clang 199.927.91522567820128419161478.956
watcom 387.326.42822242918111869342199.402
dmc 371.925.1212246058090407741560.336
pcc 289.932.3194367962780334191176.030
COINS 384.128.0187006550059908941335.854
Bcc 5.5 582.239.41909259047101112231692.216
PellesC 429.330.4146966679473179651241.080
TinyCC 511.449.96621310585857544021063.352
(補足) ↓good↓good↓good↓good↑good↑good


たったこれだけだし、 測定(実行)環境はザルで実行毎の誤差からすれば 細かい数値みちゃうとまずいだろう。 特に浮動少数演算関係のオプション設定が適切でないだろうで 設定かえたら(Whetstoneとか)結果変わってきそうな気もする. (c標準ライブラリも計測範囲で使われてるので それの影響もどう据えるかにもよるし)。 が、おおざっぱに、vcが1番よさそうで次gcc系、 後は混戦で、ケツがTinyCCって感じか。
今回以外の例を思えば vcが抜きでてるとはいいきれないけれど. (Intel C/C++気になるけど懐的に手が出せないのでVCで満足しとく)

vc9sp1 64 の結果は CPUが64bit CPUなので、コンパイラの比較ってよりCPUの比較になるけど、 64ビットOS用にコンパイルするだけで、 結構違いがでる処理もある、という例になってるかも、で(代わり映えしない処理もあるけど)。

バイリニア拡大の結果は、 64ビット整数の利用頻度が少なかろうと 汎用レジスタが増えたことによるメリットが効いている例だろう (あとSSE2も関係あるか? 追記:というか、汎用レジスタどうこうでなく、 まさにSSE2になったことが効いているよう。 clangの結果がいいのも、SSE?なコードが生成されているためのよう (clangのほうはsseしてない) )。 32bitでもVCが結構速くなる例で、結構かたよった代物だろうけど... (この手の画像処理なんかは普通からすれば特殊な扱いになるのかも. 速度/ハードを気にしだすと生のCだけで済まさないだろうし)

感想としては llvm(-gcc)は(いろいろミスして勘違いしまくりだったけれど)ものによっては非常に速くなったりでびっくりで早く使い易くなってほしく、 Clangはllvmをしなくても(?)これだけの性能あっていろいろ期待、 PCC は速度は思ってたよりはいいかも、だけど(Win版は)思ったより安定してなさそう、 PellesC はそんなもんだろう、 TinyCC は実行時速度じゃなくてコンパイル速度優先で(-benchなんてオプションがあるくらいだし)スクリプト言語的にCソースを扱うような方向があるようなので 実行時速度はこの程度の差ならokなんだろう、 COINSは悪くないのだけど期待しすぎてたため (ひょっとするとあまりx86系向きじゃないのかもだけど) ちょっと哀しい気分、てとこか。

※追記:cygwin-gcc、測定ミスでやりなおしたけど、gcc3.4の範囲なのでたいして値はかわってない(でもWhetstoneは結構ちがうか。浮動小数点はオプション設定しだいだろうでデフォルトがいい状態だったのかも)。 もともとcygwin使ったCOINSの結果と比較するのにmingwのでいいか微妙な気もして追加したものなので(ただの計算だけだとそう違わないだろうけど). あと最初の4つのテストで cygwin-gccとCOINSは win-apiでなくtime.hを用いて計測しているため若干条件が違う、とも.

※追記:安易インタプリタの結果は、clang対策での修正前にくらべ、どれも4,5秒短くなっている. isalphaやtoupperを手抜きなマクロに置き換えただけだが、結構ライブラリのオーバーヘッドがあったということか. テーブル参照より単純比較のほうが速いのかスレッド関係やロケール対策がらみなのかはしらないけれど。

※追記: llvm-gcc のやり直しにおいて、Bilinear拡大は最適化されすぎて計算がなくなってしまったため、そうならないよう、若干ソースを修正(計測時間外での対処)した.
また、Dhrystone2.1の結果も最適化されるぎている可能性があるかも(大丈夫?).
(dhry_1.c dhry_2.c を1つのソースにした場合のvc64も結構はやかったので 全体最適化としてはありなのかも?)

※追記:llvm-gcc 同様に clangも -emit-llvm で生成すると速くなる模様 (例えばbilinear拡大のは 100.9 に). が、どうも何かミスっていて正常終了できないハングするexeが作られるためちゃんと試せていない.(追記:スタックフレームポインタを保持してるはずの ebp を退避せずに汎用レジスタ的に破壊して使うコードができてる模様) (4/23追記: 試したのはbilinearのだけだが、最近のclang(1.5 trunk 102038)で試したら修正されてるようで動作)


コンパイル不具合のメモ

  • pcc は #include で、#より前に空白が置かれていると、エラーになる場合があった.
  • 行頭に#を置けばok. #の後ろに空白が入るのはok.
  • pcc で、初期化していないグローバル or static 変数でハングする場合あり(必ずではなく).
  • char buf[10] ={0}; な感じに初期値を入れてしまうことで回避できた.
  • COINSでdhrystoneコンパイル時、 gccのヘッダを流用しているため?か、
  • stdio.hヘッダにあるstatic inlineになっていないinline関数(fget?の内部関数)が 複数のobjでincludeされてると、リンクで名前の衝突が発生. (実際に必要としたソースは1つだったので、includeを調整して回避).
  • COINS, 正常なtolower(c)で')'がらみでエラー. (interpreter_smp:マクロでtoupperを乗っ取って回避).

(とかいたけど、coinsはちゃんと環境できていない可能性もあり)





2010-3-13[土] win標準と衝突するunix系コマンド.

こちらでclangのvcでのコンパイルを紹介されてたので、やってみた。出来たコンパイラを使うとincludeでvc側の ヘッダ読み込まれてエラー。 _WIN32が定義されてるし、何か、しなきゃいけない (環境)設定が抜けてるんだろうなあ。 (includeしてないソースのコンパイルでexeやasmはつくれてた)

で、そのとき、こちらの GnuWin32 をインストール.

cygwinやmsys同様 unix系フォルダ構成を持つ状態のコマンドラインツール群で、 dllや言語ファイルがあるので単体コマンドを流用したい身には一長一短だけど、 コンパイラやスクリプト言語等は含まれていないので、ある意味、身軽で、 通常(常用)の環境変数PATHの最後にGnuWin32/binを追加して使うのでも よいように思えてきた。

unix系ツールと win(dos)標準コマンド名でいくつか衝突するけど、Windows/System32/*.exeとgnuwin32/bin/*.exeを比べると

calc.exe 電卓だが、gnuのはコンソール、WinのはGUIアプリ.
expand.exe 圧縮データの解凍、だが、対象とするデータ形式は(たぶん)違ったはずだし、 引数オプションも違う.
find.exe gnuのは ファイル検索、Winのは テキスト中の文字列検索.
sort.exe ともにテキストのソートだが、オプション引数は違う.
whoami.exe ともにユーザー名表示だが、表示形式が若干違い、gnuのは ユーザー名だけだが、winのは コンピュータ名\ユーザー名 となっている. オプションも違う.

ぐらいか。
まあ、これらが関係ない状況で使う分には大丈夫かな、と。

当然他のパスも通るので衝突がありえるけど. (コンパイラ関係だと link.exe とか)
cmd.exeの内蔵のecho,mkdirも衝突するが内蔵コマンドゆえwin側としては問題なし. unix系ベースで考えるときは問題あるだろうけど、そういうときは cygwin,msysあたりをつかっているだろう、で.


※と書いたが、別に GnuWin32 でなくmsys でもほぼ同様かもだけど... (cygwinはともかく msys+mingw環境も特殊性があるのかどうか)




2010-3-14[日] winの LLVM-Clang でコンパイル.

Clangで、なんとか、コンパイルできた。 (前日冒頭のつづき)
単純なhello.cで#include <stdio.h>だけなら、実はそのまま出来てた。 ただ、3/12のテストルーチンをコンパイルするとヘッダ関係でいろいろ不具合出た。

コンパイル出来た llvm,Clang のソースは llvm rev.98447、clang rev.98448のもの(結構頻繁に更新されてるよう)で、vs2008sp1 にて release の ALL_BUILD して生成.

まず、_WIN32等が設定されてたのは まさに Clangのソース内で設定されていた。 win環境なら _WIN32 定義してて、また、VC環境だと VCのinclude等のパス設定するような処理があった. (VCでコンパイルしたから呼ばれるのかVCがinstall済みだからよばれるのかは よくわかってないけど). でもってmingw関係も定義されてる雰囲気だった(mingwやgccを詐称してるよう).

VC関係は邪魔なので -nostdinc 指定してデフォルトのincludeパスを見に行かないようにし、 引数で llvm-gcc-4.2 の環境を流用して設定するようにした。 (別に llvmのでなく普通の(最近のバージョンの)mingwの環境でも大丈夫そう)
だいたい

clang.exe -nostdinc -Dwint_t=wchar_t -D__declspec=__declspec -Ix:/llvm/bin/lib/clang/1.1/include -Ix:/llvm-gcc-4.2/include -Ix:/llvm-gcc-4.2/lib/gcc/i386-mingw32/4.2.1/include -O2 -o test.exe test.c

といった感じにコンパイル. +こまごま修正.

  • windows.h を受け付けてくれるが wint_t が未設定だったみたいで -Dwint_t=wchar_t で誤魔化した.
  • time.hをincludeしたときは、__MINGW_IMPORTが未定義扱いだったので -D__declspec=__declspec を定義して誤魔化した.
  • inline関数だった箇所がリンク時に未定義だって怒られたので、static inline に修正した(C++じゃなくてCなんだから static inline じゃないとマズイのだろうな).
  • ctype.h をincludeしたら_imp____mb_cur_max_dll等で怒られ、とりえあず ctype.h を使わないようにして逃げた.

ヘマして何か設定が足りてないだけかもしれないが、まだ、ちょっと面倒な状況かも、で。

テストの実行結果は以下の通り。 (最適化オプションは-O2にしたけど妥当かどうかは未考慮)

コンパイラBilinear 拡大(ミリ秒)安易 インタプリタ(秒)quick sort(μ秒)QSORT(μ秒)Dhrystone/secWhetstone (MWIPS)
LLVM-clang 199.927.91522567820128419161478.956

他の結果はこっちみて...
結構いい感じ。 このテストだと、VCの次くらい …gccよりよかったり悪かったりがあるので、類似物じゃないよな。 (安易インタプリタはctype.h関係を手書きマクロに置き換えたので若干条件違うことになるが→結局、他も計測しなおした)

LLVM-gcc は、dmc に対する gdc のようなものに思ってたのだけれど、どうも、測定結果を思い直すと(llvm用コードでなく)ネイティブコード生成時はただのgcc(4.2)なのかも。

追記: やっぱりマ抜けていた。--emit-llvm を指定しないとただのgccかも. --emit-llvm でllvmなコードを一旦はいてからx86向けを作る、みたい. (コンパイル手順はこっちに, 結果はこっちに追記)

で、clang も -emit-llvm 付で生成すれば同様にさらにオプティマイズできるよう。
ただ、手もとの環境で作ると、生成した.exeはハングするので、ちと残念な状態。 (ハングする前に計測結果のでたモノをみるかぎり llvm-gccと同様に早くなってた)
4/23追記: 最近のclang(1.5 trunk 102038)で試したら修正されてるようで動作。(試したのはbilinearのだけだが、さらに速く(97)なっている感じ)




2010-3-15[月] watcom,dmcのテンプレート不具合

open watcom 1.9rc1 が出ている模様. が c++ 関係はあまり進展していないのか、 1.8よりちょっとは増えたようだけれどまだ未実装のSTL関係は多そうで (stable_sortなかったり)、 クラステンプレートのメンバー関数テンプレートをクラス外に書くのも まだ未サポートのよう.

template<typename T>
class Bar {
public:
    template<typename U> void test(T* t, U bgn, U end);
};

template<typename T>
template<typename U>    // この行.
void Bar<T>::test(T* dst, U start, U last) {
    while (start != last) *dst++ = *start++;
}

のBar<T>::testの2つ目のtemplateでシンタックスエラー.

template<typename T >
class Foo {
public:
    template<typename U> void test(T* t, U bgn, U end) {
        while (bgn != end) *t++ = *bgn++;
    }
};

のようにクラス内に書くのはok.

ついでに、上記は dmd(8.51) でもコンパイルエラー(startが未定義)になる。 こっちは、 テンプレートな引数の名前が Bar::test()宣言と定義で違うのが気に入らないらしい。 定義側の引数 start, last を bgn, end に修正すれば ok。 (テンプレートでない引数は名前が宣言と定義で違っても無問題)

別のコンパイラ(bcc 5.? だったか)でも、

template<typename CharT, class Traits>
class Foo {

のようにクラス定義してメンバー関数を外に

template<typename C, class T>
void Foo<C,T>::hoge(…) {

みたいにテンプレート引数名を変えていたら 某かの不具合がでた覚えがあり(名前を統一したらok)

汎用性を思うならば(古いコンパイラ気にするなら)、 クラステンプレートのメンバー(関数)は、 下手にクラス定義から分離せずに、内部に書いてしまうほうが 余計なバグに出会わずに済むのかも。 (分離する場合は名前を揃える... てか、ひょっとして普通揃えないとダメなのかな?)

(ごちゃごちゃする定義はクラス外部に追い出して、 クラス宣言は身軽にしておこう、 なんて考えてたらドツボにハマることもあった、と)





2010-3-20[土] LLVMで Cに変換してみる

LLVM (llc) には Cソースコードを生成する機能があり、 C++ソースをCソースにすることができる模様。

ただし C++ から C への直接変換するのではなく、 一旦.ll/.bc(llvm用アセンブラソース,ビットコード)にしたものを、 llc.exe で(ターゲットCPU用アセンブラソースのかわりに) Cソースへ変換するというもの。

普通のアセンブラソースをCに変換した場合 オーバーヘッドは当然あり、 全体として問題になることはそうないかもだが (昔アセンブラソースからCに変換しての移植作業を何本かやったときの印象)、 何割(何倍)か遅くなっていてもおかしくない。

が llvmの .ll/.bc は、 普通のアセンブラソース/オブジェファイルでなく、 それより情報の多い中間コードなわけだし、 llvm-gcc & llc でオプティマイズしているため、 Cソースになっても元よりも速くなる可能性もありそう。

ということで、ちょっと、試してみた。 3/12にしたテストの1つ目。 C++でなく Cソースだけど。 (32bit色640x480→1920x1080拡大の50回生成の平均時間を求める奴. 実行環境は前回同様)

llvm-gcc で

llvm-gcc -S -o tmp.ll -emit-llvm -O2 -DNDEBUG test.c
llvm-as  -f -o tmp.bc tmp.ll
llc -march=c -f -o test_dst.c tmp.bc

として test_dst.c を生成。
なのだが、このまま別の(複数の)コンパイラでコンパイルしてみると __imp__iobやQueryPerformanceCounter等が未定義参照だと リンカに怒られる。 __imp__iob は stderr の本体(を収めた配列名)、 QueryPerfomance…は時間取得につかってるWin-APIのもの。

ヘッダ込みでコンパイルされた結果を C化してるのだから、 
llvm-gcc でコンパイルする場合のヘッダ/ライブラリと、
ターゲット・コンパイラでのヘッダ/ライブラリが同じ(矛盾しない)
でないと当然マズいのだった。

とりあえずstderrやwin-apiを使わないようにして(外部はC標準関数だけにして)回避。
ソースは、 これこれ
それを llc で変換した後のソースは、 これ

ついでに 一旦 ldでまとめたものを.llに戻してから llc したものも試す。

llvm-gcc -S -o tmp.ll -emit-llvm -O2 -DNDEBUG test.c
llvm-as  -f -o tmp.ll.bc  tmp.ll
llvm-ld     -o tmp.ll.exe tmp.ll.bc
llvm-dis -f -o tmp.2.ll   tmp.ll.exe.bc
llvm-as  -f -o tmp.2.bc   tmp.2.ll
llc -march=c -f -o test_dst.c tmp.2.bc

変換後のソースは、 これ

前者の変換後ソースには元の関数を維持しているが、 後者の変換後ソースでは関数はmain()だけになっている。


2つの変換後のソースは、だいたい他のコンパイラでもコンパイル可能。
(ダミーの alloca.h の読み込みを用意したり、 dmc では bool のtypedefが衝突するのでダミー alloca.h 内で誤魔化したり する必要はあった) (このとき使ったllvmは rev.98686 )

が失敗したモノもあり、
vc64に関しては、ハング(作られたソースが32ビットcpu専用のソースかも?)。
bcc 5.5.1 は宣言に型が多すぎる、と怒ってくれてコンパイルできず (bcc 5.8.2は可)。
clang は型チェック関係でひっかかるので挫折。
mingw440 は、前者の変換ソースのものを実行するとハング。
pcc では、後者の変換ソースでは、DEP チェックにひっかかりハング。

実行できたものについての結果は以下 (単位:ミリ秒)

コンパイラ 元の結果前者の変換での結果後者の変換での結果
vc9sp1 197153162
cygwin gcc344 256238237
mingw gcc345 255239237
mingw gcc440 269---255
LLVM-gcc42(SSE?使用) 103109104
open watcom(1.9rc1) 397327317
dmc(8.51) 352301317
pcc 323308---
coins 493334317
PellesC 408353350
TinyCC 449397396

測定したタイミングによっては10,20ぐらいの差がでたりするかもで、 ざっくりとした感じに受け止めてもらうとして。

LLVMのツールであるllvm-gccではあまり差はないようだが、 他のコンパイラでの結果は、多少なりとも llc で変換したソースのほうが速くなってる雰囲気。

ただ前者と後者の変換については、モノによって多少違うも、 測定誤差でありえる範囲の差で、あまり違いはなさそうに思う (関数の分割具合の違いによるオプティマイズの トレードオフはあるだろうで、それが微妙に出てる可能性もあるけれど)

他のソースも試すべきたんだろうが、面倒で挫折... 他の例でも速くなるのか遅くなるのかどうかは結局ソースしだいと思うが、 それでも元のソースよりも速くなる例ができたわけだから (元ソースがヘボいのだろう、というのは置いといて)、 他の例でもそう酷く遅くなるようなことはないんじゃないかと期待.

※'元の結果'は3/12の結果と比べて少しずれてる。やってることはほぼ同じだけれどソース的には多少(時間取得関数だけでなくclang測定対策等)違うせいか、測定誤差といいきれない差のものがある. 前回のexeを実行すればやはり前回と同様の値なので、ソース変更の影響のよう。今回は今回、ということで。

zip


C++ → C

で、 肝心の c++ → c .
C++標準ライブラリの使用については、 実体がすべてヘッダでの定義ですんでいるようなモノ(std::sortとか)を使う分には、 (実体がライブラリ(アーカイブ .libや.a)化されているものを使わない範囲では)、 変換ソースを他のCコンパイラでもコンパイル&実行できる(た)。

が、g++(clang)側のライブラリ(.a)に実体がある関数や機能を使った場合は、 コンパイルできても当然リンクが行えない状態。 bad_alloc みたいなライブラリものもそうだけれど、 virtual使ったり 例外を使った場合もそう。その他諸々。 C++らしい組み方をしてるとまずその手のものは使われてるだろうで...

足りてないリンク物の代用品をターゲット環境用にも用意できれば なんとかなるかもだが、大仕事だろう。(あるいはターゲット対応をllcに施すとか... どちらにしろ個人がチョロですむ作業ではなく)

I/Oを含まずtemplateを使ったような処理をベターCの範囲で書いてCに持ってくる、くらいなら...と思うも、やっぱ面倒だなあ.


あと、llc は c だけじゃなく c++ ソースも生成できる。
計測に使ったソースを後者の変換をしてみたものが これ

なんかすごい、というか、目が点になる、というか。
効率どうこう以前に趣旨が違うもののような気もする。
(パッと見でincludeフォルダ設定を追加してコンパイルを 試しみたけど、どれも上手くいかず。あまり追及する気にもなれず)


※と、まあ、発展途上のllvmを使っての感想なんで今後どうなっていくか、わからないけれど

他のC++ → C トランスレータ

ついでのメモ。

元祖のC++実装の cfront は、Cソースへのトランスレータとして実装されている。 例外が実装されずに開発は終わっているが、 こちら でR3.0.3等いくつかのバージョンのソースが公開されている模様。 (使えるかどうかはしらない)

現行のC++をサポートしているだろうトランスレータとしては Comeau C/C++。 有料だけど低価格($50)。 面倒がって未購入だけど。 他環境向けのCソース生成ならこちらのほうがよい?(夢見てるかも)... といっても、ターゲット環境ごとの個別対応は必要だろうで、 Comeauのサイトで対応と書かれているのは比較的メジャーな環境のみのよう。




2010-3-21[日] LLVM lli での実行

そういや LLVM の VM(lli) ってどれくらいなんだろうか、とちょっと気になったので 3/12のを lli で実行してみた。

llvm-gccでコンパイルして、 llc で生成したネイティブアセンブラソースからexeを作ったもの、と、 lli で実行したもの。 llcからのexe結果は不精して、前回のからコピペ。 今回試した lli はそのときより数日新しいllvmになっていたり 多少測定環境がぶれていたりするけれど、おおざっぱな雰囲気をみる分には...で。 (ソース&exe)

コンパイラBilinear 拡大(ミリ秒)安易 インタプリタ(秒)quick sort(μ秒)QSORT(μ秒)Dhrystone/secWhetstone (MWIPS)
llcでasm→exe105.827.61987135860(25056376)1525.463
lliで実行 103.626.01749939343(26184864)1530.688

大筋 lliの実行結果は llc でネイティブアセンブラ生成した場合と同様の結果のよう…

仕組みからすれば、lliのほうは測定範囲外の部分で余分に時間かかってる (実行時コンパイルしてる)だろうが、 .bcサイズに対する今時の実行環境のパワーを思えば たいしてペナルティがあるわけでなく、ってとこ、か? ( ロード時に一括コンパイルしているのかな?)

ネイティブ実行以外興味なくて、最初にちょろっと試しただけで、以外に速いかも なんて思ってたのだけど、以外に、どころじゃ、なかった。

LLVM関係の記事(appleのopenglな件とか)に書かれていることを思い返せば、 こういうことなんだろうけど、実感してなかった、というか、わかってなかったことを実感です。




<<20092011>>