C# の高速化・最適化関連

気になった部分の箇条書き。元記事にはもっといろいろと書いてあります。

※ 基本的に数千万回のループを回せば１秒弱早くなるかどうか、そういうレベルの小技（Peanut butters というらしい？）です。

元記事 → iwkjosec/C#高速化.md @ Gist

• 配列・リスト・コレクション
  • コレクションの O(n) 一覧
• スレッド関連
• アトリビュートの挙動
• おまけ

仮想メソッド呼び出しはvftableを２回参照する。遅い

int.ToStringは具象型呼び出し
objectにキャストするとToStringは仮想メソッド呼び出し
値型はボックス化も
インターフェースごしのメソッド呼び出しはインライン展開が効かない

編注： ジェネリック化されてれば気にしなくておっけ。（多分）

• "string" + 10 は遅い。"string" + 10.ToString() だと仮想メソッドが呼ばれないから早い。 いやむしろ遅くね？？ string.Concat() ならその通り（＝引数が object? だから） @ .NET Fiddle
• そもそも違いを実感するほどのイテレーションが難しい。0.2s @ 一千万回ループ
  • → https://dotnetfiddle.net/lmcH6w
• 編注： この手のド定番の最適化は近年の C# だとコンパイラーが良しなにしてくれたりするので、そういう最適化に引っかかるように「定番の書き方」をした方がむしろイイ可能性もある。（上記の結果が振るわなかったのは、その手の最適化から除外された事が原因かも

StringBuilder.GetChunks() てのがある。Unity 2021 では使えない。

• StringBuilder.GetChunks (.NET Core 3.0 から)、いいやん… と思ったのもつかの間だった
  • 編注： .NET Core 3.1 でも狂う → https://dotnetfiddle.net/o0UuMb

if (0 <= integer && integer < 10) は → if ((uint)integer < (uint)10) に出来る

• 右辺が変数の場合は uint にキャストしないと暗黙的に long にキャストされる。（左辺が uint だから）

ref る。（CE って何？）

var a = new int[0];
ref var ra = ref a[0];
foreach (ref var i in a) { } // CE
var l = new List<int>();
ref var rl = ref l[0]; // CE
foreach (ref var i in l) { } // CE
var s = new Span<int>();
ref var rs = ref s[0];
foreach (ref var i in s) { }

• プーリングはオーバーヘッドが増える。特に参照型をメンバーに持つ参照型の場合、長くオブジェクトを保持することになるからGCの世代が上がり、gen(1|2)からgen0ヒープの参照を調べることになる(らしい)

  • 編注： Unity の GC はちょっと古く（？）、ピュア C# と違って世代の概念がない。Incremental な GC（出典は失念

• 空文字列の判定 s == "" より s.Length == 0 のほうが速い

• IndexOf で文字列を検索するときは StringComparison.Ordinal を忘れずにね（編注：カルチャ無効）

• メンバー変数よりローカル変数のほうが速い

  • int などの小さい構造体ならメンバーアクセスよりもメソッドが呼ばれるたびに変数を確保したほうが速い

• sealed class

  • 派生しない型は sealed を付けた方が色々速くなる 現代の視点ではなにも修飾していないデフォルトがそうであるべきだが。
  • 編注： アトリビュートは sealed した方がイイ（セキュリティー＆パフォーマンス）と公式のガイドラインがある。

• Avoiding explicit static ctor's

  • 編注： 静的コンストラクタはやめろ、は常識らしい？？ static ctor じゃなくて field initialize すると良いらしい。
  • BeforeFieldInit ??

配列・リスト・コレクション

なあなあで選んで使ってる配列とリスト。いま改めての公式ドキュメント。

• コレクション クラスの選択

Queue Stack List Dictionary を基本に用途に合わせた色々なバリエーションがある。

そしてスレッドセーフな Concurrent シリーズもいつの間にか存在する。（.NET Standard 1.6 以上）

• ※ メソッド呼び出しの度にロックと解除を行うので、追加・削除が連続するような場合は通常版コレクションを使って一度のロックで済ませた方が良いこともある。

変更不可のコレクション System.Collections.Immutable 💬 もある。（追加インストールが必要）

• ※ IReadOnlyList<T> 等は IList<T> にキャストすれば変更できてしまう。
  • https://qiita.com/yutorisan/items/3f5fdb1495be03e56d3c

注： なぜか HashSet<T> が載ってない。一応 System.Collections.Generic 系列なのになんで？ Hashtable は非推奨なのに載ってるにも関わらず。

• 👉 HashSet<T> 💬 高パフォーマンスのセット操作を提供します。 セットは、重複する要素を含まないコレクションであり、その要素が特定の順序で存在しません。

• HashSet<T>, Dictionary<T1, T2> は追加した順序関係無しでアクセスする用途なら早い。

  • https://qiita.com/ttake/items/518bf36bf165fa9afb59

• 👉 C#(.NET)コレクションの使い分けヒント

非推奨なコレクション

ArrayList 💬 のように一覧に載っているけど非推奨なモノも存在する。

基本的にジェネリックじゃないモノは非推奨っぽい。using System.Collections; を消してエラーが出るなら非推奨の古い API を使ってると思っていい。（ハズ）

いっそ BannedApi で無効にしてしまっても良い。設定作らなきゃだけど今なら ChatGPT がやってくれるか？？

• How to use Microsoft.CodeAnalysis.BannedApiAnalyzers

Unity の C# スクリプトテンプレには System.Collections が入っているが、List<T> が存在しなかった頃の名残だろう。

コレクションの O(n) 一覧

@Zuishin さんのコメントより（ありがとうございます！

SortedList はソート済リストにバイナリサーチを行うものなので挿入、削除、検索の時間計算量が O(N) O(N) O(log N) です。
ただしキーだけではなく先頭からの位置で要素を取得することもでき、その時間計算量は O(1) と高速です。

SortedDictionary はリストではなく二分探索木を使っており、挿入、削除、検索のどれも O(log N) です。
挿入削除が頻繁に行われるなら SortedDictionary の方が速くなりますが、先頭からの位置で取り出すのは列挙して ElementAt を使うことになり、O(N) です。

Dictionary はハッシュテーブルが使われており、挿入、削除、検索が全て O(1) と非常に高速ですが、その分大きなメモリが必要になります。

• HashSet<T>, Dictionary<T1, T2> は追加した順序関係無しでアクセスする用途なら早い。

  • https://qiita.com/ttake/items/518bf36bf165fa9afb59

• コレクションのアルゴリズムの複雑さ　👇 抜粋

変更可能	分散	最悪のケース	変更不可	複雑さ
Stack<T>.Push	O(1)	O(n)	ImmutableStack<T>.Push	O(1)
Queue<T>.Enqueue	O(1)	O(n)	ImmutableQueue<T>.Enqueue	O(1)
List<T>.Add	O(1)	O(n)	ImmutableList<T>.Add	O(log n)
List<T>.Item[Int32]	O(1)	O(1)	ImmutableList<T>.Item[Int32]	O(log n)
List<T>.Enumerator	O(n)	O(n)	ImmutableList<T>.Enumerator	O(n)
HashSet<T>.Add lookup	O(1)	O(n)	ImmutableHashSet<T>.Add	O(log n)
SortedSet<T>.Add	O(log n)	O(n)	ImmutableSortedSet<T>.Add	O(log n)
Dictionary<T>.Add	O(1)	O(n)	ImmutableDictionary<T>.Add	O(log n)
Dictionary<T> lookup	O(1)	O(1) –厳密には O(n)	ImmutableDictionary<T>lookup	O(log n)
SortedDictionary<T>.Add	O(log n)	O(n log n)	ImmutableSortedDictionary<T>.Add	O(log n)

ふわっとした情報

• List.Contains(...) より List.BinarySearch(...) >= 0 のが速い（数万件のリストならね
• でも事前に .Sort() してないとダメ（@albireoさんコメントより）
  • ちなみに Sort() しなくても動く → https://dotnetfiddle.net/NRJMAK

--

• アンサー部分参照 👇

  • C# - Binary search a (sorted) Dictionary

• Dictionary よりも SortedDictionary は遅い。

• List よりも SortedList は速い。（目的による）

  • 同じ Sorted シリーズでも違う
  • 編注： LinkedList っていうシーケンシャルアクセスに特化したバリエーションもある。要素をリストの途中に挿入したりランダムアクセスしたりが List より苦手）
    ※受け売りをそのまま信じてたがちょっと違う → https://ja.wikipedia.org/wiki/%E9%80%A3%E7%B5%90%E3%83%AA%E3%82%B9%E3%83%88

スレッド関連

• スレッド セーフなコレクション

• 粒度の細かいロック機構とロック制御の不要な機構

  • SpinWait
  • SpinLock
  • ReaderWriterLockSlim
  • SemaphoreSlim
  • CountdownEvent

おまけ

.NET Standard - .NET Core と .NET Standard の分かりやすい解説

.NET Standard < .NET Core。

.NET スタンダード（標準＝JISやISO的な）仕様があって、その実装としてコアがある。コアはマルチプラットフォーム対応。.NET Framework は Windows 向け。Xamarin はモバイル＆Mac向け。Linux は .NET Core がカバー。

アトリビュートの挙動確認

アトリビュートを初めて自分の 自分のやつ で作って挙動確認したときのコード。

長いからログインしろって言われて共有リンク作れなかったわ。https://dotnetfiddle.net/

✅ インターフェイスに付けたアトリビュートはクラスに伝播しない。

✅ abstract アトリビュートの AttributeUsage は上書き出来る。

セキュリティー（？というより意図しない挙動）を防ぐためにも、アトリビュートは sealed が良いらしい。abstract を用意して自由にカスタマイズしてお使いください、はやめた方が良いようだ。パフォーマンス的にもよろしくない。

// https://learn.microsoft.com/en-us/dotnet/standard/design-guidelines/attributes
// -> DO name custom attribute classes with the suffix "Attribute."
// -> DO apply the AttributeUsageAttribute to custom attributes.
// -> DO provide settable properties for optional arguments.
// -> DO provide get-only properties for required arguments.
// -> DO provide constructor parameters to initialize properties corresponding to required arguments.
//    Each parameter should have the same name (although with different casing) as the corresponding property.
// -> AVOID providing constructor parameters to initialize properties corresponding to the optional arguments.
// -> AVOID overloading custom attribute constructors.
// -> DO seal custom attribute classes, if possible. This makes the look-up for the attribute faster.

using System;
                    
public class Program
{
    public static void Main()
    {
        var b = new Base().GetType();
        var d = new Derived().GetType();
        var i = d.GetInterface(nameof(IInterface));
        var types = new Type[] {
            typeof(AbstractAttribute),
            typeof(InheritMultipleAttribute),
            typeof(NonInheritMultipleAttribute),
            typeof(InheritUniqueAttribute),
            typeof(NonInheritUniqueAttribute),
        };
        
        bool lookForIneritance = false;  // true to retrieve inheritable attributes

        foreach (var attr in types)
            Console.WriteLine($"[{b.Name}] {b.GetCustomAttributes(attr, lookForIneritance).Length}: {attr.Name}");
        Console.WriteLine();

        foreach (var attr in types)
            Console.WriteLine($"[{d.Name}] {d.GetCustomAttributes(attr, lookForIneritance).Length}: {attr.Name}");
        Console.WriteLine();
        
        foreach (var attr in types)
            Console.WriteLine($"[{i.Name}] {i.GetCustomAttributes(attr, lookForIneritance).Length}: {attr.Name}");
        Console.WriteLine();
    }


    public class Derived : Base { }
    
    [InheritMultiple]
    [InheritMultiple]
    [InheritUnique]
    //[InheritUnique]
    [NonInheritMultiple]
    [NonInheritMultiple]
    [NonInheritUnique]
    //[NonInheritUnique]
    public class Base : IInterface {
        //[InheritMultiple]
        //[InheritUnique]
        //[NonInheritMultiple]
        //[NonInheritUnique]
        public void DoIt() {}
    }
    
    [InheritMultiple]
    [InheritMultiple]
    [InheritUnique]
    //[InheritUnique]
    [NonInheritMultiple]
    [NonInheritMultiple]
    [NonInheritUnique]
    //[NonInheritUnique]
    public interface IInterface {
        void DoIt();
    }

    [AttributeUsage(AttributeTargets.All, AllowMultiple = false, Inherited = false)]
    abstract public class AbstractAttribute : Attribute {}

    [AttributeUsage(AttributeTargets.Class | AttributeTargets.Interface, AllowMultiple = true, Inherited = true)]
    public sealed class InheritMultipleAttribute : AbstractAttribute {}
    [AttributeUsage(AttributeTargets.Class | AttributeTargets.Interface, AllowMultiple = true, Inherited = false)]
    public sealed class NonInheritMultipleAttribute : AbstractAttribute {}
    
    [AttributeUsage(AttributeTargets.Class | AttributeTargets.Interface, AllowMultiple = false, Inherited = true)]
    public sealed class InheritUniqueAttribute : AbstractAttribute {}
    [AttributeUsage(AttributeTargets.Class | AttributeTargets.Interface, AllowMultiple = false, Inherited = false)]
    public sealed class NonInheritUniqueAttribute : AbstractAttribute {}
    
}

--

AI 全盛のこの時代に謎翻訳をキメる MS の公式ドキュメント。Bing で AI やってんのにね。

以上です。お疲れ様でした。