おことわり
この記事はZennに書いていたシリーズを移したもので、初出は2023年11月11日である。
目次
今回の標的
クソコード仕置き人というからには標的はクソコードである。今回のクソコードは下記の記事より。
クソコード生産者表示
クソコード仕置き人というからには標的はあくまでクソコードであるのだが、その量産業者がいるとすれば当然そちらも警戒せねばなるまい。
今回の生産者は内藤時浩…8～16ビットCPUの昔からPCゲームを嗜まれていた方は「えっ、あの？」と思われるかもしれない。中年プログラマの私は大層驚いた。御存じでない方向けのちょうどいい人物情報リンクが思いつかないので雑に説明すると、その昔に魅力的なPCゲームを多数開発された方だ。レトロゲーム名作などの文脈で「ハイドライド」シリーズなどを目にすることも多いのではないか。
クソコード概要
List<Point> canvasPointsに100万要素ほどの点が入っている。このリストから取り除きたい点の情報がList<Point> removePointsに入っているとき、
canvasPoints.RemoveAll(p => removePoints.Contains(p));
としてせいぜい数百オーダーの削除を実行したところ、8秒以上もかかった！遅い！俺が削除ロジックを考えて使ったら20倍速になりました！参考にしていいぞ！ということのようである。
瞬時に「そりゃ遅くて当たり前やん」と思われた方には、続きが全く必要ない。以下には本当に当たり前の解説と検証しかない。
お仕置き
List<T>.Contains()はO(n)操作である。長いループの中から呼び出すのはパフォーマンス上不利なので、高速な検索ができる手段に置き換えるべき。基本的には標準ライブラリのHashSet<T>.Contains()で十分だろう。このメソッドはO(1)操作である*1。
canvasPoints.RemoveAll(removePoints.ToHashSet().Contains);
時代劇風タイトルにしたつもりなのに、いきなり悪役が斬られて断末魔のシーンでええんかいなという気はするが、技術記事なら最初に結論がいるよね…
裏取り
裏取りに使ったコードはこちら
100万要素入ったList<Point>からランダムに100要素抜粋して削除対象リストを作り、下記4種の実装それぞれで削除に要する時間をBenchmarkDotNetで調べた。
BenchmarkDotNet v0.13.10, Windows 10 (10.0.19045.3570/22H2/2022Update) AMD Ryzen 5 5600, 1 CPU, 12 logical and 6 physical cores .NET SDK 7.0.403 [Host] : .NET 6.0.24 (6.0.2423.51814), X64 RyuJIT AVX2 Job-NNHEGN : .NET 6.0.24 (6.0.2423.51814), X64 RyuJIT AVX2 InvocationCount=8 UnrollFactor=1
| Method | Mean | Error | StdDev | Gen0 | Gen1 | Gen2 | Allocated |
|---|---|---|---|---|---|---|---|
| Kuso | 78.60 ms | 0.783 ms | 0.733 ms | - | - | - | 150 B |
| BetterKuso | 197.19 ms | 1.196 ms | 1.119 ms | - | - | - | 8003518 B |
| Normal | 18.72 ms | 0.123 ms | 0.115 ms | - | - | - | 2440 B |
| Except | 74.73 ms | 0.639 ms | 0.597 ms | 500.0000 | 500.0000 | 500.0000 | 81444279 B |
- Kuso
生産者が8秒もかかるとしていて、私の手元でも1800msかかった実装*2…のはずだったのだが、下の長い折り畳みの経緯で何故か80msほどになって元の遅さが再現できなくなってしまった。申し訳ないが、ある環境で1800ms程度かかるはずの実装ということでこれを基準にさせていただきたい。
Kusoが謎の高速化
この記事を書き始める前に、「8秒もかかるならBenchmarkDotNetは不適切だな」と考えてStopWatchを使った検証にするつもりであった。実際に、それで最初に計測したKusoは1800ms程度かかっていた。生産者の記事で8秒もかかったのはPointがSystem.Drawingじゃない方（小数のやつ）だったり、削除対象の「せいぜい数百」が500件程度だったりしたのかもしれないなと考えつつ、秒単位かかるのは事実だと確認して寝た。起きてからKuso以外共々改めて計測しよう…とコードを編集して実行したら何故かKusoが80ms程度まで速くなってしまった。これならBenchmarkDotNetにやらせるかとなった次第である。
しかしKusoが異様に速くなった理由は本当に分からないので、変な話だが1800ms程度に遅くする方法にお心当たりのある方はお知らせいただきたい。寝て起きるまでの間にコンパイラもランタイムも変えていないはずだし、List.RemoveAll()のソース を見ても「引数Predicate<T>が効率悪い！何とかせねば！」とはなっていないし、JITが「最近こいつやたらとList<T>.Contains()呼ぶから暗黙の.ToHashSet()したれ」なんて気を回すとも思えないし…謎だ。 - BetterKuso
生産者が「RemoveAllより高速」としていた独自実装。（上記Kusoの謎の高速化を見なかったことにすれば）10倍弱の速度が出たということになるか。当然こんなコードを書いてはいけない。 - Normal
「お仕置き」のところで挙げた、基本に従ったまともな実装。要素100件からのContainsをO(n)からO(1)にしたので、（謎の高速化がないときの）Kusoの100倍程度の速度になるというのも納得しやすい。倍率でなく絶対的な値についても、UIで「この100個の点消して」と指示して20ms程度で終わればまず気にならないだろう。 - Except
canvasPoints = canvasPoints.Except(removePoints).ToList();
「ある集合から、別の集合を除くのなら結局差集合なのでは？」という至極もっともな実装。Normalよりもこちらを先に思いつくことがあっても自然だろう。LINQで求めた結果のリスト全体を作り直すため、今回のように100万要素もある場合は主にメモリについて圧倒的に不利だが、遅いというわけではない。ゆうしゃの持ち物リスト最大8個から、まおうが指定する禁止アイテム10選の内容に従って没収する程度ならこの記述でも全く問題ないだろう。もっとも、集合としての演算なので重複する要素があった場合は一要素にまとめられてしまうことには注意が必要だ。
戒め
.NET標準ライブラリが遅いのではない。貴方の書いたコードが遅いのだ。
勿論、ライブラリ中に極めて鈍足なコードを見つけたり、画期的な改善法を思いつくことがあれば折角のオープンソースなのだからissueでもpull requestでも挙げればよい。しかし、すでにそうやって毎日世界中の優れたエンジニアがツッコミを入れているライブラリなのであって、それよりも独自実装がずばぬけたパフォーマンスをたたき出すことはそうそうないと自覚すべきだ。いずれ標準よりも高速なライブラリやフレームワークを次々と発表するエンジニアになれれば話は別だが*3、まずは先人や公式ドキュメントが説いてくれている当たり前のことを当たり前にできるようにするべきだろう。常識に捉われるな！と叫んで非常識に陥るようではいけない。
次回予告？
最近たまたま素晴らしい題でひどいことを書いているサイトを相次いで見つけてもうて。そのうちの一つが下記のサイト。
沢山書き並べているけど、そのうち有用と言えるのは
string.StartsWithメソッド、string.EndsWithメソッドのパフォーマンスが、適切な引数で200倍になる
の1個のみである。後は全部嘘か、対処が不適切だ。
ただ、自分でお仕置きすることにこだわってはいないので、「この程度すぐ退治したるわ」という方がやっといてくれると私も嬉しい。
まだ嘆いている
にしても、あの内藤時浩がなあ…
…が、このメソッド、めちゃくちゃ遅いのです。canvasPoints が凡そ 100万ポイントあるとして、removePoints がせいぜい数百というオーダーであっても、これを実行すると
平均: 8,536ms
…遅い、遅すぎる。内部でいちいちリストを詰めている様が目に見えるようだ。こんなことせず、インデックスで処理して最後にまとめてえいやっとコピーしてくれれば十分普通に速いだろうに、なにやってくれちゃってるんでしょうか。
仕方が無いので、RemoveAll より高速に動作する removePoints に該当する処理を作ってみる事にしました。
本当になにやってくれちゃってるんだか。
