まんぼう日記

takataka's diary

件数不明のデータを読み込みつつメモリ確保するにはどうするのがよい?

プログラミングの授業の課題をあらかじめ大学院生のティーチングアシスタント(TA)のみなさんにやってもらってるんですが,そこでの議論からタイトルにあげたような疑問が湧いたので,ちょっと実験してみた,って話です.たかたかはアルゴリズムとかコンピュータシステムの専門家やないので,たぶん怪しいとこいっぱいありますよ.

 

授業で扱ってるのは,以下のような12万件強の郵便番号データです.

6148062 京都府八幡市八幡清水井
   :
5040924 岐阜県各務原市下切町

これを fscanf で読み込んで郵便番号をキーとして探索するプログラムを作るってのが課題です.授業ではメモリの動的確保なんか教えたりしませんので,データ件数そのものは不明でもデータ件数の上限は既知であるとして,大きめに確保した配列に格納するように作ればokなんです.ところが,TAさんのひとりが,データ件数未知の条件で,malloc使ってメモリを動的確保しながら読み込むプログラムを作ってくれました.しかも,効率を考えて,読み込んだデータ件数が増えるとともに2倍のサイズのメモリを再確保するようにしたもの(たぶんアルゴリズムの教科書なんかに載ってると思います).

 

そのプログラムを眺めてたら,単純にデータを二度読みするんとの違い(主に実行に要する時間の意味でね)が実感できるほどあるんやろか,というのが気になった次第です.一度データを最後まで読んでデータ件数を数える ==> 必要なメモリ領域を確保 ==> 再度データを先頭から読んで代入,ってのでもええんちゃうかと…

 

というわけで,実際にプログラムを動かして時間を測ってみました.

実験条件

実験条件はこんな感じ:

  • Mac mini (mid 2011), Intel Core i7 2.7GHz, メモリ 16GB
  • OS X Mouintain Lion
  • データファイルの置き場所は,内蔵SSDとThunderbold接続のHDDの二通り
  • データファイルは,上記の12万件強のテキストデータを cat で64倍に水増しした 7786688 件,319MB のテキストファイル

二度読みするプログラム hoge1.c

一度ファイルを読んでデータ件数を数えてから,rewind して読み込み直すようにしたもの.

二倍の領域をreallocしていくプログラム hoge2.c

myreallocx2 関数を呼ぶと,以前の領域の2倍のサイズの領域をmallocし,これまでの内容をそちらの前半にコピーします.

共通のサブルーチン

hoge.h

hoge.c

実験結果

まずは外付けHDDにデータファイルを置いた場合の結果です.

$ ./hoge1
# n = 7786688
# counting: 2.372243 [sec]
# malloc: 0.000038 [sec]
# reading: 3.796808 [sec]
# total: 6.169089 [sec]
5040924 岐阜県各務原市下切町

hoge1.c の結果は上記の通り.malloc にはほとんど時間がかかってません.合計の経過時間は6.2秒でした.

$ ./hoge2
# n = 7786688, ncap = 8388608
# reading: 6.115480 [sec]
#    myreallocx2: 2.323665 [sec]
5040924 岐阜県各務原市下切町

こちらは,hoge2.c の結果.reading の値が全体の経過時間で,6.1秒でした.そのうち,myreallocx2 に要した時間が2.3秒.おそらく memcpy に時間がかかってるものと思われます.それ以外の時間は,hoge1 の reading の時間とほぼ同じです.この実験では hoge1 のcounting と hoge2 の myreallocx2 にかかった時間がたまたま同程度だったので,両者のトータルでの経過時間がほぼ同じになったということです.

 

内蔵SSDにデータファイルを置いた場合も,かかった時間はほとんど同じでしたので,結果は省略します.

 

それから,元々たかたかが二度読みでいいんじゃねって思ったのは,「OSが一度読んだファイルの内容をメモリ上にキャッシュするやろから,二度目のアクセスが速くなって…」ということを想定してたんですが,実験ではその効果は見えませんでした.データファイルを作った直後にプログラムを実行した時と,何度も実行した後で再度実行した時とで,結果に違いは見られませんでしたので.

結論

というわけで,理論的には hoge2 の方はほぼ定数時間の手法やからうれしいとはいえ,結局はhoge1 の二度読みで十分やんってことになりました.ただ,この実験条件ではそうなった,ちう話でしかないので,一般化するのは危険でしょう.そもそも,「ストリームデータやからいっぺんしか読めへんぞ」ってこともあるでしょうし,1件のデータがもっと複雑な構造をしてる場合,データサイズに対して必要な myreallocx2 の回数が相対的に減るので,もっと効率良くなるでしょうし.細かい所では,hoge2 では領域サイズの初期値を1にしてる所をもっと大きくして,myreallocx2 の回数を減らすとか(大きな領域のmemcpyが支配的なんやったら意味ないですが).