Hatena::ブログ(Diary)

やた@はてな日記

2010-07-26

C/C++ におけるデータ入力の速度

100 万行のテキストファイル(test-data)を C/C++ で作成したプログラムで読み込むとき,どのくらいの時間がかかるかを調べた結果です.

データ入力がボトルネックになるような状況では,std::fgets(), std::fread(), std::istream::read() を使った方が良さそうです.std::istream については特に極端な差が出ていますので,速度面を重視する場合,便利なインタフェースを封印しないとダメっぽいです.実に惜しい….

追記(2010-07-28):id:metaboles さんより,std::ios::sync_with_stdio(false) を使えば std::cin.getline() や std::getline() も std::fgets() と同じくらい速くなるというコメントをいただきました(後述).

$ wc test-data
 1000000   990919 97251910 test-data
入力方法 time -f 'real %E, user %U, sys %S'速度 [MB/s]
std::fgetc() real 0:01.38, user 1.34, sys 0.04 70.47
std::getchar() real 0:01.40, user 1.31, sys 0.07 69.47
std::istream::get() real 0:06.22, user 6.08, sys 0.04 15.64
std::istream::operator>>(char &) real 0:10.22, user 9.90, sys 0.03 9.52
std::istream::operator>>(std::string &)real 0:05.97, user 5.82, sys 0.0416.29
std::fgets() real 0:00.18, user 0.16, sys 0.02 540.29
std::istream::getline() real 0:05.56, user 5.40, sys 0.08 17.49
std::getline() real 0:05.82, user 5.70, sys 0.05 16.71
std::fread() real 0:00.04, user 0.00, sys 0.05 2,431.30
std::istream::read() real 0:00.04, user 0.00, sys 0.05 2,431.30

※ テキストファイルがキャッシュされている状態で実行しています.

実験に使ったソースコードはこちら(http://sites.google.com/site/headdythehero/cabine/2010/0725/measure-input-speed.tar.gz?attredirects=0&d=1)にあります.かなり適当です(もちろん悪い意味で…).

増補版(2010-07-28)

std::setvbuf() や std::ios_base::sync_with_stdio() を使うと速度が上がるというコメントをいただいたので,条件をいろいろと追加して再実験しました.おまけとして,入力データを 1000 万行に増やしています.

結果を見る限り,std::setvbuf() の影響は小さいようです.といっても,標準入力からデータを受け取るだけのプログラムなので,バッファのサイズを大きくしてデータを先読みする旨味がなかったことが理由だと思います.入力が複数あったり,入力の合間に何らかの処理をおこなうようなプログラムであれば,効果がありそうです.

一方,std::ios_base::sync_with_stdio() については,劇的に速度が改善されました.std::getline() や std::cin.getline() の速度は 300 倍くらいになっています.std::fgets() と比べて少し遅いくらいなので,十分に実用的な速度が出ています.

感謝:n-yo さん,id:metaboles さん

wc test-data
 10000000   9910931 975315208 test-data
関数補足 ※realusersys速度 [MB/s]
std::fgetc - 0:13.8513.310.40 70.42
std::getchar - 0:13.7513.400.34 70.93
std::cin.get - 0:59.3058.930.32 16.45
std::cin.get nosync 0:24.7923.970.42 39.34
::operator>>char 1:39.9398.360.42 9.76
::operator>>char, nosync 0:31.9531.180.40 30.53
::operator>>std::string 0:58.9557.740.32 16.54
::opreator>>std::string, nosync0:04.34 3.820.38 224.73
std::fgets - 0:01.71 1.320.36 570.36
std::fgets _IOLBF 0:01.71 1.300.37 570.36
std::fgets _IOFBF 0:01.70 1.360.29 573.71
std::cin.getline - 0:55.0154.170.29 1.77
std::cin.getline nosync 0:01.88 1.560.32 518.48
std::getline - 0:57.2356.820.25 1.70
std::getline nosync 0:02.07 1.670.40 471.17
std::fread - 0:00.35 0.000.362786.61
std::fread _IONBF 0:00.35 0.010.342786.61
std::fread _IOFBF 0:00.47 0.140.332075.14
std::cin.read - 0:00.37 0.040.332635.99
::LineReader.read 自作 0:01.99 1.570.42 490.11

※ 1. nosync: std::ios_base::sync_with_stdio(false)

※ 2. _IONBF: std::setvbuf(stdin, NULL, _IONBF, 0)

※ 3. _IOLBF: std::setvbuf(stdin, io_buf, _IOLBF, 1048576)

※ 4. _IOFBF: std::setvbuf(stdin, io_buf, _IOFBF, 1048576)

※ 5. real, user, sys: time -f 'real %E, user %U, sys %S'

# sync_with_stdio() については,std::ios::sync_with_stdio() という呼び出しの他,ストリーム単位で std::cin.sync_with_stdio() という呼び出しもできるようです.

n-yon-yo 2010/07/26 21:17 行読み込みで速度重視なら,std::fgets 一択ですよね.といいつつ自分は std::fgets はバッファが固定長なのがやや気持ち悪いので,環境依存なのを知りながらも読み込みバッファを自動拡張する getline (LINUX 系) や fgetln (BSD 系) を使っています (FILE* を引数に取るもの).std::fgets と同等以上に速く,読み込んだ長さが同時に得られるので,後々の処理で std::strlen しなくて良いのも有利です.

setvbuf(ストリーム系なら,setbuf)で入出力用のバッファを1Mぐらいとるともう少し速くなるようです.

s-yatas-yata 2010/07/26 21:57 本文で挙げている方法の中から選ぶとすれば,std::fgets() がベストだと思います.といいつつ私は,行入力専用の自作クラス(内部で std::istream::read() を使用)を使っています.環境に依存しませんし,長さも取得できますし,メモリ管理もクラス側に組み込めるので,使う段階になると楽です.ただし,ブロック単位で読み込んでしまうため,対話的なインタフェースの提供には使えないという欠点があります.

フィルタ(boost など)を通してやれば圧縮ファイルにも適用できるという点は,std::istream の利点になると思います.

getline() や fgetln() は使ったことがありませんでした.参考になります.

n-yon-yo 2010/07/27 13:58 なるほど.確かに自作するのが一番ですね.どれぐらいのスループットが出るのか気になります(std::fgets より速くなったりして).fgetln も getline も関数が自動でバッファを再確保するので,バッファを free しないとメモリリークしたりします(大した問題はないですが).
しかし,ストリーム用の std::getline() が遅いのがとても残念ですね.何故こんなに遅いのか・・・std::string を使っているせいでしょうか.
添付ファイルを手元で試したところ,fgets (real 0m0.301s) に比べて fgetln は1割程度少ない時間 (real 0m0.267s) で済み,入力バッファを setvbuf で 1M にした fgetln だと4割程度少ない時間 (real 0m0.188s) で済みました.入力バッファを setvbuf で 1M にした fread には (real 0m0.063s) 遠く及びませんが,通常の fread (real 0m0.140s) には迫っています.

s-yatas-yata 2010/07/27 15:18 > 自作
試してみたところ,std::fgets() と同じくらい(遅かったり速かったり)の速度になりました.おそらく,::getline() より遅いと思います.とはいえ,std::fgets() くらいの速度があれば,データ入力以外の部分がボトルネックになることは疑いなく,あまり気にしなくても良いと思います.

> バッファを free しないとメモリリーク
::getline() を呼び出す簡単なクラスを用意すると良いのかもしれませんね.

> std::getline() は何故こんなに遅いのか
ヘッダを見たところ,std::getline() は std::streambuf の sgetc(), sbumpc(), snext() を使っていました.std::fgets() などとは異なり,上層で行単位の入力を実現しているため,バイト単位の入力を用いることになっているようです.これが原因と見て間違いないと思います.

metabolesmetaboles 2010/07/28 02:48 SGI の実装から派生した,STLport や libstdc++ であれば,
std::ios_base::sync_with_stdio(false);
を最初の行に記述することで,std::getline() 等のパフォーマンスを大幅に改善できると思います.
実際に試せる環境にないのですが,std::fgets() と同程度とは行かないまでも,かなり近い速度が期待できます.

デフォルトでは,std::cin,std::cout,std::cerr や std::clog 等のストリームは C の対応するストリームと同期して動作するようになっています.
この場合,各ストリームクラスは,その下層にある std::streambuf の派生クラスを通じて C の stdio の関数を呼び出すことが多いようです.

一方,std::sync_with_stdio() に false を指定して呼び出すと,std::cin 等のストリームが使用する std::streambuf 派生クラスが別の実装に切り替わり,C の stdio の関数を経由する必要性がなくなります.
このことが,スレッド間の同期の粒度や,バッファリングに対して,実装の最適化を許すこととなり,パフォーマンスの改善につながっているのだと思います.

なお,Dinkumware による実装においては,そのソースコードのコメントにあるとおり,std::sync_with_stdio() の呼び出しは意味がないようです.

s-yatas-yata 2010/07/28 11:44 > metaboles さん
情報ありがとうございます.std::ios_base::sync_with_stdio(false); でパフォーマンスが大幅に改善することを確認しました.

std::cin などの中身がそのようになっていることは知りませんでした.今回のことで,以前からの疑問が一つ解消されました.でも,これって完全にバッドノウハウ(http://0xcc.net/misc/bad-knowhow.html)のような気が….

C 言語から C++ への移行を戸惑わせる理由の一つがバッドノウハウの多さだと思うので,なんとも微妙な気分になってしまいます.

n-yon-yo 2010/07/30 12:41 c を経験せず,いきなり c++ を学んだ人は,そもそもハマっていることにも気がつかないでいることが多そうです.c++ ではライブラリが高度化している関係か,処理系による実装の違いでハマるケースもよくありますよね.自分が過去に経験したのは,
- gcc の独自実装の _gnu_cxx::hash <const char*> の実装が腐っている (multiplier が 5!)
- 古典的でダメと言われる std::rand () が,LINUX 系では std::random () に置き換えられているのに BSD 系ではそのまま.
とかですが,気がつくと嬉しい半面,結構凹みます(ライブラリを使うのに嫌気がさして,c++ を使っているのにどんどんプログラムは c に回帰していく).

s-yatas-yata 2010/07/30 18:26 > c を経験せず,いきなり c++ を学んだ人は…
たしかに,最初から std::getline() を使っているような場合,比較対象がないから,遅いかどうかの判断も難しいかもしれませんね.

> std::rand() …
一時期は Mersenne Twister を使っていたのですが,疑似乱数の質に大してこだわらないときは std::rand() をそのまま使っていることも….
別件ですが,以前,RAND_MAX が 65535 だったために嵌ったことがあるような気がします.

> ライブラリを使うのに嫌気がさして…
ライブラリの裏情報もそうなのですが,C++ の多機能っぷりに端を発するインタフェースの多様性も,使いにくさの要因になっていると思います.
後,C++ の機能(継承やテンプレートなど)を導入すると,便利になる一方で,使える人が減ることも….

C++ は魔物(人をたぶらかすあやしい力をもつもの 大辞泉より)ですよ.

トラックバック - http://d.hatena.ne.jp/s-yata/20100726/1280138663