投稿

12月, 2024の投稿を表示しています
イメージ
butterfly search 4.2 をリリースしました。   リリース先:   https://www.vector.co.jp/soft/winnt/util/se437071.html (vectorさんでの審査後に公開されます。執筆時点では旧バージョンが公開されています) 変更点は処理速度向上と表記ゆれ検索機能の追加になります。 ■新機能 表記ゆれ検索 この機能は聞いた事ないと思います。世界初※ではないでしょうか。 表記ゆれと言っても、タイポ(複数文字の誤りや抜け)を見つける機能となります。 簡単にいうと ・disc → disk    ・flag → flg を見つけてくれます。 対象は「アルファベット」と「数字」と「_」の列のみとなります。 編集距離(レーベンシュタイン距離)を意識しています。 ※Word等にも表記ゆれ検知はありますが辞書にない単語を表示しているだけだと思います。 ■実力 品質が非常に高いと言われるLinuxのソースコード(https://github.com/torvalds/linux)で確認したいと思います。 「kernel」という単語を「一文字違う」条件で検索すると、 一瞬にして5件のkernelバグ?(たぶんスペルミス)を見つけました。 著作権表記「Copyright」を「一文字違う」条件で検索すると、 スペルミスが4件見つかりました。著作権違反?(笑) ぜひbutterfly searchを活用して表記ゆれを見つけてください。 コードレビュー時に使用すれば、みんなびっくりする事間違いなしです。 ■表記ゆれ検索の使い方 マニュアルの整備が追い付いていないのでここにメモを書きます。 使用方法 検索文字列を入れて「表記ゆれ」ボタンを押下します。 ヒント (1)検索文字には、?と*が使用できます。 ?は1文字を意味します。 *は複数文字を意味します。 「A??B」 で表記ゆれ検索すると、例えば「AAAB」がヒットします。 「A*B」 で表記ゆれ検索すると、Aで始まってBで終わる単語がヒットします。 下記の表記ゆれ条件はすべて外しても「?」「*」が含まれていれば検索します。 (2)シフトキー シフトキーを押下すると?と*の部分のみ表示されます。目がカチカチするのでこの機能を入れています。 ※1つ...

butterfly searchのホームページ移転

 butterfly searchのホームページですが、代理公開してくれているvectorさんのホームページサービスがが2024年12月20日で終了してしまったため、下記(Google サイト)の方に移転しました。 旧:http://hp.vector.co.jp/authors/VA031523/ 新:https://sites.google.com/view/butterfly-search/ 今後ともよろしくお願いいたします。

malloc,TCMalloc,mimallocによる性能比較(各種メモリアロケータによる性能評価)

イメージ
■はじめに 高速化のアプローチとして複数スレッドによる並列化があるが、並列度が上がるほどに管理コストがかかるので単純に高速化へは繋がらない。 そんな中で、malloc(というかfree)が遅いという事に気が付いたので、その調査結果と考察を載せておく。 butterfly searchのアルゴリズムとの相性が良いかどうかそういう結果になると思う。 ■メモリアロケータ 3種類 malloc(標準) : 標準のmalloc。 Visual Studio 2022 C++に組み込まれているそのままのメモリアロケータ。 TCMalloc :google作成。C/C++用メモリアロケータ。高速なマルチスレッド実装が特徴。 mimalloc :パフォーマンス特性に重点を置きMicrosoftによって開発された、自由かつオープンソースのコンパクトな汎用メモリ・アロケータ。 ※他にもメモリアロケータはあったがコンパイルが上手くいかないので断念 ■テストの内容 butterfly searchでテキストデータをインデックス化する時間を測定する。処理は大きく2つに分かれている。 STEP1:単語の抽出。指定したスレッド数でメモリの取得解放を繰り返す。 STEP2:データのソート。単一スレッドでメモリの取得解放を繰り返す。(マルチスレッド化不可処理) ※各STEPの出力はファイル。なのでメモリは基本的にはSTEP毎に解放する作りになっている。 ※指定するスレッド数(並列度)は1と32の2通り。 ■評価環境 CPU:AMD Ryzen 9 3950X メモリ:48GB OS:Windows11 コンパイラ:Visual Studio 2022 C++ ■結果   mimallocが一番早いという結果になった。 ※値が少ないほど高速 ※メモリの処理時間を抜粋したものではなくbutterfly searchでの開始・終了時間 ※インデックス対象のテキストサイズは13Gバイト 詳細        ※値が少ないほど高速                                  ...