クソコード仕置き人両兵衛

物騒に見えても単に基本的な技術情報への誘導です

第3回 【C#】ループで文字連結といえばStringBuilder?⇒まず大量の連結自体を見直せ

C# 高速化 ベンチマーク StringBuilder クソコード

おことわり

この記事はZennに書いていたシリーズを移したもので、初出は2023年11月25日である。

目次

今回の標的

クソコード仕置き人というからには標的はクソコードである。今回のクソコードは前回に引き続き下記の記事より。他でもよく見る大量の文字列連結を取り上げる。

クソコード生産者表示

クソコード仕置き人というからには標的はあくまでクソコードであるのだが、その量産業者がいるとすれば当然そちらも警戒せねばなるまい。
今回の生産者も堺康行…前回はClosedXML関連の検索で上位にくると書いたが、さらに「C# 高速化」でもかなりの上位に来ることが分かった*1。検索結果の順位が必ずしも情報の質の順でないことはいうまでもないが、それにしてもここまで目につく位置にあっては有害である。

クソコード概要

生産者が「測定に使用したコード」を引用する。「あ」が10万個連続した文字列を得るならStringBuilderを使おうと言いたいらしい。

using System.Diagnostics;  
using System.Text;  
  
//StringBuilderで文字列結合  
var stopwatch = new Stopwatch();  
stopwatch.Start();  
var sb = new StringBuilder();  
for (int i = 0; i < 100000; i++) {  
    sb.Append("あ");  
}  
stopwatch.Stop();  
Console.WriteLine(stopwatch.ElapsedMilliseconds);  
  
//stringで文字列結合  
stopwatch = new Stopwatch();  
stopwatch.Start();  
var s = "";  
for (int i = 0; i < 100000; i++) {  
    s += "あ";  
}  
stopwatch.Stop();  
Console.WriteLine(stopwatch.ElapsedMilliseconds);

お仕置き

問題だらけなので箇条書きにしよう。

  1. 大量文字連結の必要性
    本件に限らず、BenchmarkDotNetの使い方紹介記事などでも速度改善コード例としてよく出てくるのだが、実際に1文字（もしくは短い文字列）を大量に自力で連結しなければならない機会は稀である。万単位の連続した文字を文字列化するとなるとテキストファイルやネットワークからの読み込みが想定されるが、StreamReader.ReadLineAsync()で行ごとに処理、もしくはメモリが許すならStreamReader.ReadToEndAsync()で一気に読み込みなどを先に検討すべきである。他にも文字列補間など幅広く言語仕様やライブラリからの支援が受けられるので、大量の文字を自力で連結しそうになった時点で必要性を疑った方が良い。
    以下、ダミーデータ作成などの要件でどうしても「あ」10万文字が必要になったものとして続ける*2。

  2. StringBuilderを文字列化せずに計測している
    クソコードはStringBuilderに10万文字連結して終わって数十倍高速と誇っているが、StringBuilderのまま文字列情報として使うことはほぼない。最後にstringに変換するところまで含めて「『あ』10万文字からなる文字列を作るのにかかる時間」とすべきである。

  3. 1文字は極力charで表現すべき
    クソコードは1文字を表すのに"あ"とstring型を使っているが、'あ'としてchar型で処理した方が効率がいいことが多い。このことはCA1834などで表示されるので、生産者は日常的にコード分析結果を無視しているのではないかという疑念も生じる。

  4. そもそもstringのコンストラクタで一行で済む
    stringの引数付きコンストラクタには文字と個数を受け取るものや、char[]を受け取るものなどがある。これらで簡潔に記述すれば不具合も混入しにくい。

裏取り

裏取りに使ったコードはこちら
今回もBenchmarkDotNetで計測しているが、.NET6と.NET8で明確に結果の異なる箇所があったので両方掲載した。もっとも「いちいちStringBuilderのインスタンスを作るまでもない」という結論は変わらない。

BenchmarkDotNet v0.13.10, Windows 10 (10.0.19045.4170/22H2/2022Update)
AMD Ryzen 5 5600, 1 CPU, 12 logical and 6 physical cores
.NET SDK 8.0.202
  [Host]   : .NET 8.0.3 (8.0.324.11423), X64 RyuJIT AVX2
  .NET 6.0 : .NET 6.0.28 (6.0.2824.12007), X64 RyuJIT AVX2
  .NET 8.0 : .NET 8.0.3 (8.0.324.11423), X64 RyuJIT AVX2
Method Runtime Mean Error StdDev Gen0 Gen1 Gen2 Allocated
KusoBuilder .NET 8.0 159.24 μs 1.457 μs 1.292 μs 62.2559 62.2559 62.2559 400.4 KB
BetterKusoBuilder .NET 8.0 167.88 μs 0.419 μs 0.350 μs 62.2559 62.2559 62.2559 400.4 KB
Normal .NET 8.0 61.08 μs 0.423 μs 0.396 μs 62.3779 62.3779 62.3779 195.36 KB
Linq .NET 8.0 122.45 μs 0.170 μs 0.142 μs 124.8779 124.8779 124.8779 390.74 KB
Create .NET 8.0 60.83 μs 0.316 μs 0.280 μs 62.3779 62.3779 62.3779 195.36 KB
KusoBuilder .NET 6.0 334.48 μs 2.628 μs 2.458 μs 62.0117 62.0117 62.0117 400.4 KB
BetterKusoBuilder .NET 6.0 176.57 μs 1.030 μs 0.913 μs 62.2559 62.2559 62.2559 400.4 KB
Normal .NET 6.0 59.89 μs 0.206 μs 0.172 μs 62.4390 62.4390 62.4390 195.36 KB
Linq .NET 6.0 123.47 μs 1.169 μs 1.093 μs 124.7559 124.7559 124.7559 390.74 KB
Create .NET 6.0 60.08 μs 0.081 μs 0.072 μs 62.4390 62.4390 62.4390 195.36 KB

以下、それぞれのアルゴリズムの引用コード中でCharacterCountは連結する文字の数を表す。すなわち、今回は10万である。
1. KusoBuilder

public string KusoBuilder()  
{  
    var sb = new StringBuilder();  
    for (var i = 0; i < CharacterCount; i++)  
    {  
        // ここでCA1834  
        sb.Append("あ");  
    }  
    return sb.ToString();  
}

StringBuilderに10万回Append()する生産者案。純然たるクソコードである。

2. BetterKusoBuilder

public string BetterKusoBuilder()  
{  
    var sb = new StringBuilder();  
    for (var i = 0; i < CharacterCount; i++)  
    {  
        sb.Append('あ');  
    }  
    return sb.ToString();  
}

「お仕置き」を踏まえ、Append()の引数にchar型を渡すよう改善したもの。.NET6では前出KusoBuilderの倍速ほどになるのだが、あまりにもクソコードが量産されて最適化対象になったのか、.NET8ではわずかながら逆転している*3。いずれにしてもクソコードの背比べではある。

3. Normal

public string Normal() => new('あ', CharacterCount);

意図も明確だし、これで十分だろう。内部では結局StringBuilderを使って作っているのでは、と予想していると前出のBetterKusoBuilderの3倍弱速いことが意外かもしれない。.NETのソースを見るとVector<T>などを駆使して高速化を図っているのが分かる。これより有意に高速に実装できる自信がある場合のみ自力でやれば良い。

4. Linq

public string Linq() => new(Enumerable.Repeat('あ', CharacterCount).ToArray());

Normalを見て「違うの！本当は動的に異なる文字も連ねていくの！！」と言い出した場合*4を考慮して、何らかのIEnumerable<char>から作るとどれくらいのオーダーになるかの参考測定。一旦ToArray()が入ってしまうためGCを促してしまうが、それ込みでもKusoBuilder兄弟より確実に速い。可読性も考えて通常はStringBuilderよりも優先していいだろう。

5. （移転時追記）Create

public string Create() => string.Create(CharacterCount, 'あ', (span, c) => span.Fill(c));

初出において、現代C#で事前に長さが分かっている文字列の生成と言えば当然出してくるべきstring.Create()が欠けていたので、移転のついでに計測コードと結果に追加した。3.Normalと同等と言えるパフォーマンスが確保できている。Span<T>.Fill()も最終的にはVector<T>を利用した最適化に行きつくのだろう。今回のように、同一文字を連結するだけならこちらの記述を選ぶ意味は特にない。しかし、生成する内容によっては第3引数によって柔軟にSpan<char>を操作できる利点が生きることもあるだろうから選択肢として押さえておきたい。

戒め

.NET標準ライブラリが遅いのではない。貴方の書いたコードが遅いのだ。
濫造された「ループで文字を結合するときはStringBuilderを使えばn倍速」説を鵜呑みにしたのか、ループ回数に関わらずやたらとStringBuilderのインスタンスを作るコードをよく目にする。例えばstring[] errorItemNamesにユーザーからの入力エラーのあった項目名（多くても数十）が入っているとして、「カンマ区切りで表示してくれ」という要件に対し下記のようなコードが書かれがちである。

var sb = new StringBuilder();  
foreach (var errorItemName in errorItemNames)  
{  
    if (sb.Length > 0)  
    {  
        sb.Append(',');  
    }  
    sb.Append(errorItemName);  
}  
// sb.ToString()を画面に表示

開発現場で一度は上記のようなクソコード*5を目にしたことはないだろうか。あるいは、要件が「区切りのカンマは不要になった。そのまま続けて表示してくれ。」と変わった途端に上記に似たクソコードに逆戻りしてしまう例も多々ある。現代では、StringBuilderに限らず、forやforeachを回して内部で何かを加え続けること自体がアンチパターンだと認識すべきだろう。そのうえで、当初Javaにならって用意されたと思われるStringBuilderは、近年のC#や.NETの進化によりレガシーに寄りつつあると把握しておくべきである。

*1:2023年11月25日時点でGoogle2位

*2:このひねり出した例もテキストエディタのマクロやPowerShellで十分そうなので、やはり必要となる状況は想像しがたい。

*3:charの方が遅いのも妙なので、今後さらに最適化されて再逆転するかもしれない。

*4:前回も書いたが、仮にそうだとしたら最初からそうとわかる例を提示すべきである。

*5:皮肉なことに、Visual Studio 2022でこれを入力しているとIntelliCodeによって次々と予測されていく。かなり普遍的なクソコードなのだろう。

第2回 【C#】LINQのWhere()で絞った後First()呼ぶとき、ToList()を挟んだ方がいい？⇒断じて否

C# 高速化 LINQ ベンチマーク クソコード

おことわり

この記事はZennに書いていたシリーズを移したもので、初出は2023年11月19日である。

目次

今回の標的

クソコード仕置き人というからには標的はクソコードである。今回のクソコードは下記の記事より。
素晴らしい題とは裏腹に、令和4年に公開され令和5年に更新されているとは信じがたい嘘や不適切な処置が多数並んでいる。何度かに分けて丁寧にお仕置きしていこう。

クソコード生産者表示

クソコード仕置き人というからには標的はあくまでクソコードであるのだが、その量産業者がいるとすれば当然そちらも警戒せねばなるまい。
今回の生産者は堺康行…ClosedXML関連の情報を探していると度々検索上位に来る印象だ。個人企業の代表者らしい。私は純開発者なので、経理事務営業設計実装と一人でこなされていることは敬服するが、記事を読む限り少なくとも実装はなるべく早く誰かに任せるべきだろう。実際にプログラマを募集されているようだが、レビューと称してクソコードを強要される可能性から優れた技術者ほど応募を躊躇しそうではある。

クソコード概要

まずは生産者の記事から引用しよう。

次のコードのように、Whereで絞込した後にFirstメソッドで取り出すといった処理を行う場合、事前に即時評価を行った方が高速になります。
ケース①ではFirst実行時にWhereが未評価のため全件検査になる一方、ケース②では絞り込みが評価された後ですので、検索範囲が絞られた効果を得ることが出来ます。

//事前準備。list変数は要素数1万のList<TestClass>クラスインスタンス  
//各要素のProp1にインデックスと同じ自然数を格納。（兼ウォーミングアップ）  
var list = new System.Collections.Generic.List<TestClass>();  
for (int i = 0; i < 10000; i++) {  
   list.Add(new TestClass() { Prop1 = i });  
}  

//テストケース①即時評価せずFirstで取り出し  
var narrowedEnumerable = list.Where(x => x.Prop1 > 4000);  
var result = narrowedEnumerable.First(x => x.Prop1 == 4345);  

//テストケース②即時評価してからFirstで取り出し  
var narrowedList = list.Where(x => x.Prop1 > 4000).ToList();  
var result = narrowedList.First(x => x.Prop1 == 4345);

瞬時に「そんなはずねえけどなあ」と思われた方には、続きが全く必要ない。以下には本当に当たり前の解説と検証しかない。しかし初心者がやたらとToArray()やToList()をしたがって困っている開発現場も多かろうから、しっかりお仕置きしておく。

お仕置き

早いものでLINQも生まれて15年以上になるが、基本はずっと変わっていない。下記にしたがえば間違えない。

  • 可能な限りIEnumerable<T>のまま取り回せ
  • 2回以上結果を列挙する *1 場合、もしくは特定の時点での結果が必要な場合のみToArray()やToList()などで確定させろ

したがって先ほど引用したコードにおいて採用すべきは「テストケース①」である。後に私からの説明も置いてはおくが、優れた記事はすでに多くあるので、それらから基本をしっかり把握すればまず問題ない。今回は次に挙げる記事を推薦する。
2021年の記事だが、この頃から急に遅延評価優先が流行するはずもなく、この記事もさらに3年半前に書かれた内容を刷新したものとある。いずれにしても、必要以上にToArray()やToList()したがるなということである。

「2回以上結果を列挙」ってなんや？の補足。推薦した記事で理解できれば読む必要はない。 「2回以上結果を列挙する場合は」とはいうが、そもそも何をしたら「1回結果を列挙した」と数えるのか？それは、あるIEnumerable<T>に対して下記のような操作をすればいずれも「1回」分になると押さえておくとよい。

  • foreachで要素を取り出し始める（仮に全要素を取り出さずに抜けたとしても）
  • 集計系のメソッドを呼び出す…Sum(), Count(), Average(), ...など
  • 探索系のメソッドを呼び出す…First(), ElementAt(), Any(), All(), ...など

上記に含まれないSelect(), Where(), Take(), Skip(), Distinct() *2などの呼び出しは「遅延評価」の性質を持つ。すなわち、呼び出しても即座に結果は列挙しないので「1回」分に数えない。必要になるまで結果の計算を遅らせることで、後から「有無だけ分かれば良かったわ」などと言われた場合に楽ができるよう構えているのである。あるメソッドが遅延評価なのか迷った場合はEnumerableクラスのリファレンス*3の該当するメソッドの説明を見に行くといいだろう。「注釈」欄にこのメソッドは、遅延実行を使用して実装されます。*4とあれば遅延評価である。

裏取り

今回はクソコードがベンチマークなので計測法自体にも触れておく。素人がウォーミングアップ云々と計測法を気遣ったつもりでも限界がある。.NETのマイクロベンチマークでは事実上公式レギュレーションと言えるBenchmarkDotNetを用いるべきだ*5。仮にレギュレーション自体に問題があることが分かっても、オープンソースたるBenchmarkDotNetの修正を待って同一コードで再度計測することは容易である。これこそまさに関心の分離といえよう。
今回のクソコードについては、何故First()一発で書ききらずにWhere()を先に挟んでいるのかとも思ったが、「Prop1が4000を超えることは業務共通の条件であるのに対し、その中から4345の要素を探すことは機能固有の要件なので分けて実行するのだ」とでも脳内補完することにした。TestClassの詳細も分からないので、とりあえずint型プロパティを増やしておいた。そうしてできた裏取り用コードと、その測定結果が下記である。
裏取り用コード

BenchmarkDotNet v0.13.10, Windows 10 (10.0.19045.3693/22H2/2022Update)  
AMD Ryzen 5 5600, 1 CPU, 12 logical and 6 physical cores  
.NET SDK 8.0.100  
  [Host]     : .NET 8.0.0 (8.0.23.53103), X64 RyuJIT AVX2  
  DefaultJob : .NET 8.0.0 (8.0.23.53103), X64 RyuJIT AVX2
Method Mean Error StdDev Gen0 Gen1 Allocated
ToListCultist 27.58 μs 0.552 μs 0.590 μs 7.8430 1.9531 131472 B
Normal 10.74 μs 0.200 μs 0.385 μs - - 72 B

ToListCultistが生産者の推奨する「即時評価してからFirstで取り出し」である。何の利点もないことがよく分かるだろう。実行時間が3倍弱ということに目が行きがちだが、1万件からの探索に対して10μs単位の差なのでここがボトルネックとして表面化する機会はあまりなさそうだ。それよりも注目したいのはAllocatedである。メモリを大幅に無駄遣いしていることが見て取れる。Gen0, Gen1が示すとおり不要なGCも促してしまっている。

戒め

LINQが遅いのではない。貴方の書いたコードが遅いのだ。
前回のHashSet<T>のように、メモリを確保してパフォーマンス向上を図ることはあるが、メモリを浪費した挙句パフォーマンスを落とすいうのはクソコードそのものである。
再び生産者の記事から引用しよう。

（参考）ToList()の処理自体にはさほどの処理速度不可はかからない
次のようなコードで比較してみたところ、処理速度では大きな差は見られませんでした。（尚、メモリ効率の面では①の方が優れていると推測されます）

// 引用者注：listの初期化部分は前掲と同じなので割愛する  
//テストケース①　評価は1回だけ  
var narrowedEnumerable1 = list.Where(x => x.Prop1 < 5000);  
var narrowedEnumerable2 = narrowedEnumerable1.Where(x => x.Prop1 < 2000);  
var narrowedEnumerable3 = narrowedEnumerable2.Where(x => x.Prop1 < 1000);  
var result = narrowedEnumerable3.ToList();  

//テストケース②　Whereするごとに評価する  
var narrowedList1 = list.Where(x => x.Prop1 < 5000).ToList();  
var narrowedList2 = narrowedList1.Where(x => x.Prop1 < 2000).ToList();  
var narrowedList3 = narrowedList2.Where(x => x.Prop1 < 1000).ToList();

「不可」は「負荷」のことだとして、計測法が不適切なうえに認識が甘すぎる。GCは全スレッド中断のうえで実行される重たい処理として有名で、それをメモリ浪費によって促してしまうのは避けるべきだ。万事がゼロアロケーションであるべきとは思わないが、資源は大切に使おう。

豪華特別付録　Count()ならどうなる！？

ほぼ同じ内容で回を分けるのもなんなので付録で済ませる。生産者の記事にはToList()してからCount()しよう（ToList()後は当然Countプロパティだが）という主張もある。そのコードを引用する。

//テストケース①　事前にToListせすCountメソッドを利用  
var narrowedEnumerable = list.Where(x => x.Prop1 > 4000);  
if (narrowedEnumerable.Count() > 0) {  
    foreach (var item in narrowedEnumerable) {  
        var a = item.Prop1;  
    }  
}  
  
//テストケース②　事前にToList  
var narrowedList = list.Where(x => x.Prop1 > 4000).ToList();  
if (narrowedList.Count > 0) {  
    foreach (var item in narrowedList) {  
        var a = item.Prop1;  
    }  
}

テストケース①を見ると、Count()の呼び出しとforeachによる取り出しで「2回結果を列挙している」例なので結果を確定させてから操作すべきである…それ自体は間違いではないが、Where()の条件に該当する要素が皆無の場合はforeachを素通りしてくれるのでifによる要素数の判断がそもそも不要である。するとCount()も不要で、それに伴いやはりToList()も不要になってしまう。
「違うの！結果がないときは『ない』という特別メッセージを表示するの！！」とでも言うつもりなのかも知れないが、それなら最初からそうと分かる例を提示しないと無益だ。ループの中でローカル変数に各要素を上書きし続けるだけ（書いた値を利用しない）という処理も最適化で消されてしまいかねないので、ベンチマークには適さない。正しく計測できないと正しく高速化もできないだろう。

*1:クエリ内容が簡素で結果の要素も少ない場合、「IEnumerable＜T＞のまま2回連続でforeachさせても、ToArray()させたものよりわずかに速かった」という逆転もありえる。しかし、このわずかな差がボトルネックになることは稀だろう。

*2:個人的にDistinctが遅延評価は意外だった

*3:左の見出しで「列挙」と中途半端に自動翻訳されているのは勘弁してほしい

*4:「遅延評価」表記の方をよく見る気がするが、公称が「遅延実行」なのか、自動翻訳の妙なのかは分からない。

*5:ちょうど先日リリースされたVisual Studio 2022 17.8では新機能としてプロファイラとBenchmarkDotNetの連携が強化されており、今後も公式化が進むとみられる。

第1回 【C#】List<T>.RemoveAll()は使い物にならないほど遅い？⇒遅くなる記述を選んだだけです

C# 高速化 ベンチマーク List<T> クソコード

おことわり

この記事は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
  1. 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()したれ」なんて気を回すとも思えないし…謎だ。
  2. BetterKuso
    生産者が「RemoveAllより高速」としていた独自実装。（上記Kusoの謎の高速化を見なかったことにすれば）10倍弱の速度が出たということになるか。当然こんなコードを書いてはいけない。
  3. Normal
    「お仕置き」のところで挙げた、基本に従ったまともな実装。要素100件からのContainsをO(n)からO(1)にしたので、（謎の高速化がないときの）Kusoの100倍程度の速度になるというのも納得しやすい。倍率でなく絶対的な値についても、UIで「この100個の点消して」と指示して20ms程度で終わればまず気にならないだろう。
  4. 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 に該当する処理を作ってみる事にしました。

本当になにやってくれちゃってるんだか。

*1:勿論「遅いO(1)もありうる」事実は常に意識しておく必要がある。当然、必ずO(n)のn倍速になるというわけでもない。ただし、今回のように極端に効率が悪いと分かっている場合は「長いループから呼ぶのでO(1)採用」で十分である。

*2:BenchmarkDotNetに乗せる都合上、測定コード上ではアルゴリズムに影響のない範囲で表現を変えている。以下も同様

*3:私がこの文脈で最初に思い浮かべるのは@neueccさん