VecTripper: a SIMD Accelerated TRIP Searcher for Mac OS X

最終更新日：2011/12/3

English Page

VecTripperは、PowerPC G4/G5のAltiVecやIntel CPUのSSE, AVXを用いてを用いて高速にトリップの検索を行うツールです。AltiVecやSSEを持たないマシンでは動作しません。G4(7447A) 1.33GHzでは、パターンファイルを用いた検索で820ktrips/s, 正規表現による単純なマッチングで715ktrips/s, 連番検索で790ktrips/s程度の速度が出ます。

最新版ではIntel CPUにも正式対応しています。また、64bitアプリケーションになりましたので、Intel Core 2とLeopardの組み合わせでは64bit環境で動作します。32bit環境よりも15%程度高速になるようです。

12桁トリップにも暫定対応しました。

使い方

Readmeを参照してください。

パフォーマンス

Macに使われている様々なCPUについて、パターンファイル検索でのおおよそのパフォーマンスを表にしてみました。最高速度とは、(1GHzあたりの速度×歴代のMacに搭載された最高のクロック周波数) の値です。

マルチCPUなマシンでは検索スレッドを複数走らせることにより、コア数倍のスループットを得ることができます。

表 各CPUにおけるパフォーマンス

CPU	1GHz,1コアあたりの 速度(ktrips/s)	最高速度(ktrips/s)
G4(7410)	507*	254* (@500MHz)
G4(7447A)	615	1026 (@1.67GHz)
G5(970)	705	1903 (@2.7GHz)
Core 2 (65nm) 32bit	778	2334 (@3GHz)
Core 2 (65nm) 64bit	895	2685 (@3GHz)

*旧バージョンの数値

ダウンロード

ソースコードも同梱されています。コンパイルの方法等はReadmeを参照してください。

• VecTripper_20111203.tar.bz2 (664,648Bytes)
• (CUDA用試験版; 12桁専用, ソースのみ) VecTripper_cuda_test_090803.tar.bz2 (6,232Bytes)
• (少し前のバージョン) VecTripper_20090729.tar.bz2 (966,049Bytes)
• （旧版）VecTripper_20050809.tar.gz（223,331Bytes)
• （旧版）VecTripper_20050809b.tar.gz（223,457Bytes)

最近の変更点

2011/12/3

• いまさらAVXに対応してみた (12桁のみ)
3オペランド化で余計なmovdqaを消して、VEXエンコーディングで命令長が削れるものを削った程度なのですが、何故かSSE版と比べて25%ぐらい高速です。16bytes/clkのフェッチ帯域がクリティカルだったのだろうか。

2009/8/3

• CUDA用:
  • ちょっと高速化
  9800GT(112SP)で125M/s (位置指定あり)、105M/s (位置指定なし)。8600GT(32SP)で28M/s (位置指定あり)、23M/s (位置指定なし)。

2009/8/2

• CUDA用のをちょっと修正:
  • -dオプションで利用するデバイスの番号を指定できるように
  複数のGPUが存在する場合は、複数立ち上げて個別に-dオプションを指定してやれば全部のGPUが使えると思います (未確認)。
  • G200ファミリで立ち上げるスレッド数を増やした
  レジスタの上限に引っかからなくなるらしい。所有していないので効果は未確認。遅くなったり全く動かなかったりするようなら、main.cuの先頭の方にあるNUM_THREAD_G200マクロを弄ってください。
  • ちょっとバグ修正
  • ちょっと高速化

2009/7/31

• CUDA用のを置いてみた
12桁のみ。ソースのみ。CUDA SDKを入れて自分でコンパイルしてください。今のところ様々な制限があります。動作確認はLinuxでしています。Macでもコンパイルは確認していますが、所有機種のGPUのVRAMが128MBしかなく動作確認ができません。
• CUI
出力はUTF-8決めうち。表示以外にカレントディレクトリにout.txtを作ります。
• ターゲットは一つ+連番検出のみ
5文字以上の文字列のみ指定可。^と$で位置指定は可能。8連以上の(純)連番は自動で検索されます。
• あまり速度は出ない
9800GT(112SP)で110M/s (位置指定あり)、90M/s (位置指定なし)。8600GT(32SP)で25M/s (位置指定あり)、20M/s (位置指定なし)。位置指定無しの場合文字列の長さで速度が変化 (長いほど速い)。
例によってCUDAを初めて触ってみて1日ぐらいで書いたものなので、いろいろ変かも。

2009/7/29

• PPCとx86-64用のコードをちょっと最適化
• Core2 (65nm) 2.2GHz 64bit: 11.7M/s
• G5 2GHz : 8M/s
• G4 (7447A) 1.33GHz : 5M/s
ぐらい。

2009/7/9

• パターンファイル検索をいろいろ変えた
パターンファイルの構文がこれまでとは非互換なので注意してください。そのため読み込むファイル名は意図的にpattern.txtからtarget.txtに変えてあります。これまでのメタキャラクタである?が使えず、代わりにデフォルトで任意の位置にヒットするようになっています。位置指定としては^と$が使え、これらは正規表現と同じ使い方をします。また[]を使って[a-z0-9]のような指定もできます。詳しくはreadmeを読んでください。
パターンの数が少ない場合はこれまでと同じパターンマッチングアルゴリズムを使いますが、数が増えるとアルゴリズムが変わります (Aho-Corasick)。開始時に中で小さなベンチマークを走らせて、高速なアルゴリズムを自動で選択します。
8文字、位置指定無しのランダムな文字列をパターンに指定した場合の検索速度の変化はこんな感じ (2段増幅回路のBode線図ではない)。トリップ生成部が相対的に高速な12桁トリップでは10000パターンでピークの1/2以下に落ち込んでいますが、これは最悪に近い値で、英単語のような文字の出現順序に偏りがある文字列群を検索する場合はここまで速度は低下しません。例えば/usr/share/dict/wordsの先頭から10000語のような極端に偏った文字列群をパターンファイルに入れて検索すると、同じ10000パターンでも速度低下はほとんど起こりません。ちなみに、本来は検索速度はパターンの数には比例せず、検索対象の文字列長(短いほど良い)と最短パターン長(長いほど良い)に相関がある程度のはずですが、状態遷移の際のランダムアクセスによるキャッシュのヒット率がそのまま速度に現れているものと思われます。
Aho-Corasickのデータ構造には冗長性の大きい素のtrieをほぼそのまま使っています (failure遷移を高速化する程度の工夫はしています)。なのでメモリ効率が非常に悪く、例えば[0-9][0-9][0-9][0-9][0-9][0-9]のような事をして展開されたパターン数が百万以上のオーダになると、システムのメモリを圧迫してスワップを起こしてしまいます。これは今後改善すべき点ですが、これは部分文字列のマッチング速度に特化しているACゆえの代償で、さらに他のアルゴリズムを導入しないと改善は難しそうです。

2009/7/1

• PPC用のコードを最適化
• 最大の敵、gettimeofdayを始末
ループ毎に呼んでたらまさか10%も占めていたとは。結局
• Core2 (65nm) 2.2GHz 64bit: 11.4M/s
• Core2 (65nm) 2.2GHz 32bit: 11M/s
• G5 2GHz : 7.7M/s
• G4 (7447A) 1.33GHz : 4.8M/s
ぐらいに。

2009/6/30

• x86-64用のコードを最適化。ついでにPPC用のも最適化。
最終的にピーク検索速度は
• Core2 (65nm) 2.2GHz 64bit: 10.1M/s
• Core2 (65nm) 2.2GHz 32bit: 9M/s
• G5 2GHz : 6.8M/s
• G4 (7447A) 1.33GHz : 3.8M/s
ぐらいになりました。この手に限る

2009/6/29

• まあ、アセンブラを使えばiccなぞ必要なくなるわけだ。
i386で9M、x86_64で9.3Mぐらい。x86_64は真面目に実装してないのでもうちょっと改善の余地あり。

2009/6/28 (その2)

• これはひどい、バイナリを更新するのを忘れていたようだ。
なのでさっきまで上がっていたのはIntel CPUでは本来の速度が出ません。
• バックグラウンドで発見した時はDockのアイコンで通知するように
Thanks to CTBadge
• ちょっと高速化

2009/6/28

• 連番検索できるようにした
• 12桁トリップのパターンファイル検索で自動的に8連以上の(純)連番トリップを検索するようにした
オーバーヘッドが小さかったので (1-2%) 特に無効化するオプションは付けてません。
• i386用のコードをちょっと見直して高速化
• コア部分をiccでコンパイルしてみた
これだけで恐ろしく(i386では20%ぐらい)高速化された。やはりx86 SIMDのintrinsicsに関してはgccの吐くコードを信じてはいけないのである。コンパイル済みの.sファイルがソース中に入ってるので、Xcodeのプロジェクトではこれをアセンブル/リンクのみするようにしてます。

ひととおり機能が実装されたのでVecTripperの12桁トリップ検索について少しまとめてみると、

• 生成する鍵空間は128¹² (0x25-0x7eと0xa1-0xc6)
• パターンファイル検索時のピーク速度は1スレッドあたりおおよそ
  • Core2 (65nm) 2.2GHz 64bit: 8.7M/s
  • Core2 (65nm) 2.2GHz 32bit: 8.4M/s
  • G5 2GHz : 5.2M/s
  • G4 (7447A) 1.33GHz : 3M/s
• DESと違って処理が32bit単位なのでbitsliceとかをせずとも容易にSIMD化可能
• 生成速度自体がかなり高速なので検索部分が足を引っ張る

等。

2009/6/27

• GUIのバグをいろいろ修正
• <>とかは普通に使えるのか...逆に$#は1文字目に来てはいけないのね

2009/6/26 (その3)

• その他マルチスレッドでの不具合をいろいろ修正

2009/6/26 (その2)

• マルチスレッドで動かすとカウンタのmutexでえらく時間を食うのを修正

2009/6/26

• やたらめったら乱数生成しないようにして、高速化
パターンファイル検索時には、ほぼ理想に近い速度で回るようになりました
• バグ修正

2009/6/25 (その3)

• 12桁のパターンファイル検索に対応
これで検索速度は昨夜の2倍ぐらいになったはず...

2009/6/25 (その2)

• レジスタ数にものを言わせてスループットを稼ぐ作戦
x86-64にてそれなりに速度向上
• 速度表示をktrips/sにした

2009/6/25

• いろいろおかしかったのを修正
• SFMTにした
• ちょっと速くなった

2009/6/24

• 12桁トリップに暫定対応
今のところ正規表現検索のみ。なのでいろいろ足枷になって遅いです (Core2 2.2GHzでコアのみ6.6M/s/coreぐらいなのが、生成検索を含めると3.6M/s/coreぐらい)。コア部分には一応SSE/AltiVecを使ってるけど、1時間ぐらいでへろへろっと書いたのでこれといった最適化はしてません (32bitと64bitで速度が変わらないという怪現象が...gccめ)。暇な時にasmで書き直す予定。

2009/1/13

• Command-Qさんに頂いたアイコンを追加

2009/1/12

• i18n/l10n

2008/12/29

• Intel 64bit向けのsboxをちょっぴり最適化して速度向上

2008/12/23

• 最適化フラグと一部コードの変更でIntel CPUでの速度が多少向上
• 検索方法の指定によって正規表現入力用テキストフィールドを無効にするように
• プロセス優先度の設定を追加

2008/12/21

• 3年ぶりに更新。
• 団子厨さんからsbox高速化のコードを頂いたので組み込み、PPCで2割程度の速度向上
• いまさらIntel CPUに対応
24h突貫工事なので問題が残ってるかも。まあ、wineでwin用のを動かせばいい話ではある。
• Core2+Leopard向けに64bit化
G5より..はやーい

スクリーンショット

勝手にリンク

他のトリップ検索ソフトへのリンク。

Mac用

• Danae
OS9以下 or G3以前だと事実上これの一択な気も。
• とりっぱー for Mac
…

Windows用

• 見知らぬ国のトリッパー（w
言わずと知れた元祖トリップ検索ソフト。GUI
• Tripcode Explorer
はやい。GUI
• mty
はやい。CUI
• Million_seeker
大量検索に向いてるらしい。CUI
• Trip-Mona
一時期（たぶん）一世を風靡した、トリップ検索の考え方を変えたソフト。CUI

その他

• うとりっぱ〜
オープンソースのトリップ検索ソフト。PPC MacではSIMDを使わないので遅いです。

---

もどる

---

このページはリンクフリーです。
一応連絡先