[Namazu-devel-ja 1575] Re: hash の負荷軽減
Tadamasa Teranishi
yw3t-trns ＠ asahi-net.or.jp
2007年 4月 20日 (金) 12:40:04 JST
寺西です。
約1万件の文書をまとめてインデックスを作成する場合と、インデックスを
分けて作成する場合の時間を測定しました。
1) 測定マシン
前回と同じ
2) 測定データ
http://www.namazu.org/ml.html#archive の以下のファイル
A) namazu-devel-ja 4,136通
B) namazu-users-ja 3,881通
C) namazu-win32-users-ja 2,242通
-----------------------------
合計 10,259
メディアタイプは message/rfc822
3) 測定条件
a) $ON_MEMORY_SIZE を標準(5000000), 10倍, 1/10, のそれぞれ
b) A,B,C をまとめた時と、A,B,C それぞれでインデックスを作成した時
および nmzmerge でインデックスをまとめる時間
c) Namazu 2.0.17(SA), 修正(SE) のそれぞれ
4) 修正内容
前回と同じ
5) 結果
・結果(I) Namazu 2.0.17(SA)で測定
| 文書数| 処理時間 | 処理時間 | 処理時間
$ON_MEMORY_MAX | | 50000000 | 5000000 | 500000
-----------------+-------+-------------+-------------+-------------
A+B+Cまとめて | 10259 | 685.7960[1] | 830.9160[7] |1638.016 [65]
| 文書数| 処理時間 | 処理時間 | 処理時間
| | 50000000 | 5000000 | 500000
-----------------+-------+-------------+-------------+-------------
A | 4136 | 286.4409[1] | 311.2507[3] | 515.1370[27]
B | 3881 | 255.6200[1] | 278.4375[3] | 453.7676[24]
C | 2242 | 152.0534[1] | 166.8537[2] | 237.9477[15]
-----------------+-------+-------------+-------------+-------------
小計 | | 694.1143 | 756.5419 |1206.8523
-----------------+-------+-------------+-------------+-------------
nmzmerge (B+C) | | 175.9377
nmzmerge A+(B+C) | | 371.2264
-----------------+-------+-----------------------------------------
小計 | | 547.1641
-----------------+-------+-------------+-------------+-------------
合計 1241.2784 | 1303.706 |1754.0164
* A: namazu-devel-ja
* B: namazu-users-ja
* C: namazu-win32-users-ja
* [] 内はインデックス書き出し回数
.....................................................................
・結果(II) 修正(SE)で測定
| 文書数| 処理時間 | 処理時間 | 処理時間
$ON_MEMORY_MAX | | 50000000 | 5000000 | 500000
-----------------+-------+-------------+-------------+-------------
A+B+Cまとめて | 10259 | 563.6400[1] | 677.2240[7] |1528.630 [65]
| 文書数| 処理時間 | 処理時間 | 処理時間
| | 50000000 | 5000000 | 500000
-----------------+-------+-------------+-------------+-------------
A | 4136 | 221.9006[1] | 247.3236[3] | 424.0362[27]
B | 3881 | 206.8999[1] | 229.6178[3] | 346.1183[24]
C | 2242 | 123.0638[1] | 129.4084[2] | 192.6253[15]
-----------------+-------+-------------+-------------+-------------
小計 | | 551.8643 | 606.3498 | 962.7798
-----------------+-------+-------------+-------------+-------------
nmzmerge (B+C) | | 175.9377
nmzmerge A+(B+C) | | 371.2264
-----------------+-------+------------------------------------------
小計 | | 547.1641
-----------------+-------+-------------+-------------+--------------
合計 1099.0284 |1153.5139 |1509.9439
* A: namazu-devel-ja
* B: namazu-users-ja
* C: namazu-win32-users-ja
* [] 内はインデックス書き出し回数
6) 考察
通常、インデックスをまとめて作成するよりは分割して作成した方が
処理時間の合計は短くなります。これは処理時間がO(N)ではないためです。
(ソートとかありますから)
特にインデックス書き出し回数が増えると、その差は大きくなるようです。
このことから、インデックスを適当に分割することはある程度有効である
ことがわかります。
ただし、$ON_MEMORY_MAX を変更することで処理速度を短くすることが
可能(通常可能)であれば、そちらの方が効率的なようです。
分割して作成したインデックスをマージした場合は、nmzmerge の処理が
かなり遅いため、どうしても1つのインデックスにしたい場合には、分割
してインデックスを作成し、後でマージするという方法はあまり効率的
でないことがわかります。(インデックス書き出し回数がこれより多くなる
と逆転しますが、現実的にその回数で運用するのは適切ではないので、
無意味です。)
ただし、インデックスを別のマシン(CPU)で分散して作成するという
場合は、同時に処理ができるのでそういった用途では有効でしょう。
なお、インデックスは複数に分かれていても検索時に複数のインデックス
が利用できますから、1つのインデックスにこだわる必要はないでしょう。
インデックスが分かれていれば、検索範囲をグループごとに変えることも
できますので、便利な場合も多いです。ただ、検索の処理時間はインデック
スが分かれていると遅くなったり、スコアの計算が違ったりするので、
その点は割り切る必要があります。
nmzmerge は高速化できるのではないかと思います。また、2つのイン
デックスのマージしかできませんが、複数のインデックスのマージが
できれば、もっと効率的ではないかと思います。nmzmerge の改良が望まれ
ます。
7) 測定データ
[7-1] nmzmerge B, C のインデックスをまとめる
Total Elapsed Time = 177.0377 Seconds
User+System Time = 175.9377 Seconds
Exclusive Times
%Time ExclSec CumulS #Calls sec/call Csec/c Name
29.9 52.69 190.38 1 52.695 190.38 main::nmzmerge
19.4 34.24 53.798 127113 0.0003 0.0004 nmzword::write
15.1 26.62 42.256 146090 0.0002 0.0003 nmzword::read
7.85 13.80 25.876 277160 0.0000 0.0001 nmzfile::getlist
6.52 11.47 15.297 194466 0.0001 0.0001 nmzfile::putline
5.83 10.25 13.948 192649 0.0001 0.0001 nmzfile::putlist
5.02 8.838 8.308 265776 0.0000 0.0000 nmzlib::readw
4.97 8.738 7.167 786312 0.0000 0.0000 IO::Handle::print
3.99 7.017 20.763 131072 0.0001 0.0002 nmzphrase::read
2.90 5.108 9.546 65536 0.0001 0.0001 nmzphrase::write
2.70 4.759 3.954 402973 0.0000 0.0000 IO::Handle::read
2.44 4.289 3.517 386451 0.0000 0.0000 IO::Seekable::tell
2.30 4.049 3.610 220099 0.0000 0.0000 IO::Handle::getline
2.30 4.038 6.649 213465 0.0000 0.0000 nmzfile::getline
1.25 2.200 1.946 127114 0.0000 0.0000 main::wordcmp
[7-2] nmzmerge A と (B + C) のインデックスをまとめる
Total Elapsed Time = 379.0464 Seconds
User+System Time = 371.2264 Seconds
Exclusive Times
%Time ExclSec CumulS #Calls sec/call Csec/c Name
36.8 136.8 397.08 1 136.82 397.08 main::nmzmerge
23.0 85.66 121.53 198683 0.0004 0.0006 nmzword::write
14.9 55.47 84.780 229805 0.0002 0.0004 nmzword::read
5.60 20.77 26.698 311532 0.0001 0.0001 nmzfile::putline
5.37 19.95 37.075 360875 0.0001 0.0001 nmzfile::getlist
4.69 17.41 22.486 264219 0.0001 0.0001 nmzfile::putlist
3.85 14.27 11.348 117247 0.0000 0.0000 IO::Handle::print
3.64 13.50 12.614 358413 0.0000 0.0000 nmzlib::readw
2.32 8.626 23.722 131072 0.0001 0.0002 nmzphrase::read
2.10 7.778 6.896 353444 0.0000 0.0000 IO::Handle::getline
1.98 7.348 6.100 499746 0.0000 0.0000 IO::Handle::read
1.97 7.316 12.380 342676 0.0000 0.0000 nmzfile::getline
1.86 6.918 5.481 575708 0.0000 0.0000 IO::Seekable::tell
1.75 6.497 11.216 65536 0.0001 0.0002 nmzphrase::write
1.19 4.409 3.913 198684 0.0000 0.0000 main::wordcmp
--
=====================================================================
寺西 忠勝(TADAMASA TERANISHI) yw3t-trns ＠ asahi-net.or.jp
http://www.asahi-net.or.jp/~yw3t-trns/index.htm
Key fingerprint = 474E 4D93 8E97 11F6 662D 8A42 17F5 52F4 10E7 D14E
Namazu-devel-ja メーリングリストの案内