13/10/13 23:47:17.62 B/E+227R0
待て屋ってソース公開されてたっけ？
それなら、メモリ消費の少ないその方法を採用してみるとか。
401:混沌 ◆Chaos/geeeIV
13/10/14 00:06:18.79 HNICMWPj0
>>400
自分は ずっと前のトリッパーをちょこちょこ使っていた程度で、待てやとかも使ったことはないんですが
ただ、展開するから高速にマッチ出来るんじゃないかと思うｗ
このスレの過去ログとかほとんど見てないけど、初期はパターン数制限あったのがある時期に制限がなくなったってのが
たぶんその時に、パターンを展開して（おそらくはマッチする法のトリップも相当数メモリに展開してからまとめて）
アルゴリズム検索（２分検索みたいな？）を取り入れたんじゃないかと予想
メモリ展開して最適化するからこその、大量検索パターンを高速にマッチできてるんだと思いますよｗ
402:名無しさん＠お腹いっぱい。
13/10/14 02:51:29.17 Ehj1Nv8O0
一応、パターン作成＋結果からトリップ抽出＋ローマ字変換＋篩い掛けできるセットを配布しておきます。
ソースコードも添付しますので、参考までにどうぞ。
URLﾘﾝｸ(www1.axfc.net)
403: ◆ISONOIIISI
13/10/14 02:52:29.66 Ehj1Nv8O0
あ、私はID:KYI8bH6i0です。
404:名無しさん＠お腹いっぱい。
13/10/14 03:17:32.75 a2gerbx00
>>391
>>> 正規表現の場合、展開数で制限を設ける方式ですか？
>> おおまかに言えばそうですね。
>> 厳密に言えばハッシュ値の数で決まります。
> ｽﾚﾘﾝｸ(esite板:100-101番)
なんかもう全部展開しちゃってる感じ？
>>401
先にメモリに展開する場合、展開したテーブルがキャッシュやメモリから溢れると思いっきりロスしそう。
展開数が一定範囲を超えたら正規表現とのマッチ処理をJITするのが最速なのかな・・・
405: ◆Meriken//XXX
13/10/14 04:18:18.49 cHLdpSNUP
MTFではパターンの一部(5文字)からハッシュ値を作成していて、
ハッシュ値の生成に必要な分は最初に全て展開しています。
この方法だと非常に強力な正規表現が使える代わりに
メモリの消費量は大きいです。
正規表現の部分は2年前に作ってからほとんどいじっていないので
改善の余地がかなりあります。待て屋のマッチングのアルゴリズムは
かなり特殊なのですが、これについては鳥屋氏にいろいろ教えて
いただいたので、ぜひMTFに取り込みたいところです。
406: ◆Meriken//XXX
13/10/14 04:22:38.64 cHLdpSNUP
>>369
どもども。10桁トリップ検索のAVX2対応の作業がおわったら新しい開発版を
うｐするのでお楽しみに。
407: ◆Meriken//XXX
13/10/14 04:34:56.58 cHLdpSNUP
>>389
> まあもともと256bit化したときにキャッシュに乗り切るようにあんな構造にしたので。
なるほど、そういうことだったんですね。流石です。
> 107MTPSあたりで頭打ちになります。
これはおかしいですねえ。ちょっとMTFがどうなってるか調べてみます。
408: ◆Meriken//XXX
13/10/14 05:17:58.05 cHLdpSNUP
10桁トリップのAVX2対応のルーチンがようやく動きました。
AVX(8スレッド): 23.65M TPS
AVX2(8スレッド): 43.44M TPS
AVX2(4スレッド): 39.04M TPS
>>383よりだいぶましになりました。
CPUを定格に戻せば48.40M TPS出る計算です。
HTの効きは今ひとつなので、まだキャッシュの使い方に
改善の余地がありそうです。
あとは最終転置やキー生成の処理の見直しですね。
409: ◆Meriken//XXX
13/10/14 05:39:05.79 cHLdpSNUP
>>389
12桁トリップ検索はこんな感じです。速度が出ないのはなかなか謎ですねえ。
AVX(8スレッド): 117.31M TPS
AVX2(8スレッド): 215.71M TPS
AVX2(4スレッド): 184.12M TPS
410: ◆Meriken//XXX
13/10/14 08:45:16.44 cHLdpSNUP
キー生成のルーチンを見なおして、10桁トリップ検索の速度が
少し上がりました。
AVX2(8スレッド): 43.44M TPS -> 46.02M TPS
定格で51.28M TPS相当なので、まずまずといったところでしょう。
もうちょっと搾り取れそうな気もしますが、かなり疲れたので
取りあえず休憩することにします。