☰

なぜWCはこんなに遅いのでしょうか?

tag-icon • tag-icon performance wc
なぜ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

これは、ファイルが null でいっぱいであることによって引き起こされる奇妙なエッジ条件だけではありません。ファイルがランダム データでいっぱいであったり、テキスト ファイルであったりする場合でも、パフォーマンスに同じ違いが見られます。

(これは Ubuntu 13.04、64 ビット版です)

答え1

そこでソースを確認してみたところ、2 バイト文字の処理が遅いことが原因のようです。基本的に、読み込んだ文字ごとに、mbrtowc()ワイド文字への変換を試行する必要があり、そのワイド文字が単語区切り文字、行区切り文字などであるかどうかをテストします。

実際、ロケールLANG変数をデフォルトen_US.UTF-8(UTF-8 はマルチバイト文字セット) から " C" (単純なシングルバイト文字セット)に変更すると、wcシングルバイトの最適化を使用できるようになり、速度が大幅に向上し、以前の約 4 分の 1 の時間しかかかりません。

-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のタスク

を実行するとwc、ファイルを 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単語と行の境界を決定し、出現回数を追跡する必要があるためです。

追加のWCディスカッション

私はこれを見つけました2006年のコーディングチャレンジ.NET での実装について説明しています。疑似コードをいくつか見れば難しさはかなり明白なので、他の操作よりもはるかに遅いように見えるwc理由を明らかにするのに役立つかもしれません。wc

関連情報