F# でコマンドレットを書いてる pt.44
krymtkts/pocof 開発をした。
前回の対応 で非同期のバグが云々言ってたやつは、普通に immutable なデータ構造に起因するバグだった。ショボ。 a9e5bab
Prerelease 出すにあたり最後に解消しておきたいのが、
-NonInteractive時に結構な確率で Pester のテスト ≒ end-to-end テストがコケるところだ。いわゆる flaky test 化してしまった。
前に書いた ↑ は検討外れで、検索可能なプロパティの一覧を保持する際の内部データに F# の Map を利用していたので、非同期で要素が追加された際に結果が反映されないというものだった。
要はただの凡ミスだったわけなので .NET の非同期コレクションで置き換えて解消した。
他データ読み込み中に操作がない場合の描画間隔を調整したり #198 細々とした修正を入れている。
他にも試したいことがあったのだけど、うまくいかなくて頓挫した。 以下に記すのは思考の整理のためのその記録。
まず code coverage の計測を coverlet から altcover に変えてみようと思い、試してみた。 coverlet は F# が生成する IL 向けにチューニングされてないので、コード上に現れない微妙な branches のせいで coverage を落とす。↓ これ。
Multiple branch points created for F# string slice · Issue #1208 · coverlet-coverage/coverlet
そのため F# らしく書けない事がある。 altcover でそれが解消せんかな的なことを考えて試してみた。 また F# の OSS を使うという点でも良い。 けどデフォルト設定で altcover で計測すると pocof 以外のバイナリも検査対象になり、そのせいか実行速度が 5 倍くらいになってしまった。 なんてこった。 対象のアセンブリを絞る設定が要るようだ。 でも設定してみても速くなったり F# の IL に最適化される確証ないなーと思ったのでこれは今のところナシとした。 sandbox で試してみてから pocof に導入できるか検討するのがまともな判断かな。
次に pocof で大量データを操作すると遅い件に関する対応だ。 この対応として非同期で描画して遅く感じさせない改良を入れてきたけど、肝心の検索自体は速くなってない。 内部データの seq (実際は ConcurrentQueue) に対して正規表現で検索し、件数を数えるので、時間計算量が O(N) かかってる。 もちろん件数を数えるときにも O(N) かかってる。
コレクションを分割して Task で並行処理したら速くならんかなと試してみたが更に遅くなった。
元々 CPU bound な処理だから並列じゃない限り速くならんのよな。
そもそも内部データの seq を分割する Seq.chunkBySize や処理後の Seq.concat で O(N) かかるし。
ただこの過程で Array.Parallel や F# Parallel Sequences を知ったので、なんか参考にできるのかも知れない。
他の方法として内部データ構造の変更が思いつくので、 ChatGPT や GitHub Copilot に相談してみた。
彼らは初め「Trie にしたらいいやん」って言ってきた。
プロパティ毎に Trie 作成するってことかあ？と思ったので、でも「 1 億要素あって PSObject の任意のプロパティに対して正規表現の検索が可能でないとあかんねんけど...」と伝えたら「それはデータ構造だけやと理論的に難しいで」とのことだった。
そら難しくなかったらお前に相談せんやろ...とりあえず検索パターンごとの最適化みたいなのを先に試してみるべきなのかも知れん。
例えば AND 検索であれば、クエリが追記されていく限りはそれより前の絞り込み結果に対して検索する方が少ない N 減で済むから速くなるとか。 でもこの方針だと、 OR 検索の場合や非同期コレクションが更新された場合は常に全体を検索せねばならず、どうにもならんけど。 pocof は無駄にリッチに AND 検索と OR 検索ができて、正規表現とワイルドカードのどちらでも検索もできるため、打つべき手段も色々ややこしいことになってる。 他に、検索機能を database なんかの外に出してみたらどうかとも思いつくが、なんか負けた気がするからそれは却下。 自前の何かで解決したい。 今のところ、全列に索引が貼られたテーブルみたいな如何にもメモリ食いそうな構造しか思いつかないので、なんか探求してみる。
そもそもの話、生の seq や ConcurrentQueue の件数を取ってみてもそんな爆発的に遅くないねんよな。
つまり pocof で入れてる実装に起因して遅い可能性も微レ存だと。
PSObject を文字列にするあたりだとか、存在するかわからないプロパティに reflection でアクセスするあたりだとか、なんか PSObject の取り扱いが難しいんじゃないのこれ。
前にプロパティ一覧取ってメモリ爆食いしてたやつを思い出した。
まだまだ伸びしろがあるということで一旦の締めとする。 結構直してきたので、この初の非同期描画版になった pocof はもういい加減リリースしたいな(何度目)。