技術解説

技術解説

GNU diff はなぜ 10GB で 150 秒かかるのか — ソースを読んで分かった「全部読んでから比べる」設計と、GNU grep が速いままの理由

10GB(約 1 億行)のテキスト 2 本を比べると、GNU diff は 150.93 秒、私の作っている UwDiff の uvd は 21.23 秒でした。使ったメモリは 17.23GiB と 0.41GiB です…
技術解説

速さの話をする前に決めること — 3OSテスト#0:cold と hot の作り方・答えの持ち方・VMware の数字の扱い、ただし Linux は仮想機で Windows には cold を作る標準の手段が無い

秒だけでは足りません。 「10GB のログが 0.3 秒で開きました」と書かれた記事を読んで、同じファイルを自分の機械で開いたら 12 秒かかった——そういう経験は、たぶん誰にでもあります。嘘をつかれたわけではありません…
技術解説

diff や grep で比べられないファイルはなぜ多いのか? — Shift-JIS・圧縮・Word・PDF・10GB を1つの道具で比べたくて UwDiff を作った

結論から書くと、diff や grep が弱いのではなく、「日本語の文字コード」「圧縮」「Office・PDF」「数 GB」「OS をまたぐ」が重なると、どの道具でも何かしらの指定や別の道具が要るからです。 その組み合わ…
技術解説

無料版 uvf の3つの直し — Full Spectrum⑤:ヒットした行の書き出しが 4.70秒→2.68秒・確保メモリ 28GB→0.4GB、ただし ripgrep 2.83秒 とは同等どまり

この連載の前の4回は、どれも有料版 uvp の索引の話でした。索引を作らない無料版 uvf には、別の遅さが残っていました。 全体テストの結果を眺めていて、無料版だけが ripgrep に負けている式が1つ見つかりました…
技術解説

10GBの2回目はどこで縮んだか — Full Spectrum④:前置できない正規表現が ripgrep の hot 13.54秒に対し uvp 0.73秒、ただし±N行の2語目の突き合わせは1.24倍の同等どまり

3GB で速くなった仕組みが、10GB でもそのまま効くとは限りません。 前の2回で入れた「行の骨格」と「ブロックの印」は、3GB の測定で決めた仕組みです。10GB・1億行で全体テストを流すと、2回目にまだ重い式が4つ…
技術解説

klogg・ripgrep・grep・PowerGREP から何を取り入れたか — UwView が他のツールに学んだ機能と、あえて入れなかったもの(First Light〜Full Spectrum)

UwView は、ほかのツールに負けた記録の積み重ねでできています。 klogg に機能表で負け、ripgrep に正規表現で負け、grep のパイプには「自動化では今もかなわない」と書いてきました。そのたびに、相手の良…
技術解説

開かなくてよいブロックを先に知る「ブロックの印」と1MBのブロック — Full Spectrum③:素の検索で ripgrep の hot 0.31秒に対し uvp 0.17秒、ただしどこにでもある語では印を確かめる分だけ4%遅い

3GB の OpenStreetMap の XML を 1MB ずつに切ると 2,893 個のブロックになり、そのうち 東京 が入っているのは 910 個でした。 残りの約 7 割は、開く必要がありません。けれど「開かな…
技術解説

ヒットしない行のかたまりを読まずに飛ばす「行の骨格」 — Full Spectrum②:ripgrep の -E -v より hot で28.2倍、ただしどのブロックにもヒットがある式では同等どまり

9,224万行のうち、ヒットするのは1行でした。 3GB の OpenStreetMap の XML で ^ + uvf・uvp は私が作っている UwView の検索コマンドです(uvf は無料版、uvp は有料版 U…
技術解説

Shift-JIS・EUC-JP・UTF-16 を索引の中で UTF-8 にそろえた — Full Spectrum①:ripgrep の -E より2回目から5.4〜38.8倍、ただし1回目は ripgrep が1.2〜1.5倍速い

変換が毎回入っていました。 Shift-JIS の 3GB を探すと、ヒットした行を数える前に、3GB 分の文字コード変換が走ります。2回目も、3回目も、同じ変換です。 索引を持っているのに、なぜ毎回変換していたのか。そ…
技術解説

ripgrep と同じ1コマンドで、12本・7形式・zip・pbf を探せるようにしました — Wide Field⑮(最終回):無料版は同等のまま、uvp はカーネル8.6万本で4.0倍、1.5倍を超える負けは2種類

2種類だけ残りました。 14回かけて、ripgrep に負けている場所を全部数え直したら、1.5倍を超える負けは2種類でした。どちらも有料版 uvp が索引を持つ代価です。 探せる入口を7つ増やしておいて、速さの負けが2…