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つ...
投稿
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バイト 詳細 ※値が少ないほど高速 ...
butterfly search 4.1 をリリースしました。
- リンクを取得
- ×
- メール
- 他のアプリ
butterfly search 4.1 をリリースしました。 リリース先: https://www.vector.co.jp/soft/winnt/util/se437071.html (vectorさんでの審査後に公開されます。執筆時点では旧バージョンが公開されています) 変更点は処理速度と安定化になります。クラッシュする事が減っていると思います。 ■技術的な話 ・ファイル名の検索 高速化に関してはファイル名のみを検索した際に、CPUを12ケ割り当てるようにしました。 これにより12倍速になっているはずです。 それでも、Everythingの検索のほうが速いです。ファイル名はインデックス化していないので勝てないです。 ・ファイルアクセス CFileを使用してアクセスしていますが、CFileが遅いことに今更気が付きました。 CFileの呼び出しを減らすことでwriteの速度は2倍くらい向上しています。 ちなみにCStringは極悪なほど遅いので、速度を求める処理にCStringを使用してはいけません。
butterfly search 4.0 をリリースしました。
- リンクを取得
- ×
- メール
- 他のアプリ
リリース先: https://www.vector.co.jp/soft/winnt/util/se437071.html (vectorさんでの審査後に公開されます。執筆時点では旧バージョンが公開されています) 大きな変更点としては、処理速度の改善があげられます。 コンパイラをVisual Studio 2022にして、アプリを32bit→64bit化しています。 これによってボトルネックだったメモリの使用上限2GB(4GB設定だけど実際には2GBくらい/理由は後述)が無くなりました。 ポインタサイズが2倍(データ量が2倍)になり、PCに求めるスペックも2倍になりました。 結果的には思ったより時間短縮にはなりませんでしたが、今後CPUのスレッド数が増えれば時間短縮になっていくと思います。 動作するスレッド数はメモリの搭載量に比例して変化するように作ってあります。 現在は最大12スレッドで動作するようになっています。12の理由は私が使用しているPCがRyzen 5 1600(12スレッド)だからです。 機能面としては、日付のヒートマップ画面の追加があります。何月何日に何が起きたのかを2次に展開した形で確認できると思います。年号(大正、昭和とか)も認識するはずです。こちらは現在もバグばかりの状態なので今後に期待していただければと思います。 ■技術的な話 32bitアプリの延命措置として/LARGEADDRESSAWAREオプションをよく使用すると思います。 /LARGEADDRESSAWAREオプションをコンパイル時に使うと2GB→4GBまでメモリを使用できるようになると書いてあります。ですがこれは、実際にはメモリを一度も開放しない場合の話。malloc()後free()しないのであれば4GB近くまで使えますが、 malloc()とfree()は繰り返しますよね。そうすると仮想アドレスが断片化するので、大きなサイズの仮想アドレスの確保がうまくいかなくなります。 例えるなら電話番号0000から9999までの1万回線を連続して所持したいという希望があった時、設備にも余裕があったとしても古い電話帳では連続した空きは見つかりませんね。そんな感じです。
SVN リビジョン1000はありません 「No such revision xxxxx」
- リンクを取得
- ×
- メール
- 他のアプリ
butterfly searchのソースをコミットしようとしたらTortoiseSVNが 「リビジョン1000はありません」って言ってくるじゃないですか。 もうこのカメちゃんったら、寂しがりやさんなのね。。。 惨事が起きていると理解し、SVNのリポジトリが壊れたことが分かったのだけれども、SVNのリポジトリはGoogleドライブに置いているだよね。Googleドライブが壊れる訳ないよね。 症状としては、リビジョン1000のコミットではエラーが出ないけど、その次の1001のコミットで1000に関してのエラーがでる。 処置としては、、、 リビジョンを999に戻して、SVNのリポジトリをGoogleドライブ(Gの仮想ドライブ)に置かない。でとりあえず復旧しました。仮想ドライブ上では操作しても復旧できませんでした。 SVNはリビジョン1000毎にフォルダを作るのだけれど、それがGoogleドライブ上ではうまく行かないって事なんだろうな。butterfly searchで検索Gドライブを検索させるとエクセプションが発生するのでGoogleドライブが提供している何かのAPIに問題があると思われる。 障害発生時のバージョン情報 TortoiseSVN TortoiseSVN 1.14.5, Build 29465 - 64 Bit , 2022/09/24 08:31:31 ipv6 enabled Subversion 1.14.2, -release Google ドライブ バージョン: 73.0.4.0
butterfly search 3.0b をリリースしました。
- リンクを取得
- ×
- メール
- 他のアプリ
butterfly search 3.0b をリリースしました。 リリース先: https://www.vector.co.jp/soft/winnt/util/se437071.html (vectorさんでの審査後に公開されます。執筆時点では旧バージョンが公開されています) 大きな変更点としては、インデックスに登録する条件を増やしました。 今までインデックスのキーとして登録していなかった単語同士の組み合わせも 登録するようにしました。これにより今まで苦手だった、よく登場するけどその組み合わせはあまりないという条件、 例えば「0+0」の検索がまともな速度で動作する様になりました。英語の文章検索も速くなっています。 これによる副作用としては、キーの数が1.5倍くらい増え、インデックスの作成時間も1.5倍くらい長くなりました。 ■「0+0」の場合 ・3.0aまで → 「0」,「+」の2つをインデックスに登録。 ・3.0bから → 「0」,「+」の2つをインデックスに登録しさらに、 「0+」,「0+0」,「+0」の3つをハッシュ化後にインデックスに登録。 ■「This is a Pen.」の場合 ・3.0aまで → 「THIS」,「IS」,「A」,「PEN」,「.」の5つをインデックスに登録。 ・3.0bから → 「THIS」,「IS」,「A」,「PEN」,「.」,「 」の5つをインデックスに登録しさらに、 「THIS 」,「 IS」、「IS 」,「 A」「A 」,「 PEN」「PEN.」, 「THIS IS」「 IS 」,「IS A」,「 A 」,「A PEN」,「 PEN.」の14つをハッシュ化後にインデックスに登録。 ■「今日はいい天気ですね。」の場合 ・3.0aと3.0bで違い無し → 「。」、「い」、「いい」、「いい天」、「い天」、「い天気」、「す」、「すね」、 「すね。」、「で」、「です」、「ですね」、「ね」、「ね。」、「は」、「はい」、 「はいい」、「今」、「今日」、「今日は」、「天」、「天気」、「天気で」、「日」、 「日は」、「日はい」、「気」、「気で」、「気で...