☰

トイレに行くのはなぜこんなに遅いのでしょうか？

tag-icon • tag-icon performance wc
トイレに行くのはなぜこんなに遅いのでしょうか？

wcユーティリティがなぜそんなに遅いのですか？

大容量ファイルで実行すると、md5sumより約20倍かかります。

MyDesktop:/tmp$ dd if=/dev/zero bs=1024k count=1024 of=/tmp/bigfile
1024+0 records in
1024+0 records out
1073741824 bytes (1.1 GB) copied, 0.687094 s, 1.6 GB/s

MyDesktop:/tmp$ time wc /tmp/bigfile 
         0          0 1073741824 /tmp/bigfile

real    0m45.969s
user    0m45.424s
sys     0m0.424s

MyDesktop:/tmp$ time md5sum /tmp/bigfile 
cd573cfaace07e7949bc0c46028904ff  /tmp/bigfile

real    0m2.520s
user    0m2.196s
sys     0m0.316s

これは、ファイルがヌルで埋められているために発生する奇妙なエッジ条件ではありません。ファイルがランダムなデータで埋められている場合、またはテキストファイルであっても、同じパフォーマンスの違いが見られました。

（Ubuntu 13.04、64ビットベース）

答え1

そのため、ソースコードを見てみると、2バイト文字を処理するのに遅いようです。既定では、読み取ったすべての文字に対してmbrtowc()ワイド文字に変換しようとする関数を呼び出してから、そのワイド文字をテストして単語区切り文字、行区切り記号などであることを確認する必要があります。

実際、LANGデフォルトのロケール変数（UTF-8はマルチバイト文字セット）を変更して ""（単純なシングルバイト文字セット）en_US.UTF-8に設定すると、シングルバイト最適化が有効になり、速度が大幅に向上します。速度は前回の約4分の1しかかかりません。Cwc

また、各文字が単語（-w）、行長（-L）、または文字（-m）として計算されているかどうかを簡単に確認してください。バイトおよび/または行計算のみを実行する場合は、ワイド文字処理をスキップして非常に高速に実行できますmd5sum。つまり。

私は実行しましたが、マルチバイト文字（、、など）を処理する関数はgprof実行時間の約30％しかかかりませんでした。バッファーの手順を実行し、バッファーのすべての部分で完了した文字をバッファーの先頭に戻し、次に処理できるようにします。mymbsinit()mymbrtowc()myiswprint()

これで何を探すべきかを知っているので、UTF-8でいくつかのユーティリティが遅いことを言及するいくつかの記事を見つけました。

https://stackoverflow.com/questions/13913014/grepping-a-huge-file-80gb-any-way-to-speed-it-up http://dtrace.org/blogs/brendan/2011/12/08/2000x-performance-win/

答え2

ただ推測だけです。しかし、リンゴとオレンジを比較し、wc進行中の作業とmd5sum進行中の作業を比較することです。

md5sum 操作

ファイルを処理するときは、md5sumファイルをストリームとして開き、配信を開始します。MD5チェック機能メモリはほとんど必要ありません。これは本質的にCPUとディスクI / Oの制限です。

トイレ作業

実行されると、wcファイルを一度に1文字ずつ解析する以外の作業を実行します。実際には、ファイルの構造を一度に1行ずつ分析して、文字間の境界がどこにあるのか、単語の境界であるのかを確認する必要があります。

はい

次の文字列とそれを解析するときは、各アルゴリズムがどのように文字列を通過するかを検討してください。

“Hello! Greg”
“Hello!Greg”
“Hello\nGreg”
“A.D.D.”
“Wow, how great!”
“wow     \n\n\n    great”
“it was a man-eating shark.”

MD5の場合、これらの文字列は一度に1文字ずつ移動します。これは、どの単語と行の境界が何であるかを判断し、どのくらいの項目がwc表示されるかを追跡する必要があるためです。

その他のトイレディスカッション

私はこれを見つけましたコーディングチャレンジ2006wc.NETでの実装について説明します。いくつかの疑似コードを見ると難しさが非常に明確であるため、wcこれが他のタスクよりはるかに遅い理由を説明するのに役立ちます。

関連情報