Hatena::ブログ(Diary)

純粋関数型雑記帳 このページをアンテナに追加 RSSフィード Twitter

このページはHaskellを愛でるページです。
日刊形式でHaskellなどについての記事をだらだらと掲載しとります。
2004 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 06 | 07 | 08 | 09 | 11 |
2007 | 03 | 04 | 05 | 07 | 08 | 09 | 12 |
2008 | 02 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 03 | 05 | 06 | 09 | 10 | 11 | 12 |
2010 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 12 |
2011 | 01 | 02 | 05 |
本体サイト

2008年12月23日(火) C++のstreamの転送速度を調べる

C++初心者の私がC++をやめたくなった瞬間。

なにをいまさらな。

[]C++のstreamの転送速度を調べる C++のstreamの転送速度を調べるを含むブックマーク C++のstreamの転送速度を調べるのブックマークコメント

はじめに

C++のstreamはとても良くできていて、これを用いたライブラリを作りたいのだけど、

本当に(主にパフォーマンス的な理由で)大丈夫なのとかそういう話。

初めにお断りしておきますが、以下の内容はすべてlinux+gcc4.3での話です。

streamは遅い

ふつうにistreamからget()して、ostreamにputしてるとめちゃくちゃ遅い。

C言語のgetchar, putcharより10進数で1.5桁ぐらい遅いよ。

istream::readとかででかいブロック読めば大丈夫なのだけど、

細かい単位で読みたいことの方が多いよね。

そういうわけで、そういう場合にも速く転送することが可能なのかどうか調べてみる。

テストプログラム

istreamの内容をostreamに転送するプログラムを6通り書いた。

その1:普通プログラム

オーソドックスプログラム

void copy1(ostream &os, istream &is)
{
  for (char c; is.get(c); os<<c);
}
その2:ブロックごとに読み書き

今回の趣旨には会わないが速度の比較のため。

(readに失敗したときの処理があってるのか不明)

void copy2(ostream &os, istream &is)
{
  for (;;){
    char buf[1024];
    if (!is.read(buf, 1024))
      break;
    os.write(buf, 1024);
  }
  copy1(os, is);
}
その3:istream_iteratorを使う

is>>c; os<<c;と同じような意味だろうから、

空白がとばされてるような気がするので、

入力には空白は入れないように配慮。

void copy3(ostream &os, istream &is)
{
  istream_iterator<char> p(is), end;
  ostream_iterator<char> q(os);
  copy(p, end, q);
}
その4:istreambuf_iteratorを使う

Effective STLおすすめの方法。

空白は大丈夫です。

void copy4(ostream &os, istream &is)
{
  istreambuf_iterator<char> p(is), end;
  ostreambuf_iterator<char> q(os);
  copy(p, end, q);
}
その5:ostreamにstreambufを突っ込む

あんまり柔軟性は無いけど、

この書き方がどのぐらいの速度なのか調べたかった。

void copy5(ostream &os, istream &is)
{
  os<<is.rdbuf();
}
その6:istreamからstreambufに突っ込む

5と同じぐらいの速度になるという予測

void copy6(ostream &os, istream &is)
{
  is>>os.rdbuf();
}

六つ書いたけど、期待しているのはその4だけです。

これがどういうケースで速くなるのかを調べたい。

テスト

これらのルーチンを、ifstream&ofstreamと、cin&cout、

さらにそれぞれ組み合わせと、出力が/dev/nullになってるときの

計8通りでテスト単位は秒。

ファイルサイズは1GB、

メモリ8GBのマシンにおいて実行。

ファイルの内容はキャッシュにすべて乗った状況ですので、

純粋CPUの計算量のみが考慮されるものと考えてください。

file -> file(普通ファイル)
copy1 40.310
copy2 3.340
copy3 46.900
copy4 1.550
copy5 1.870
copy6 1.620
file -> file(/dev/null)
copy1 38.610
copy2 0.880
copy3 45.390
copy4 0.400
copy5 0.390
copy6 0.410
file -> stdout(普通ファイルリダイレクト)
copy1 47.780
copy2 3.560
copy3 53.990
copy4 3.330
copy5 4.120
copy6 4.060
file -> stdout(/dev/nullにリダイレクト)
copy1 56.530
copy2 0.700
copy3 66.580
copy4 0.510
copy5 0.500
copy6 0.510
stdin -> file
copy1 69.860
copy2 3.390
copy3 98.580
copy4 34.540
copy5 35.980
copy6 34.880
stdin -> /dev/null
copy1 68.000
copy2 0.890
copy3 100.190
copy4 34.180
copy5 34.040
copy6 34.410
stdin -> stdout(file)
copy1 とても長い(>300)
copy2 6.080
copy3 とても長い
copy4 46.160
copy5 70.310
copy6 70.530
stdin -> stdout(/dev/null)
copy1 とても長い
copy2 0.870
copy3 とても長い
copy4 44.830
copy5 44.210
copy6 44.350

とても長いと書いてあるところは、長すぎたので切りました。

5分で切りましたが、多分10分たってもおわらないのじゃないかな。

考察

出力が/dev/nullか普通ファイルかは当然/dev/nullの方が速いものの、

systemの時間が変わるだけです。

計測する必要なかったな。


ブロック転送(copy2)はすべてにおいて速い。

これも当然ながら。


copy1はすべてにおいて遅い。

当然ながらほとんどuser時間


copy4,5,6は同じぐらいの速度になった。

streambuf_iteratorだけ遅いという結果にならなくてよかった。

標準入力->標準出力で4と5,6で結果がだいぶ違う原因は不明。


以下はstreambuf_iteratorについて。

入力がifstreamの時はおしなべて速い。

入力がcinの時は速くない。

でも、cin.get()とかで読み取るよりは速い。


出力はofstreamでcoutでも大差はなし。

どちらかというとofstreamを使う方が速いようだ。


cin, coutが実際どういう型になっているのかは知らないが、

まあ実装がfstreamと違うのだろう。


速度の違いの理由を調べるため、straceをかけてみた。

基本的にどれもある程度まとまってread/writeされていた。

(サイズは8KB,4KB,1KB様々だが)

つまり、速度の違いはそれ以外のオーバーヘッドである。

しかし、許容しがたいほど遅かったもの(cin->coutのcopy1,3)は

出力が一文字ずつwriteされていた。

これは如何に。

ファイルからcoutへ転送する場合も再度調べたが、

たしかにバッファリングされている。

同じcoutへの出力なのになぜ?


調べるために、次の2つのコードを書いた。

for (char c; cin.get(c); ) cout<<c;
ifstream ifs("tmp");
for (char c; ifs.get(c); ) cout<<c;

すると、やはり、なんと、前者はバッファリングされず、後者はされるのだ。

私はこの結果を見たとき、

もうC++とはとっととおさらばしてユートピアへ行こう!

と思わずにはいられなかった。

今回この原因を探るのはめんどいのでしないが、

まあそのうち調べたいと思う。というか、調べないといかんのだろうなあ。


read/writeとの比較

FD間で直接転送した場合と比べてどうなのかを調べてみた。

void fdcopy(int to, int from)
{
  char buf[1024*8];
  for (int n; (n=read(from, buf, sizeof(buf)))>0; ){
    char *p=buf, *q=p+n;
    while(p<q){
	ssize_t ret=write(to, p, q-p);
	assert(ret>0);
	p+=ret;
    }
  }
}
結果
file-> file 1.280
file -> /dev/null 0.390
stdin -> stdout 2.430
stdin -> stdout(/dev/null) 0.380

streambuf_iteratorのオーバーヘッドは1割程度と言うことになる。

(バッファのサイズが違ったりするので、単純には言えないけども)

まとめ

まとめて読むことが可能なら、istream::read(), ostream::write()を使おう。


cinからのistreambuf_iterator経由での入力はあまり速くない。

でも、get()などを呼ぶことに比べたら速い。

ifstreamからのistreambuf_iteratorはとても速い。


ostreambuf_iteratorは大体とても速い。


結論としては、streambuf_iteratorは十分速い、十分使える。

つまり、stream使っといて大丈夫

としとし 2008/12/24 09:18 コンパイルオプションが載っていないんですが

コンパイルオプションを変えると
遅い方法でもコンパイラがよろしく最適化してくれて
十分な速度で実行されたりしますか?

tanakhtanakh 2008/12/24 18:30 上のはすべて-O2による結果です。-O0にするとuser時間が大体すべて倍ほどになりましたがそのぐらいでした。ですので最適化してくれて十分な速度で、ということはないと思います。

herumiherumi 2008/12/26 21:55 mainの直後に
std::cin.tie(0);
std::ios::sync_with_stdio(false);
を入れてベンチマークとったらどうなるでしょうか.

ocean-cityocean-city 2009/01/03 16:01 http://www.cplusplus.com/reference/iostream/ios/tie.html
ですね。
>The tied stream is another output stream object which is
>flushed before each i/o operation in this stream object.
がいかにも怪しい。

トラックバック - http://d.hatena.ne.jp/tanakh/20081223

2008年12月21日(日) Google Coe Jam 2008 World Finals

なんかここのところの週末は他にやりたいことがあって、

文章を書きかけですっかり忘れていたら、

完全に時期を逃した感がありますが、

今更ながら参加記を記しておきます。

[]Google Coe Jam 2008 World Finals Google Coe Jam 2008 World Finalsを含むブックマーク Google Coe Jam 2008 World Finalsのブックマークコメント

http://code.google.com/intl/ja/codejam/

f:id:tanakh:20081118024325j:image:w320

というわけで、参加してきました。

結果はSmall全部+A-Largeの36点で43位でした。

英語が全く駄目な私にとっては、無事に帰ってこれただけで奇跡なので、

あまり高望みはしますまい…。

サンフランシスコ

コンテスト本番以外には特にイベントのないCode Jam

着いた次の日の午前9時から開始というキツキツのスケジュールなのですが、

それは疲れそうだったので、私は一日前から現地入りしました。

終わった後もせっかくサンフランシスコまで行って何もせずにというのは

あんまりなので、一日延長しました。

これがなぜかフライトに有利に働いて、

ほかの人たちは韓国経由とかでやってきているところを

悠々と成田サンフランシスコ直通便で行けました。


ひとりで海外に行くのは初めてだったのでとても不安でした。

なにしろ言葉が通じませんのでね。

しかし、必要に迫られて頑張ってみると、

案外コミュニケーションはとれるもので、

通じなくてどうしようもない、という状況はおきませんでした。

だいぶ経験値が上昇したような気がします。


クレジットカードを持ってなかったのも不安だったのですが、

これもまあ何とかなりました。

15万円持って行った現金は2万円+200ドルぐらいしか残りませんでしたので、

ちょっと何かがあったらまずかったかもしれません。

最初に日本で5万円両替して、500ドル弱手に入れたのですが、

ホテルに着いたらデポジットが700ドルいるとか言われて、

向こうでドルを調達したら5万円が400ドル弱にしかならなくて、悶絶しました。

私の1万円はどこかに消し飛んだようです。


Google

さて、そんなわけで、レジストレーションとか立食パーティーみたいなのがあった翌日、

ついに本番となりました。

朝6時半ホテル出発の9時コンテストスタートです。

いきなり厳しいですが、日本時間じゃないので何とかなりました。


サンフランシスコの街を抜け、海岸沿いのハイウェイをひたすら南下していくと

どんどん何もないところへと向い、

その何もないところの一角Googleはありました。

日本でいうと京阪奈みたいなもんなのかなあと思いました。


Google本社は、思っていたのとだいぶ違って、

きっとそれは日本Googleを先に見ていたからだと思うのですが、

広い敷地にあまり高くない建物がたくさん、

さしずめ大学キャンパスのようでありました。

食べるところがたくさんあって、そこらじゅうに自由に飲める飲み物が設置されていて、

中庭にはビーチバレーコートから恐竜化石までありました。


中国韓国かのテレビインタビューに来ていました。

軽い気持ちでOKOKとか言ってしまったのですが、

何聞いてきているか全然わからないし、

終始しどろもどろの対応で(自分が)ひどかったです。

解答は日本語でOKですよ、みたいなことを言われたので

日本語で答えておきましたが、たぶんインタビュアーの人は

日本語わかっていないので、かみ合わない妙な雰囲気のまま終了。


コンテストの会場は、食堂の横のスペースに設営されていました。

たぶん食べるところだったのだと思うのですが、

そんなオープンなスペースでコンテストは始まりました。


本番

持参した日本語キーボードを取り付けたり、GNOMEの設定を変えたり、

テンプレートコンパイルできることを確認したりして、開始を待ちました。


画面上にカウントダウンが表示され、それが00:00になってコンテストは開始しました。

開始しても会場はシーンと静まり返っており、

あれ、これ始ってるの?と不安になりましたが、

Enter Contestというボタンを押すと問題が見れたので、

確かに始まっているのだということがわかりました。


(問題はこちらを参照)

http://code.google.com/codejam/contest/dashboard?c=agdjb2RlamFtchALEghjb250ZXN0cxjRzBQM


この日の戦略はノープランでした。

何をどうしたらいいか何も考えていなかったので、

とりあえずAを読みました。

読み始めたは良いものの、全然頭に入ってこなくて参りました。

英語が難しいのか、問題のシチュエーション現実離れしているから

想像で補うことができないからか、とても解読に苦労して、

やはり例によって例の如く、読んでる最中にサブミットがされ始めました。

10分ぐらい経ってようやくなんとかサンプルと整合性のとれる理解が得られたのですが、

それでもそれが合っているか分からなかったので、

英語の理解を確信にするためにとりあえずSmallのコードを書くことにしました。

コードは数分で書き終わり、サブミットするとCorrectと帰ってきました。

よかった。理解は間違っていなかった。

Largeの解法は思いつかなかったので解く問題をBに変更。


Bも英文が全然頭に入ってこなくて参りました。

これもシチュエーションが不自然すぎるのです。

なんでネズミ捕りなのか意味がわかりません。

これもとりあえずSmallを通すことにしました。

普通に深さ優先的にペイントして終了。

Largeは計算しないとできなさそうだなあと思ったのでCに移動。


Cは問題文が素直で助かりました。

しかしLargeの解法はまるで思いつかなかったので

とりあえず全部調べろといわんばかりのSmallを適当に通しておきました。

この辺までは一問15分ペース


残るDとEは問題が長かったので、とりあえずDから手をつけることに。

Smallの解法も自明ではないように思えましたが、

少し考えると、とりあえずもう一つの森まで最短でつないで、

あとはBFSのminをとればいいように思えたのでそれを実装。

しかしなんだかコードがすっきりしなくて、

どろどろしてきたので、一旦Eにスイッチ


Eもシチュエーション現実離れしすぎていましたが、

解読は普通に終わり、Smallもできそうな感じでした。

15*2^15*2^15*15ぐらいの計算量だったので、不安もありましたが

ぐずぐずもしていられないので、実装を始めました。

コード自体はすぐにできて、サブミットしようとしたのですが、

テストケースを持ってきて、実行させてみると全然間に合わない。

これはやばいかなと思いつつ、

スコアの計算などをビットごとにループを回していた部分をテーブル引きに変えたり、

生成したパターンが有効かどうかのチェックもテーブル引きに変えたりして

15の係数を一つはずして、サンプルを再入力

4スレッド並列で3分ぐらいで終わったので、行けるだろう、として、

二つ目のサンプルをサブミット、やっとこさSmallが通る。

かなり時間を消耗してしまいました。

この辺で残り一時間ぐらい。圧倒的に時間が足りない。


一通り問題を見たのでDに戻る。

ちょっとコードから離れていたので、見通しが良くなっていました。

するするとかけて、するすると終了。

さっき書いてた時に感じたのはなんだったんだろう。

そして残り45分ぐらい。


Smallが終わって、次に何をやるか。

といってももう全然時間がないので絞らないといけません。

解けそうなのはDのLarge。

Smallと同じような感じで、

森を全部spanning treeつないで、それから全森からのBFSのminでいいような気がしたのですが、

なんだかすっきり書く方法が思いつかず、17点というのも

本当にこんなんでいいのかという気にさせてくれて、やっぱりDはやめることに。

あと解けそうなのはAのLargeとBのLargeか。

AのLargeはかなりたくさんの人が解いていたので、

これはやるべきだろう、ということでAを考え始めました。


ジュースをミックスする割合を決めて、それぞれについてチェックしたらO(n^3)か。

これはn=5000には大きすぎる。

割合を決めるのにO(n^2)、あとは決めた時のカウントがO(1)かO(logn)かで

できれば何とかなると考えて、10分ほどうんうん唸っていると、

fenwick treeでできるんじゃないか、と気付きました。

分かったらコードはすぐできて、

しかし、万が一にもTLEなどあってはならないので、

手元で大きなケースを作って、

それでも十分に速いことを確認して石橋をたたきながらLargeをサブミット。


残りは15分。もう解法が今すぐに思いついても一問も

書けないような気はしていたのですが、

一番可能性の高そうなBを考えることにしました。

しかし考えてもいい案は浮かばず。

Dがもしかしたらすっきりいけるのかなあと思いながらDを眺めてみるも

これまた何も浮かばず。


そんなこんなで、ぐだぐだしながらのこり15分を過ごしました。

終わる時もあっさりと終了。カウントダウンぐらいあってもよかったんじゃなかろうか。


終了後

終わって一息ついていると、

今度は日本記者インタビューしたいらしいとのことなので、

これまたOKOKとか言っているとなんか別室に連れていかれて

そこでインタビューを受けました。

今度は日本人の方だったので、普通日本語で対応しました。

外国でこう日本語で受け答えするのって、

ちょっと不思議な感じで、ちょっと楽しかったです。


それからご飯を食べたり日本人で集まって解法を言い合ったりしました。

Googleの食堂はいろいろな国の料理があって、なかなかおいしかったです。

もちろん和食もあって、と言っても寿司なのですが、

せっかくなのでカリフォルニア寿司も食べておくことにしました。

目の前でサーモンの握りを握ってくれて結構本格的なんだなあと思いました。

味も結構ちゃんとしていました。

どうでもいいのですが、サンフランシスコの街には妙に寿司屋が多くて、

3分歩けば必ず見つかるほどです。

日本でもそんなにないと思うのですが、

よほどサンフランシスカンは寿司が好きなのでしょうか。


食事が終って、社内を見学したり、

Google技術の説明を聞いたりしました。

イベントがほとんどないのに、そういうアピールはするのだなあと思いました。

途中、Java Puzzlersという本?からJavaの奇妙なふるまいについての話がありました。

私はJavaはほとんど使わないので、そんな重箱の隅仕様は知っているはずもなく、

なんでアメリカくんだりまで行ってJava勉強をせねばならないのかなあ、と思いました。


それからホテルに帰って、表彰式でした。

アルコールが出たので、もらいに行くとIDを要求されました。

まあなんというか、年齢制限のあるものなのだからこれぐらいは当然なのか。

ディナーを食べながら下のほうから順に発表されていきます。

とりあえず97位から51位までには入っていなくてホッとしました。

AのLargeは通っていたっぽい。

しかし、次の50位から26位で名前が出て来て

やっぱりこんなもんだよなあという感じでした。

1位はACRush氏でした。鉄板過ぎる。

89点というのが自分との如何ともし難い距離を感じさせます。

久しぶりに、悔しいという気持ちが沸いてきました。

勝ちたい、終わってからだというのに。

来年ももしあればもっと自分を鍛えて行きたいと思いました。


観光

一日延泊して観光してきました。

サンフランシスコは坂が多い街です。

東京もたいがい凸凹した街だなあと思っていたのですが、

比べ物にならないぐらい坂だらけです。

f:id:tanakh:20081113070045j:image:w320

とりあえず、坂道をがんばって歩いて日本人街に行ってみました。

あまりにも日本でびっくり。

紀伊国屋書店があったのですが、内装から置いてある本までどうみても日本で、

とても奇妙な感覚でした。

それから中華街とかを見て、

名物のケーブルカーに乗りフィッシャーマンズワーフに向かいました。

ガイドブックに載ってた、フィッシャーマンズワーフで自転車を借りて、

ゴールデンゲートブリッジ自転車で渡る、というやつをやりました。

英語がなかなか聞き取れなくて、自転車を借りるのに一苦労。

クレジットカード持ってないの?持ってないけどそこを何とか貸してくれ。

なんか店長みたいな人に話が行って、クレジットカードは?ないです。

うーん。とか何とか話が進んで、

じゃあ300ドル出せという話になったのですが、

所持金が260ドルしかない。

ちょっとそんなにお金ないです、と言ったら、

じゃあそれでいいやということになって、全財産と引き換えに

自転車を借りることができました。

閉店までに帰ってこなかったらお金返せない、

しかも閉店まで2時間ぐらいしかないという状況だったのですが、

がんばって自転車を漕いで、何とか間に合いました。

アメリカまで来てこんな危ない橋を渡る必要もなかったかなあ。

自転車は結構良くて、なんとGPS付きでした。

f:id:tanakh:20081116081720j:image:w320

橋は結構高い所にかかってて、そこまで登るのにも一苦労。

橋からの眺めはなかなか爽快でした。

良い経験ができました。

f:id:tanakh:20081116082812j:image:w320

そのあとはフィッシャーマンズワーフで買い物とかして、

書店マンガとか買ってみたりして、ホテルに帰りました。


終わって

サンフランシスコに行けたのはいい刺激になりました。

自分プログラミング能力でこういう大会に出れたのはかなりの久しぶりでしたし、

そういうところに出て、中ほどの成績が取れたのは、

まだまだ自分も捨てたもんじゃないなと思えるようになりました。

TopCoderSRMは負けたときが悔しすぎるので

以前負けてから全然参加してなかったのですが、

今後はリハビリ意味もこめて積極的に参加して行きたいと思います。