history

青木日記 RSS

<前の日 | この月 | 次の日>

2004-05-30

refctl.rb

昨日ふれた「独自のリファラ解析プラグイン (refctl.rb)」 が欲しい人は CVS で取ってください。 cvs -d :pserver:anonymous@cvs.loveruby.net:/src co tdiarytools で取れます。 ただし後に述べるように、tdiary.rb にパッチが必要です。 これもやはり CVS に入っている、tdiary.rb-referer_day_only.diff を当ててください。

refctl.rb は解析というよりはフィルタです。 単純に検索エンジンからのリンクを除外して アクセスの多い順に並べているだけなので、 00default.rb とあまり変わりません。 ちょっと特徴的なのは URL のホスト部分を見ることで、 同じホストから来たリファラはアクセス数に関らず隣に並びます。

いずれにしても disp_referrer2 に比べると機能が低すぎるので 代用にはならないでしょう。 あくまで機能をあきらめて速度を稼ぐ類のプラグインです。 以下のようなポリシーの元に仕様を決めました。

  • permalink だけを検出する。 検索エンジンやアンテナからのリファラは不要。
  • でもアンテナからのアクセスがいくつあるのかだけは知りたい。 「どのアンテナ」という情報は不要。
  • 日本語できれいに表示するのはあきらめる。 @referer_table のメンテ放棄。

このポリシーの元ではリファラ情報は三つのクラスに分割できます。

  • アンテナ (アクセス数が必要)
  • 検索エンジン (単に捨てる)
  • 残り (URLが必要)

できるだけ重くならないようにクラスを判定するため、 latest へのアクセスはすべてアンテナとみなして アクセスが来た時点で特殊な URL にマップします (tdiary.rb にパッチが必要)。 検索エンジンは自動では判定できないので、 disp_referrer2 が使っている判定方式を流用します。

ただしここで disp_referrer2 の実装をそのまま使ってしまうと 速度はほとんど変わらなくなります。 昨日書いた通り、disp_referrer2 のボトルネックは検索語を取得するコードです。 大量のリファラに対して大量の正規表現 (しかも効率が悪い部類に属するパターン) を適用しているため、計算量が極端に上がっています。 refctl.rb では、何を検索したのかという 情報をあきらめることによって計算量を下げました。

disp_referrer2.rb の最適化

ちなみに、細かくベンチマークを取ってみると、 必ずしも情報を減らさなくても速度は上げられることがわかります。 例えば ja/disp_referrer2.rb に以下のような正規表現があります。

%r{^http://.*?\bgoogle\.([^/]+)/(search|custom|ie)}i

これを以下のように変えるだけで コストは大きく下がります。

%r{\Ahttp://(?:[^./]+\.)*?google\.([^/]+)/(search|custom|ie)}i

工夫したのは以下の点です。

  • 「^」ではなく「\A」を使う。
  • 「[^./]」 を使うことで、host 部分に対するマッチであることを明示する。

この工夫の意義を証明するため、 以下のように極端なケースにおけるベンチマークをとってみましょう。

# ベンチマークテスト
require 'benchmark'
 
n = 100_0000
url = 'http://a/' + ('googl.' * 10) + 'com'
Benchmark.bm(16) {|x|
  x.report('original') {
    n.times do
      %r[^http://.*?\bgoogle] =~ url
    end
  }
  x.report('after') {
    n.times do
      %r[\Ahttp://(?:[^./]+\.)*?google] =~ url
    end
  }
}
 
# 結果
                      user     system      total        real
original          6.960000   0.000000   6.960000 (  6.967214)
after             0.910000   0.000000   0.910000 (  0.911670)

実に 7 倍速。いろいろな条件で計測してみたところ、 改善後のパターンは改善前のパターンに比べ 25%〜800% の速度向上が見られました。 特に上記のようにマッチが失敗する場合に速度が向上します。

しかしこれでは失敗する場合にしか速度が上がらないように見えるので、 もう少し実地に近い条件でもデータをとってみましょう。 家に来る実際のリファラは 240 種類前後、 このうち Google のリファラが 100 種類前後、 平均 URL バイト長は 120 バイト、うちホスト部分が 21 バイトです。 一方 disp_referrer2.rb には正規表現が 59 個登録されています。 これを元に平均的なマッチ環境を想定し、 上記二つの正規表現の実行時間を測定すると、 Celeron 333A のマシンでは以下のような差が付きました。

                      user     system      total        real
dispref           0.910000   0.000000   0.910000 (  0.913449)
aamine            0.200000   0.000000   0.200000 (  0.197613)

以上から、 正規表現マッチ部分については平均 450% の速度向上が期待できます。 disp_referrer2 の消費時間全体に対して正規表現マッチがどれくらいの 割合を占めているかはきちんと計測していませんが、 以前ベンチマークをとったときには parse_as_search が上位に来ていたので相当有効だと思います。 キャッシュと Nora がなくても現状の 2〜3 倍速はいけるんじゃないかな。 特にリファラが多い環境では効果が高いはずです。

(19:30)

CVSクラック (2)

http://www.dm4lab.to/~usa/ruby/d/200405c.html#id20040530_P1 より

> _ 「オープンソース関連が狙われてるところを見ると、
> 意図的にやってるんだろうなあ」って、最近やられてる
> のはたいていCVSの穴からやられてる(らしい)わけで、
> そうなると必然的にオープンソース関連のところばかり
> になるんじゃないでしょうか。

そっか。因果が逆の可能性があるわけですね。

(21:22)

本日のツッコミ(全7件) [ツッコミを入れる]
通りすがりのバグ指摘人 (2004-05-31 17:29)

RSS を
http://http://i.loveruby.net/d/20040530.html#p01
のように吐いてます。

ささだ (2004-05-31 19:04)

正規表現はさっぱりわからないんですが、onigurumaと以前の正規表現エンジンで、傾向は同じものなんでしょうか。

青木 (2004-06-01 01:38)

RDFのバグの御指摘ありがとうございます。
その場しのぎでプラグインを修正したのが間違ってました。

青木 (2004-06-01 02:09)

今回のはマッチの意味を考えてパターン自体をせばめて
いる (マッチしない文字列を増やした) ので、どんな
エンジンであっても性能がよくなる可能性が高いです。
例えば元のパターンは 'http://host/google.com/search'
や "aaa....a\nhttp://google.com/search" にもマッチ
しますが、変更後のパターンだとマッチしません。
つまり表現を変えただけではなくて、意味が違うんです。

青木 (2004-06-01 02:19)

あ、%r<\Ahttp://[^./]*?google> だとさらに速い。

青木 (2004-06-01 02:50)

嘘だ。[^./] じゃ排除しすぎだろ。

zunda (2004-06-12 20:06)

ヒントをありがとうございます。正規表現を変えて試してみましたが、ほとんど速度は変わりませんでした。よくみてみたら、disp_referrer.rbの中で検索エンジンの正規表現を使う回数は、もともとあまり多くないようにしてあったのが原因のようです。
爆速disp_referrerを夢みてたんだけど…。あ、もしかして変な小細工するより総当たり=~の方が速いか?…続く(おい

名前
メールアドレス

<前の日 | この月 | 次の日>
2002|04|05|06|07|08|09|10|11|12|
2003|01|02|03|04|05|06|07|08|09|10|11|12|
2004|01|02|03|04|05|06|07|08|09|10|11|12|
2005|01|02|03|04|05|06|07|08|09|10|11|12|
2006|01|02|03|04|05|06|07|08|09|10|11|12|
2007|01|02|03|04|05|06|07|08|09|10|11|12|
2008|01|02|04|05|06|09|10|
2009|07|
2010|09|

Copyright (c) 2002-2007 青木峰郎 / Minero Aoki. All rights reserved. LIRS