From: "NARUSE, Yui" Date: 2008-03-17T16:20:33+09:00 Subject: [ruby-dev:34072] rb_memsearch　optimization This is a multi-part message in MIME format. --------------000907010806050601080000 Content-Type: text/plain; charset=ISO-2022-JP Content-Transfer-Encoding: 7bit 成瀬です。 現在の rb_memsearch は Karp-Rabin を使っています。 導入の際に Karp-Rabin についておっしゃっていた通り、 確かにパターンが短い場合でも長い場合でもそれなりの性能を示しています。 しかし、パターンの長さによってアルゴリズムの向き不向きが変わるのならば、 長さによってアルゴリズムを変えてはどうでしょう。 具体的にはパターンが 1 バイトの場合はリニアサーチが最速です。 逆に、WORD幅 - 1 バイトを超える場合にはどんどん飛ばしていく BM 系の方が速いでしょう。 さて、今回はパターンを5種類に分け、 1. m > n, m == n, m == 0 等 #=> それぞれ計算 2. m == 1 #=> リニアサーチ 3. 2 <= m <= SIZEOF_VALUE #=> 単純にシフトして比較 4. SIZEOF_VALUE < m <= SIZEOF_VALUE * CHAR_BIT #=> Shift Or 5. SIZEOF_VALUE * CHAR_BIT < m #=> Quick Search で試してました。 「単純にシフトして比較」は hashing しない Karp-Rabin のような感じです。 1 WORD にバイト列をそのまま、32bit システムなら 4 文字、 64bit システムなら 8 文字格納して比較します。 このレベルの処理だとテーブル参照のコストが以外と効いてくるので、 それなりに差が出てきました。 2. や 3. をいちいち別にする必要があるかという議論はあると思いますが、 rb_memsearch の主たる用途である String#index がもっぱら数文字を引数として 呼ばれることを考えれば、妥当ではないかなぁと。 2. と 3. はだいたい今の 1.5 倍くらいになります。 4. は Shift-Or が効くかと思ったんですが、 実際にはもう Quick Search の方が速くなっていました。 5. は非常に高速なのですが そのまま実装すると UTF-8 の場合が問題でして、 例えば、ひらがなの中からひらがなを探すとかのような、 同じ 1/2 ブロック内での検索だと 3 バイトのうちの 2 バイトがいたるところで ヒットするので、期待したほどの速度がでなくなります。 そのため、UTF-8 の場合には文字単位で比較するようにしています。 この対策の有無で、単純な Quick Search の最悪のケースから 3 倍ほど変わります。 # 壊れた UTF-8 文字列でもちゃんと動くはずです これらの対策を施した場合のベンチマークは以下のとおりです。 rad.rb user system total real ruby-18 2.140625 0.007812 2.148438 ( 2.153251) ruby-19 2.171875 0.007812 2.179688 ( 2.180716) patched 0.343750 0.007812 0.351562 ( 0.358093) rad8.rb user system total real ruby-19 79.687500 0.093750 79.781250 ( 79.725523) patched 47.640625 0.085938 47.726562 ( 47.701325) rad.rb は [ruby-core:15508] で Radarek さんが出していたベンチマークです。 この時点で現在同様 Ruby 1.9 は 1.8 と同等の速度になっていましたが、 これがさらに 7 倍速くなります。 rad8.rb は対象のテキストを Ruby 1.9 添付の README.EXT.ja を、 UTF-8 に変換したデータに変えたものです。 こちらでは 1.5 倍になっています。 添付のパッチには一応参考までに Shift-Or を用いたバージョンもつけておきました。 場合分けの手間に見合った速度の向上はあると思うのですが、いかがでしょう。 -- NARUSE, Yui DBDB A476 FDBD 9450 02CD 0EFC BCE3 C388 472E C1EA --------------000907010806050601080000 Content-Type: text/plain; name="memsearch.patch" Content-Transfer-Encoding: base64 Content-Disposition: inline; filename="memsearch.patch" LS0tIGluY2x1ZGUvcnVieS9lbmNvZGluZy5oCShyZXZpc2lvbiAxNTc4NykKKysrIGluY2x1 ZGUvcnVieS9lbmNvZGluZy5oCSh3b3JraW5nIGNvcHkpCkBAIC0xNzYsNSArMTc2LDYgQEAg aW50IHJiX3VzYXNjaWlfZW5jaW5kZXgodm9pZCk7CiBWQUxVRSByYl9lbmNfZGVmYXVsdF9l eHRlcm5hbCh2b2lkKTsKIHZvaWQgcmJfZW5jX3NldF9kZWZhdWx0X2V4dGVybmFsKFZBTFVF IGVuY29kaW5nKTsKIFZBTFVFIHJiX2xvY2FsZV9jaGFybWFwKFZBTFVFIGtsYXNzKTsKK2xv bmcgcmJfbWVtc2VhcmNoKGNvbnN0IHZvaWQqLGxvbmcsY29uc3Qgdm9pZCosbG9uZyxyYl9l bmNvZGluZyopOwogCiAjZW5kaWYgLyogUlVCWV9FTkNPRElOR19IICovCi0tLSBpbmNsdWRl L3J1YnkvaW50ZXJuLmgJKHJldmlzaW9uIDE1Nzg3KQorKysgaW5jbHVkZS9ydWJ5L2ludGVy bi5oCSh3b3JraW5nIGNvcHkpCkBAIC00NjYsNyArNDY2LDYgQEAgZG91YmxlIHJiX2dlbnJh bmRfcmVhbCh2b2lkKTsKIC8qIHJlLmMgKi8KICNkZWZpbmUgcmJfbWVtY21wIG1lbWNtcAog aW50IHJiX21lbWNpY21wKGNvbnN0IHZvaWQqLGNvbnN0IHZvaWQqLGxvbmcpOwotbG9uZyBy Yl9tZW1zZWFyY2goY29uc3Qgdm9pZCosbG9uZyxjb25zdCB2b2lkKixsb25nKTsKIFZBTFVF IHJiX3JlZ19udGhfZGVmaW5lZChpbnQsIFZBTFVFKTsKIFZBTFVFIHJiX3JlZ19udGhfbWF0 Y2goaW50LCBWQUxVRSk7CiBWQUxVRSByYl9yZWdfbGFzdF9tYXRjaChWQUxVRSk7Ci0tLSBy ZS5jCShyZXZpc2lvbiAxNTc4NykKKysrIHJlLmMJKHdvcmtpbmcgY29weSkKQEAgLTk1LDQx ICs5NSwyMDIgQEAgcmJfbWVtY21wKGNvbnN0IHZvaWQgKnAxLCBjb25zdCB2b2lkICpwMgog ICAgIHJldHVybiBtZW1jbXAocDEsIHAyLCBsZW4pOwogfQogCi1sb25nCi1yYl9tZW1zZWFy Y2goY29uc3Qgdm9pZCAqeDAsIGxvbmcgbSwgY29uc3Qgdm9pZCAqeTAsIGxvbmcgbikKK3N0 YXRpYyBpbmxpbmUgbG9uZworcmJfbWVtc2VhcmNoX3NzKGNvbnN0IHVuc2lnbmVkIGNoYXIg KnhzLCBsb25nIG0sIGNvbnN0IHVuc2lnbmVkIGNoYXIgKnlzLCBsb25nIG4pCiB7Ci0gICAg Y29uc3QgdW5zaWduZWQgY2hhciAqeCA9IHgwLCAqeSA9IHkwOwotICAgIGNvbnN0IHVuc2ln bmVkIGNoYXIgKnMsICplOwotICAgIGxvbmcgaTsKLSAgICBpbnQgZDsKLSAgICB1bnNpZ25l ZCBsb25nIGh4LCBoeTsKKyAgICBjb25zdCB1bnNpZ25lZCBjaGFyICp4ID0geHMsICp4ZSA9 IHhzICsgbTsKKyAgICBjb25zdCB1bnNpZ25lZCBjaGFyICp5ID0geXMsICp5ZSA9IHlzICsg bjsKKyNpZm5kZWYgVkFMVUVfTUFYCisjIGlmIFNJWkVPRl9WQUxVRSA9PSA4CisjICBkZWZp bmUgVkFMVUVfTUFYIDB4RkZGRkZGRkZGRkZGRkZGRlVMTAorIyBlbGlmIFNJWkVPRl9WQUxV RSA9PSA0CisjICBkZWZpbmUgVkFMVUVfTUFYIDB4RkZGRkZGRkZVTAorIyBlbmRpZgorI2Vu ZGlmCisgICAgVkFMVUUgaHgsIGh5LCBtYXNrID0gVkFMVUVfTUFYID4+ICgoU0laRU9GX1ZB TFVFIC0gbSkgKiBDSEFSX0JJVCk7CisKKyAgICBpZiAobSA+IFNJWkVPRl9WQUxVRSkKKwly Yl9idWcoIiEhdG9vIGxvbmcgcGF0dGVybiBzdHJpbmchISIpOworCisgICAgCS8qIFByZXBh cmUgaGFzaCB2YWx1ZSAqLworICAgIGZvciAoaHggPSAqeCsrLCBoeSA9ICp5Kys7IHggPCB4 ZTsgKyt4LCArK3kpIHsKKwloeCA8PD0gQ0hBUl9CSVQ7CisJaHkgPDw9IENIQVJfQklUOwor CWh4IHw9ICp4OworCWh5IHw9ICp5OworICAgIH0KKyAgICAvKiBTZWFyY2hpbmcgKi8KKyAg ICB3aGlsZSAoaHggIT0gaHkpIHsKKwlpZiAoeSA9PSB5ZSkKKwkgICAgcmV0dXJuIC0xOwor CWh5IDw8PSBDSEFSX0JJVDsKKwloeSB8PSAqeTsKKwloeSAmPSBtYXNrOworCXkrKzsKKyAg ICB9CisgICAgcmV0dXJuIHkgLSB5cyAtIG07Cit9CiAKLSNkZWZpbmUgS1JfUkVIQVNIKGEs IGIsIGgpICgoKGgpIDw8IDEpIC0gKCgodW5zaWduZWQgbG9uZykoYSkpPDxkKSArIChiKSkK K3N0YXRpYyBpbmxpbmUgbG9uZworcmJfbWVtc2VhcmNoX3NvKGNvbnN0IHVuc2lnbmVkIGNo YXIgKnhzLCBsb25nIG0sIGNvbnN0IHVuc2lnbmVkIGNoYXIgKnlzLCBsb25nIG4pCit7Cisg ICAgY29uc3QgdW5zaWduZWQgY2hhciAqeCA9IHhzLCAqeGUgPSB4cyArIG07CisgICAgY29u c3QgdW5zaWduZWQgY2hhciAqeSA9IHlzLCAqeWUgPSB5cyArIG47CisgICAgVkFMVUUgaSwg bGltLCBzdGF0ZSwgdGFibGVbMjU2XTsKIAotICAgIGlmIChtID4gbikgcmV0dXJuIC0xOwot ICAgIHMgPSB5OyBlID0gcyArIG4gLSBtOworICAgIC8qIFByZXByb2Nlc3NpbmcgKi8KKyAg ICBmb3IgKGkgPSAwOyBpIDwgMjU2OyArK2kpCisJdGFibGVbaV0gPSB+MDsKKyAgICBmb3Ig KGxpbSA9IDAsIGkgPSAxOyB4IDwgeGU7ICsreCwgaSA8PD0gMSkgeworCXRhYmxlWyp4XSAm PSB+aTsKKwlsaW0gfD0gaTsKKyAgICB9CisgICAgbGltID0gfihsaW0+PjEpOworICAgIC8q IFNlYXJjaGluZyAqLworICAgIGZvciAoc3RhdGUgPSB+MDsgeSA8IHllOyArK3kpIHsKKwlz dGF0ZSA8PD0gMTsKKwlzdGF0ZSB8PSB0YWJsZVsqeV07CisJaWYgKHN0YXRlIDwgbGltKQor CSAgICByZXR1cm4gKHkgLSB5cyAtIG0gKyAxKTsKKyAgICB9CisgICAgcmV0dXJuIC0xOwor fQorCitzdGF0aWMgaW5saW5lIGxvbmcKK3JiX21lbXNlYXJjaF9rcihjb25zdCB1bnNpZ25l ZCBjaGFyICp4cywgbG9uZyBtLCBjb25zdCB1bnNpZ25lZCBjaGFyICp5cywgbG9uZyBuKQor eworICAgIGNvbnN0IHVuc2lnbmVkIGNoYXIgKnggPSB4cywgKnhlID0geHMgKyBtOworICAg IGNvbnN0IHVuc2lnbmVkIGNoYXIgKnkgPSB5cywgKnllID0geXMgKyBuOworICAgIFZBTFVF IGh4LCBoeTsKKyAgICBsb25nIGQgPSBzaXplb2YoaHgpICogQ0hBUl9CSVQgLSAxOworI2Rl ZmluZSBLUl9SRUhBU0goYSwgYiwgaCkgKCgoaCkgPDwgMSkgLSAoKChWQUxVRSkoYSkpPDxk KSArIChiKSkKIAogICAgIC8qIFByZXByb2Nlc3NpbmcgKi8KICAgICAvKiBjb21wdXRlcyBk ID0gMl4obS0xKSB3aXRoCiAgICAgICAgdGhlIGxlZnQtc2hpZnQgb3BlcmF0b3IgKi8KLSAg ICBkID0gc2l6ZW9mKGh4KSAqIENIQVJfQklUIC0gMTsKICAgICBpZiAoZCA+IG0pIGQgPSBt OworICAgIC8qIFByZXBhcmUgaGFzaCB2YWx1ZSAqLworICAgIGZvciAoaHkgPSBoeCA9IDA7 IHggPCB4ZTsgKyt4LCArK3kpIHsKKwloeCA9IEtSX1JFSEFTSCgwLCAqeCwgaHgpOworCWh5 ID0gS1JfUkVIQVNIKDAsICp5LCBoeSk7CisgICAgfQorICAgIC8qIFNlYXJjaGluZyAqLwor ICAgIHdoaWxlIChoeCAhPSBoeSB8fCBtZW1jbXAoeHMsIHkgLSBtLCBtKSkgeworICAgIAlp ZiAoeSA9PSB5ZSkKKwkgICAgcmV0dXJuIC0xOworCWh5ID0gS1JfUkVIQVNIKCooeS1kKSwg KnksIGh5KTsKKwkrK3k7CisgICAgfQorICAgIHJldHVybiB5IC0geXM7Cit9CiAKLSAgICBp ZiAobiA9PSBtKSB7Ci0JcmV0dXJuIG1lbWNtcCh4LCBzLCBtKSA9PSAwID8gMCA6IC0xOwor c3RhdGljIGlubGluZSBsb25nCityYl9tZW1zZWFyY2hfcXMoY29uc3QgdW5zaWduZWQgY2hh ciAqeHMsIGxvbmcgbSwgY29uc3QgdW5zaWduZWQgY2hhciAqeXMsIGxvbmcgbikKK3sKKyAg ICBjb25zdCB1bnNpZ25lZCBjaGFyICp4ID0geHMsICp4ZSA9IHhzICsgbTsKKyAgICBjb25z dCB1bnNpZ25lZCBjaGFyICp5ID0geXMsICp5ZSA9IHlzICsgbjsKKyAgICBWQUxVRSBpLCBx c3RhYmxlWzI1Nl07CisKKyAgICAvKiBQcmVwcm9jZXNzaW5nICovCisgICAgZm9yIChpID0g MDsgaSA8IDI1NjsgKytpKQorCXFzdGFibGVbaV0gPSBtICsgMTsKKyAgICBmb3IgKDsgeCA8 IHhlOyArK3gpCisJcXN0YWJsZVsqeF0gPSB4ZSAtIHg7CisgICAgLyogU2VhcmNoaW5nICov CisgICAgZm9yICg7IHkgPCB5ZTsgeSArPSAqKHFzdGFibGUgKyB5W21dKSkgeworCWlmICgq eHMgPT0gKnkgJiYgbWVtY21wKHhzLCB5LCBtKSA9PSAwKQorCSAgICByZXR1cm4geSAtIHlz OworICAgIH0KKyAgICByZXR1cm4gLTE7Cit9CisKK3N0YXRpYyBpbmxpbmUgdW5zaWduZWQg aW50CityYl9tZW1zZWFyY2hfcXNfdXRmOF9oYXNoKGNvbnN0IHVuc2lnbmVkIGNoYXIgKngp Cit7CisgICAgcmVnaXN0ZXIgY29uc3QgdW5zaWduZWQgaW50IG1peCA9IDgzNTM7CisgICAg cmVnaXN0ZXIgdW5zaWduZWQgaW50IGggPSAqeDsKKyAgICBpZiAoaCA8IDB4QzApIHsKKwly ZXR1cm4gaCArIDI1NjsKKyAgICB9CisgICAgZWxzZSBpZiAoaCA8IDB4RTApIHsKKwloICo9 IG1peDsKKwloICs9IHhbMV07CisgICAgfQorICAgIGVsc2UgaWYgKGggPCAweEYwKSB7CisJ aCAqPSBtaXg7CisJaCArPSB4WzFdOworCWggKj0gbWl4OworCWggKz0geFsyXTsKKyAgICB9 CisgICAgZWxzZSBpZiAoaCA8IDB4RjUpIHsKKwloICo9IG1peDsKKwloICs9IHhbMV07CisJ aCAqPSBtaXg7CisJaCArPSB4WzJdOworCWggKj0gbWl4OworCWggKz0geFszXTsKICAgICB9 Ci0gICAgLyogUHJlcGFyZSBoYXNoIHZhbHVlICovCi0gICAgZm9yIChoeSA9IGh4ID0gaSA9 IDA7IGkgPCBkOyArK2kpIHsKLQloeCA9IEtSX1JFSEFTSCgwLCB4W2ldLCBoeCk7Ci0JaHkg PSBLUl9SRUhBU0goMCwgc1tpXSwgaHkpOworICAgIGVsc2UgeworCXJldHVybiBoICsgMjU2 OworICAgIH0KKyAgICByZXR1cm4gKHVuc2lnbmVkIGNoYXIpaDsKK30KKworc3RhdGljIGlu bGluZSBsb25nCityYl9tZW1zZWFyY2hfcXNfdXRmOChjb25zdCB1bnNpZ25lZCBjaGFyICp4 cywgbG9uZyBtLCBjb25zdCB1bnNpZ25lZCBjaGFyICp5cywgbG9uZyBuKQoreworICAgIGNv bnN0IHVuc2lnbmVkIGNoYXIgKnggPSB4cywgKnhlID0geHMgKyBtOworICAgIGNvbnN0IHVu c2lnbmVkIGNoYXIgKnkgPSB5cywgKnllID0geXMgKyBuOworICAgIFZBTFVFIGksIHFzdGFi bGVbNTEyXTsKKworICAgIC8qIFByZXByb2Nlc3NpbmcgKi8KKyAgICBmb3IgKGkgPSAwOyBp IDwgNTEyOyArK2kpIHsKKwlxc3RhYmxlW2ldID0gbSArIDE7CisgICAgfQorICAgIGZvciAo OyB4IDwgeGU7ICsreCkgeworCXFzdGFibGVbcmJfbWVtc2VhcmNoX3FzX3V0ZjhfaGFzaCh4 KV0gPSB4ZSAtIHg7CiAgICAgfQogICAgIC8qIFNlYXJjaGluZyAqLwotICAgIHdoaWxlICho eCAhPSBoeSB8fCBtZW1jbXAoeCwgcywgbSkpIHsKLQlpZiAocyA+PSBlKSByZXR1cm4gLTE7 Ci0JaHkgPSBLUl9SRUhBU0goKnMsICoocytkKSwgaHkpOwotCXMrKzsKKyAgICBmb3IgKDsg eSA8IHllOyB5ICs9IHFzdGFibGVbcmJfbWVtc2VhcmNoX3FzX3V0ZjhfaGFzaCh5K20pXSkg eworCWlmICgqeHMgPT0gKnkgJiYgbWVtY21wKHhzLCB5LCBtKSA9PSAwKQorCSAgICByZXR1 cm4geSAtIHlzOworICAgIH0KKyAgICByZXR1cm4gLTE7Cit9CisKK2xvbmcKK3JiX21lbXNl YXJjaChjb25zdCB2b2lkICp4MCwgbG9uZyBtLCBjb25zdCB2b2lkICp5MCwgbG9uZyBuLCBy Yl9lbmNvZGluZyAqZW5jKQoreworICAgIGNvbnN0IHVuc2lnbmVkIGNoYXIgKnggPSB4MCwg KnkgPSB5MDsKKworICAgIGlmIChtID4gbikgcmV0dXJuIC0xOworICAgIGVsc2UgaWYgKG0g PT0gbikgeworCXJldHVybiBtZW1jbXAoeDAsIHkwLCBtKSA9PSAwID8gMCA6IC0xOworICAg IH0KKyAgICBlbHNlIGlmIChtIDwgMSkgeworCXJldHVybiAwOworICAgIH0KKyAgICBlbHNl IGlmIChtID09IDEpIHsKKwljb25zdCB1bnNpZ25lZCBjaGFyICp5cyA9IHksICp5ZSA9IHlz ICsgbjsKKwlmb3IgKDsgeSA8IHllOyArK3kpIHsKKwkgICAgaWYgKCp4ID09ICp5KQorCQly ZXR1cm4geSAtIHlzOworCX0KKwlyZXR1cm4gLTE7CisgICAgfQorICAgIGVsc2UgaWYgKG0g PD0gU0laRU9GX1ZBTFVFKSB7CisJcmV0dXJuIHJiX21lbXNlYXJjaF9zcyh4MCwgbSwgeTAs IG4pOworLy8gICAgfQorLy8gICAgZWxzZSBpZiAobSA8PSBTSVpFT0ZfVkFMVUUgKiBDSEFS X0JJVCkgeworLy8JLy9yZXR1cm4gcmJfbWVtc2VhcmNoX2tyKHgwLCBtLCB5MCwgbik7Cisv LwlyZXR1cm4gcmJfbWVtc2VhcmNoX3NvKHgwLCBtLCB5MCwgbik7CisgICAgfQorICAgIGVs c2UgaWYgKGVuYyA9PSByYl91dGY4X2VuY29kaW5nKCkpeworCXJldHVybiByYl9tZW1zZWFy Y2hfcXNfdXRmOCh4MCwgbSwgeTAsIG4pOworICAgIH0KKyAgICBlbHNlIHsKKwlyZXR1cm4g cmJfbWVtc2VhcmNoX3FzKHgwLCBtLCB5MCwgbik7CiAgICAgfQotICAgIHJldHVybiBzLXk7 CiB9CiAKICNkZWZpbmUgUkVHX0xJVEVSQUwgRkxfVVNFUjUKLS0tIHN0cmluZy5jCShyZXZp c2lvbiAxNTc4NykKKysrIHN0cmluZy5jCSh3b3JraW5nIGNvcHkpCkBAIC0yMDg4LDcgKzIw ODgsNyBAQCByYl9zdHJfaW5kZXgoVkFMVUUgc3RyLCBWQUxVRSBzdWIsIGxvbmcgCiAgICAg bGVuID0gUlNUUklOR19MRU4oc3RyKSAtIG9mZnNldDsKICAgICBmb3IgKDs7KSB7CiAJY2hh ciAqdDsKLQlwb3MgPSByYl9tZW1zZWFyY2goc3B0ciwgc2xlbiwgcywgbGVuKTsKKwlwb3Mg PSByYl9tZW1zZWFyY2goc3B0ciwgc2xlbiwgcywgbGVuLCBlbmMpOwogCWlmIChwb3MgPCAw KSByZXR1cm4gcG9zOwogCXQgPSByYl9lbmNfcmlnaHRfY2hhcl9oZWFkKHMsIHMrcG9zLCBl bmMpOwogCWlmICh0ID09IHMgKyBwb3MpIGJyZWFrOwo= --------------000907010806050601080000--