メモリー上で処理するよりもディスクに直接書き込む方が高速？ 86
ストーリー by headless
効率 部門より
効率 部門より
ソフトウェア開発者の間では一般的に、ディスクアクセスを避けてできるだけメモリー上で処理することが実行時間の短縮につながると考えられているが、これに逆行する研究結果をカナダ・カルガリー大学とブリティッシュコロンビア大学の研究チームが発表した(論文: PDF、
ITworldの記事、
本家/.)。
実験はJavaおよびPythonを使い、WindowsおよびLinux上で1バイト、10バイト、1,000バイトの文字列をそれぞれ100万バイトになるまで繰り返し結合し、結果をディスクに書き込むというもの。比較対象としては同じく1バイト、10バイト、1,000バイトの文字列を結合せずに計100万バイトになるまで直接ディスクに書き込んでいる。また、同じコードにより100万バイトの文字列を処理する実験も行っている。
その結果、Javaで1バイトの文字列を結合処理してからディスクに書き込んだ場合、ディスクへの直接書き込みと比べて約9,000倍の時間がかかったという。PythonではJavaほどの速度低下は見られなかったものの、直接書き込みの方がメモリー上での処理よりも数百倍高速だったとのこと。また、Linux上で実行したPythonのコードでは、元の文字列に新しい文字列を結合する方が新しい文字列に元の文字列を結合するよりも高速だったとしている。
論文ではこのような結果になった原因として、OSによるバッファリングがあるためにディスクへ直接書き込んでも速度がそれほど低下しないと指摘。また、OSのメモリー管理がメモリー上での処理を低下させる原因になる可能性もあるとし、開発者はOSやライブラリーなどについてより多くの知識を持つことでパフォーマンスを改善できるなどと結論付けている。ただし、論文の最後に掲載されているコードを見ればわかるように、文字列の結合には「+=」または「+」を使用しており、効率の良い処理を選択しているとはいえない。論文には「JavaではStringBuilderやStringBufferといったミュータブルなデータ型を使用すれば結果が大幅に改善する」といった記述もある。本家/.では結論に合わせた結果が出るように実験したのではないかとの指摘もみられるが、皆さんはどう思われるだろうか。
実験はJavaおよびPythonを使い、WindowsおよびLinux上で1バイト、10バイト、1,000バイトの文字列をそれぞれ100万バイトになるまで繰り返し結合し、結果をディスクに書き込むというもの。比較対象としては同じく1バイト、10バイト、1,000バイトの文字列を結合せずに計100万バイトになるまで直接ディスクに書き込んでいる。また、同じコードにより100万バイトの文字列を処理する実験も行っている。
その結果、Javaで1バイトの文字列を結合処理してからディスクに書き込んだ場合、ディスクへの直接書き込みと比べて約9,000倍の時間がかかったという。PythonではJavaほどの速度低下は見られなかったものの、直接書き込みの方がメモリー上での処理よりも数百倍高速だったとのこと。また、Linux上で実行したPythonのコードでは、元の文字列に新しい文字列を結合する方が新しい文字列に元の文字列を結合するよりも高速だったとしている。
論文ではこのような結果になった原因として、OSによるバッファリングがあるためにディスクへ直接書き込んでも速度がそれほど低下しないと指摘。また、OSのメモリー管理がメモリー上での処理を低下させる原因になる可能性もあるとし、開発者はOSやライブラリーなどについてより多くの知識を持つことでパフォーマンスを改善できるなどと結論付けている。ただし、論文の最後に掲載されているコードを見ればわかるように、文字列の結合には「+=」または「+」を使用しており、効率の良い処理を選択しているとはいえない。論文には「JavaではStringBuilderやStringBufferといったミュータブルなデータ型を使用すれば結果が大幅に改善する」といった記述もある。本家/.では結論に合わせた結果が出るように実験したのではないかとの指摘もみられるが、皆さんはどう思われるだろうか。
ソースはarXiv (スコア:5, 参考になる)
こんな釣りが査読を通ったの？ と思ったらarXivでした。
しかも、1st authorが生物学で、last authorが化学生物工学。何がどうしてこうなったのか教えてほしい。
Re:ソースはarXiv (スコア:3, おもしろおかしい)
たぶんセンサーから得たデータをCSVで書き込む時かなんかに大発見しちゃったのでは？
Re: (スコア:0)
そんな感じでしょうね。
書き出し処理が遅いや、メモリ上で処理するように書き換えよう→あれ? なんだか余計に遅くなったぞー、とか。
文字列結合なんて、適当にやってると、運悪くパフォーマンスの悪いやり方を踏むかどうかでかなり差が出る激戦区。
Re: (スコア:0)
ソースがarXivでも問題ないし、専門が生物学や化学生物工学の著者が別の分野で論文書いても問題ない。
この論文が眉唾なのは他のコメントでも指摘されてるとおりだけど、問題なのは論文の内容の妥当性であって、
arXivだとか著者の専門がどうとかいうことじゃないだろう。それじゃ低レベルな野次だ。
Re: (スコア:0)
まあ正論なんだが。しかしこの内容を見るとarXivから拾ってきたものを論文と言うなと言いたくなるわな。
論文というからにはある程度ちゃんとした査読プロセスを経ていないと。
Java版のコード見たら (スコア:5, すばらしい洞察)
ディスク書き込みにBufferedWriterクラスを使ってました。なのでJava版に関しては「直接ディスクに書き込んでいる」わけではありません。
Re:Java版のコード見たら (スコア:3, 参考になる)
C 言語的にいうとこんな感じでしょうか。だとすれば後者の方が断然速いですね。（ちょっとコードが意地悪かな）
#define MAX 1000000
void memory()
{
unsigned char* ptr;
size_t i;
FILE* f;
ptr = NULL;
for (i = 0; i MAX; i++) {
ptr = realloc(ptr, i + 1);
ptr[i] = '1';
}
f = fopen("tstm", "wb");
fwrite(ptr, 1, MAX, f);
fclose(f);
free(ptr);
}
void disk()
{
unsigned char buf[8096];
FILE* f;
size_t i, c;
f = fopen("tstd", "wb");
for (i = 0, c = 0; i MAX; i++, c++) {
if (c == sizeof(buf)) {
fwrite(buf, 1, c, f);
c = 0;
}
buf[c] = '1';
}
fwrite(buf, 1, c, f);
fclose(f);
}
Re:Java版のコード見たら (スコア:2)
https://gist.github.com/taku0/e68851bf357dda0f989c [github.com]
実際測ってみました。100万文字を書き込んでいます。
FileWriter: 約50 ms
BufferedWriter + FileWriter: 最初のうちは約30 ms、120回目ぐらいからJITが効いて13 ms
StringBuilder + FileWriter: 14 ms
CPU: Core i7 4500U
ストレージ: CFD販売 CSSD-M256HLHG5Q
OS: Linux 3.14.35 x86_64
JVM: Oracle JVM 1.8.0_40, server VM
途中sleep入れてるのはCPUが熱くなって遅くなるのを防ぐためです(本当は設定を変えてTurbo Boost等を無効にするのが正しいのですが手抜きです)。
Javaのヒープ領域 (スコア:2)
文字列にあわせて新しい領域をとるために遅いことはわかりますが、Javaのほうが遅いというのは、ヒープ領域が小さすぎて、
GCが多数回動いているからでしょうか？
Re:Javaのヒープ領域 (スコア:2)
コード見ればわかりますが、毎回書き込みはバッファリング効かせてるんでシステムコールの回数はかなり抑えられてます。
一方でメモリ上で結合の方は、Stringで+を使っての結合なので、内部では new StringBuffer(orig).append(str).toString()が毎回走るので遅くて当たり前です。
GC以前に「そりゃそうなるよな」としか言いようがないです。
Re: (スコア:0)
今回の結果は極端にしても、メモリとディスクアクセスの早さが逆転する分岐点はどこでしょうね。有名どころのコードでみつかると話が面白いんですが（人任せ）。
Re: (スコア:0)
PythonのGCは基本参照カウント、循環参照を別途マーク・アンド・スイープで回収するので。、
文字列のような内部に参照を持たないインスタンスの場合GCが動かない。
Re: (スコア:0, 参考になる)
論文のソースコードがダメダメですね。遅くて当たり前です。
JavaではStringは変更不可のオブジェクトなので文字列を効率よく編集するにはStringBuilderを使うのが常識になってます。
String concatString = "";
for (int i=0; i < numIter; i++) {
concatString += addString;
}
上のコードは次のコードと等価です。毎回大量のオブジェクトを生成して破棄する富豪的なコードなのでGCが大量に発生して最悪のパフォーマンスになっていますね。
String concatString = "";
for (int i = 0; i < n
Re:Javaのヒープ領域 (スコア:1)
うん、みんな知ってる
>論文には「JavaではStringBuilderやStringBufferといったミュータブルなデータ型を使用すれば結果が大幅に改善する」といった記述もある
Re:Javaのヒープ領域 (スコア:4, 参考になる)
さらにいうと、リバースコンパイラでチェックしたけど、
最近のコンパイラなら hoge += fuga 的にシンプルに記述していれば、
勝手にテンポラリな StringBuilder に置き換えてくれる。
# 当然、StringBuffer とか使って現在では微妙な最適化した古いコードは、コンパイラで最適化してくれない。
# 何でも感でも人間が最適化するのは考え物ですね。
Re:Javaのヒープ領域 (スコア:3)
さらに言えば、BufferedWriterをやめて、FileWriterで毎回writeするならもっと遅くなるでしょうね。完全に逆転するでしょう。
BufferedWriter使ったらバッファが一杯になるまでIOは走らないので、いわばこっちこそが「文字列を結合してから書き込む」に相当する処理なので。
Re:Javaのヒープ領域 (スコア:2)
> 一方的に書くだけだとバッファの許す限り応答待ちは特に必要ないよ。
読むだけならなおさらですね。
なので実際のデバイスからの読み書きの処理時間より、システムコールのオーバーヘッドの方が大きくなるはずなんだよね。
これはmmap/DirectByteBuffer使って読み書きするのとread/writeの読み書きとでは同じディスクからの読み書きだけど速度が桁違いに違うことからも明らか。
JavaのDirectByteBufferなら、1バイトずつ100万回読み書きしても、100万バイトを1度に読み込むのも速度は大して変わらないのに、
read/writeだと1バイトずつ100万回と100万バイトを1回で読み込むのとでは2桁くらい性能が悪くなるからね。
例えば dd if=/dev/urandom of=test.dat BS=1024 count=1000で1Mくらいのファイル作って、IOPerfTest.java [github.com]みたいなテストを実行してみればわかるよ。自分の環境だと
Test IO::730 ms
Test IOAll::3 ms
Test NIO::8 ms
Test NIOAll::0 ms
という結果になった。
同じことをpythonでやるとmmapの性能がJavaほど出ないけど、1バイトずつ100万回読み込むのと、100万バイトを一度に読み込むのではmmapにせよreadにせよ非常に大きな差が出た。
ioperf_test.py [github.com]を実行すると、
test_io: 1734.96699333 ms
test_io_all: 0.364065170288 ms
test_mmap: 186.017990112 ms
test_mmap_all: 0.677824020386 ms
となった。
ツッコミホイホイ (スコア:2)
＃普通より低速化させる方法を必死で考えたのかと思うと、ある意味凄いな
結果については (スコア:1)
事前に直前までを書き込み済み相当になってて、非同期に処理できた、みたいな要素もあるのかな...?
たぶん
new x
for{
x.something()
}
write(x)
みたいな処理だったら
new x
for{
x.something()
async write(x)
}
write(x)
的なことが破綻なくできたら、 それは効率を上げれて、差を隠蔽できるんじゃなかろうかな、とは思う
M-FalconSky (暑いか寒い)
書き込みキャッシュ (スコア:1)
＞OSによるバッファリングがあるためにディスクへ直接書き込んでも速度がそれほど低下しないと指摘。
これ、「ディスクに直接書き込む」って言えんのか？
Re:書き込みキャッシュ (スコア:1)
バッファリンがどうこう言ってるあたりからして、計測時間中には全く書き込んでいない可能性すらある。
Re: (スコア:0)
でも、「ファイルから直接読み込む」ことができるなら問題ないんですよ。
事の本質は、メモリは断片化できないけど、ファイルは断片化しててもいい、ってことだと思いますけどね。ファイルは断片化上等だから、領域の再確保でコピーが発生しません。精々が飛んでる部分のアドレスを書くくらい。一方、メモリは確保した領域が足りなくなれば、そこをあきらめて新しい場所に移動して既存の部分はコピーするから、ですよね。
だから、ファイルっぽいメモリ確保ができるメモリマネージャーを誰かが作ればいいんだと思いますよ。ポインタで直接足し算引き算できないのがネックですけど、ファイルと同等のインターフェイスを備えるくらいならできるでしょうから、そこを経由させて最後に一気にディスクアクセスした方が速いと思います。
Re: (スコア:0)
RAMディスクとかってそういう仕組みじゃないの？
そもそもディスク上でデータ処理なんかしたら、IO待ちだけで死ねると思うんだけどね。
多分この研究者達は、DBシステムの先人達の苦労を、貶めたいんだろうね。
Re: (スコア:0)
それって、memory-mapped fileのことでは？
Re:書き込みキャッシュ (スコア:1)
Linuxなら、Direct I/OやRAW I/Oを利用した場合のみがディスクへ直接書き込みになります。仮想ファイルシステムレベルで扱いが違いますので一緒に議論することはできません。それにmemory-mapped fileについても議論する必要があるだろうしね。
Windowsの場合、memory-mapped fileが一番高速みたいですね。最近のWindowsならOSによるバッファリングも間接的にmemory-mapped fileを使っているようですしね。
あと、メモリ空間に余裕があるなら、Laege Page Supportを利用するかどうかによっても違いが出てくるけれど、ここでの議論とは趣旨が変わってくる。
Re: (スコア:0)
str1=str1+str2 より str1+=str2 の方が速い、みたいな話ですね。
要するに (スコア:1)
SSD最強って事で。
Re:要するに (スコア:1)
Javaを使わないほうが早い。
まじれす (スコア:0)
この結果はOSのディスクキャッシュが大きく影響するから、
関係無いです。
単純すぎる (スコア:0)
驚いた (スコア:0)
IOの速度が気になる時は各層でのバッファリング意識するのは当然だと思ってた。
一番驚いたのは、こんな新入社員の暇つぶしにやらせるような内容の調査が(なんの目的であれ)論文として存在するということ。
いったい何がしたいのか (スコア:0)
A. 1MBの文字列処理をする + ディスクに1MB書き込む
B. ディスクに1MB書き込む
そりゃ、Bのほうが早いのは当然。
Re:いったい何がしたいのか (スコア:1)
論文中では何故かBufferedWriterを使っています。8192バイトずつ書き込んでいるのに気付いていないのでしょうか。
Re: (スコア:0)
あからさまにディスク優位なほどのシンプルすぎるプログラムでしたね。
これが、文字列を分割して間に別の文字列を挟み込んで...とかやりだせば一気にメモリ優位になっていくはず。
Re: (スコア:0)
ディスクの方も「読み込み＋結合＋書き込み」でループすべき
Re: (スコア:0)
一応、実験で言いたいことは、
メモリでデータ処理してからまとめてディスクに書くより、
ディスクに直接書いたほうがいいということなのだと思う。
たださ、データをシーケンシャルにディスクに書くだけの単純処理で、それが示されるわけないじゃない。
うーｎ (スコア:0)
何度もメモリ確保し直している時点でダメ
そもそも、テキストに書き出すだけなら、文字列を結合する必要ないよね？
興味深い (スコア:0)
つまり、例えばRRDファイルを管理する場合、対象ファイルやノードが膨大であっても、tmpfs上にRRDファイルを直接展開するよりもrrdcachedを使った方が速く、更にそれよりもRRDファイルを毎回ディスクに書き出す方が速いというわけですねわかります。
RRDtoolもJavaやPythonで作りなおせばそうなるんですかね？
実に興味深い。
他見てないけど、少なくともJavaのコードは (スコア:0)
> ディスクアクセスを避けてできるだけメモリー上で処理することが実行時間の短縮につながると考えられているが、これに逆行する研究結果を
逆行してない。
それするのがBufferedWriter。
二重にバッファリングしてるから遅くなる。しかも非効率なコードで。
対抗して、「JavaでStringBuilder使うより+で連結したほうが高速？」(C#なども) (スコア:0)
StringBuilder buff = new StringBuilder();
buff.append("select col1,col2,col3");
buff.append(" from table1");
buff.append(" where id = 123456");
-------------------------------------
String buff = "select col1,col2,col3"
+ " from table1"
+ " where id = 123456";
-------------------------------------
以外とわかってない人が多い。
Re: (スコア:0)
それは一つの式で複数結合している場合はコンパイラが最適化してくれるだけで、
ループの中で結合処理をしてたら普通にStringBuilder使ったほうが高速。
Re: (スコア:0)
だから、「高速 ？ 」なんだって。
速い遅い語る前に仕組みを理解しましょうってこと。
Re: (スコア:0)
コンパイラの最適化とかまで考え及ばず（無知なだけ）で、「StringBuilderを使えば問題ない！！」って
「やり方だけを覚えている」アホが多いって言っているんじゃないの？
実際に数回の限られた文字列結合でStringBuilder使って指摘されても逆切れする人は多い
当然、彼らはStringBuilderを使用すること自体にもコストがかかることや、そのコスト以上の恩恵が得られるのはどの程度からなのか？など考えたことすらない
とりあえず噛み付きたいだけだったんだろうけど、銀の弾丸なんてないってことは素直に認めた方が貴方の将来に＋だよ
Re:対抗して、「JavaでStringBuilder使うより+で連結したほうが高速？」(C#なども (スコア:1)
『数回の限られた文字列結合』のコストてどれくらいかかるの。
ハードウェアの力でどうにでもなるところをちくちく最適化するのは、仕事でなくて趣味の範囲だよね。
Re:対抗して、「JavaでStringBuilder使うより+で連結したほうが高速？」(C#なども (スコア:1)
「コストが無視できないから」「やりたいことが明確でないから」のどちらが本当の理由ですか。
どちらにしても、指摘してやり直させる動機としては弱いけど。
こんなレビューがまかり通るなら、レビュアーの教育にもっと力を入れた方がいい気がする。
アホ対策には全部 StringBuilder を使ってくれるほうが、パフォーマンス劣化の原因が一つ減るので安心できる。
Re: (スコア:0)
言語だけでなく型や命令だって銀の弾丸は無いし。
てかC#に至っては文字列探して連結するループなんか記述不要でLINQとString.Join、
Javaだとstreamである程度は近づけられるが末端foreachなのでStringBuilderかな。
Python版 (スコア:0)
ミスリードを誘うための恣意的なプログラミング、というだけに見えますね。
for文の中身を
concatString = addString + concatString
こうするだけで、メモリ版の方が高速になります。（結果として同じ答えが得られる）
concatString += addString
addStringを逆順に入れることに拘りたい or 古いPythonでも速くしたいなら下記のようにすればOKで、やはりメモリ版の方が高速。
conlist=[]
for i in range(0, numIter):
conlist.append(addString)
conlist.reverse()
concatString = "".join(conlist)
Re:Python版 (スコア:2)
ディスクに直接書き込むって方は、
for i in range(0, numIter):
f.write(addString)
というコードを使っているので、メモリで結合も
concatString += addString
で良いはず。遅くするために無理やりやってますよね。
あとこれ書いた人はまずバッファリングについて調べたほうがいいですね。pythonにしろJavaにしろ、IO操作にバッファリング効かせたら何を比較したいのやらさっぱりわからないですね。pythonも
open('file.txt', 'w', 0)
して比較するべきでしょう。
結論「んなこたーない」 (スコア:0)
評価方法が間違っている
でFA?
Re: (スコア:0)
この論文に関してはそうなんだろうなぁ…
でも、非アクティブなタブや使いもしないキャッシュをオンメモリで保持してメモリとページファイルバカ食いするWebブラウザとかみるとディスク活用したほうが軽量高速になるケースは少なくない気がする。
非アクティブなタブのデータは全部ディスクに吐き出して、アクティブ化の際に一括で読み込みとかしてくれたほうがコミットサイズ的にも負荷的にも有利な気がしてならない。
物理メモリを溢れまくってると、タブ切り替えでページフォルトが落ち着くまでの時間がタブあたりの消費メモリ量を読み込む時間を圧倒的に超えるだろアレ。