Skip to content

Instantly share code, notes, and snippets.

@iwkjosec

iwkjosec/C#高速化.md

Last active February 27, 2024 12:09
Show Gist options
  • Save iwkjosec/61669b580739c0405f58987e70470881 to your computer and use it in GitHub Desktop.
Save iwkjosec/61669b580739c0405f58987e70470881 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
C#高速化.md

.NET Blog Performance Improvements で Peanut Butterと呼ばれる類の小手先の定数倍高速化まとめ(羅列) 個人的なメモをpublicにしただけなのであんまり信用しない方が。長文部分はだいたいわかってないで書いてる(数年前の自分･･･)
ランタイムやライブラリの進化で無意味になることがあります。
整えてないので見にくい。

原則

  • コピーを作らない
  • スタック上で完結させる（==アロケーションを避ける）Sapn<T>とstackallocは強い。ただしスタック領域は狭い。
  • 仮想メソッドは遅い
  • ボックス化はもっと遅い (2021-01-11 今見ると書かなくていいレベルの自明な前提･･･まぁいいか)

.NET Blog のパフォーマンス改善の記事達

インライン化とプーリングはその部分だけのベンチが速くなっても全体としては遅くなることもあるぞい

インライン化でメソッド呼び出しコストが消えてもそのメソッドが色々なところから呼ばれる場合コードサイズが増えて悪影響がでる
メソッド呼び出しコストの削減だけが目的ならすべてのメソッドを展開すればいいけどそれで速くなるわけない
インライン化するのは小さなメソッドだけなのは相対的な効果が大きいからとかではなく後続の最適化(定数畳み込み等)が掛かりやすくするため

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

線型データ構造

  • 範囲チェック
    × if (0 <= x && x < length) //C#erを名乗ってはいけない例
    ○ if ((uint)x < (uint)length)
    lengthが変数のとき、キャストしないとintとuintの比較になってlongに暗黙拡大される

    • 関連 : intの変数が正であることが保証されてるからいいかと思ってintとuintの2項演算をするとlongになってるのでキャストして

  • 舐める

    • 配列、Span<T>をforで回すのが最速。配列、Span<T>に対するforeachはコンパイル時にforに化ける
    • List<T>もforで添字アクセス　foreachはMoveNext()のコストがかかる
    • 配列やSpan<T>をforで回すときはLengthを使う。内部的な範囲チェックが消える
      範囲チェック消滅パターン
      範囲チェック消滅パターン
    • 部分アクセスはAsSpanしてLengthで舐めれば最適化がかかる
    • AsSpanするときはMemoryMarshal.GetArrayDataReferenceを使った方がnullチェックとか共変チェックとかなくて速いはず。
      共変チェックとは：.NETの配列は共変（どうして･･･）なのでAsSpanするときにBase[]の中身がDerived[]だと困るから調べる。
    • 配列よりSpan<T>のほうが舐めるのわずかに速いことがある？
    • .NET 5.0からCollectionsMarshal.AsSpan<T>(List<T>)というのがある。Listの内部配列を抜き出せる。

  • スライス
    えーなんで配列と文字列の新インスタンスつくるの。Span<T>で返せよ
    ということでarray.AsSpan()[range] str.AsSpan()[range]
    AsSpanを挟まないコードはね、駄目

  • ref

      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) { }

Span<T>を崇めよ

配列 Span<T>

  • 二次元配列よりジャグ配列の方が速いことがあり、なんでやねん
    例 僕のスパーステーブル

  • new T[0]よりArray.Empty<T>()を使う
    new T[0]は配列のインスタンスが作られるがArray.Empty<T>は既に存在するものを使いまわす。
    Length == 0だから値は必ず同値だが参照の同値性は new T[0] != new T[0] Array.Empty<T>() == Array.Empty<T>() これでハマるようなことは普通ない（値は書き換えようもないし新しいインスタンス代入したら参照が非同値なのはそれはそうなので）けど一応注意

  • C#1.x .Net 1.0　時代のクソAPI(ジェネリックがない、共変配列)
    引数がobject{[]}{?}だったり戻り値がobject{[]}{?}だったりするクソAPI 共変配列、便利？ --いいえ
    RegexとかMatchesCollectionをforeachするとMatchではなくobjectがやってくる。死ね
    object[]に代入するときに本来の型との型チェックがいちいち入るんじゃ･･･
    共変性は参照型にしか働かないため、構造体でラッパをつくってUnsafe.As<object[], Wrap<T>>(ref objarray)をすると速い。
    https://ufcpp.net/blog/2018/12/arraydowncast/
    //これ引数戻り値がobjectでボックス化仮想メソッド呼び出し配列なら共変チェックとかが入ってクソ、ジェネリックを使えという話をわけて共変配列についてだけかきたい

  • ArrayPool<T>
    Coreのみ

以下は無意味になりました
//- Array.Copy(src, dst, length)
//Array.Copy(src, src.GetLowerBound(0), dst, dst.GetLowerBound(0), length)を呼んでいるだけ //Array.Copy(src, 0, dst, 0, length)を使おう

以下はCore 2.1で確認。intの10^5の配列の場合非ジェネリックが75.66 usでジェネリックが91.55 us
Core 3.1と.NeT 5.0ではともに78 us ぐらいだった。内部的にはTrySZ系のネイティブコードが消えている。でもcoreclrのアーカイブには3.1でも残っているように見えるが。
//- Array.Reverse<T>(T[] array)
//CoreにはArray.Reverseのジェネリック版がある。非ジェネリック版はArray型にキャストすれば呼べる。 //非ジェネリック版は従来実装と同じネイティブコード(TrySZReverse)で、ジェネリック版はUnsafeクラスとrefでマネージコードで頑張っている。 //が、ネイティブコードののほうが速いからArray.Reverse((Array)array)を使うとよい //TrySZReverseが成功するのはプリミティブ値型だけらしい？コード見ればわかるがこれに失敗するとArrayReverseが呼ばれて死

  • card table
    何dotnet/coreclr#17891 (comment)
    object[]のような参照型はカードテーブルチェックがかかる･･･？ 分からんhttps://stackoverflow.com/questions/39309806/card-table-and-write-barriers-in-net-gc

  • ReadOnlySpan<byte> data = new (byte)[] {...}
    最適化で無駄な配列確保をしない。
    sbyte、boolでも可。charはエンディアンの関係でダメ。ビッグエンディアン？そんなもん使う方が悪いだろ

  • PinSpanExplicit
    {ReadOnly}Span<T>.GetPinnableReferenceは配列や文字列と挙動をそろえるためnullやemptyに対しnull pointerを返すための分岐があって遅いのでMemoryMarshal.GetReferenceを使うとよい

文字列

.NETの文字列は不変(参照型だけど値型のようにふるまいたい、が、代入などでコピーが発生するとつらいため、こういう仕様に･･･)
だから、新しい文字列を生成することで文字列の変更を擬似的に達成している。添え字アクセスは読み取り専用で書き換えられない
文字列に対して何度も変更するならchar[]を使うとかもあり（char[]をつくるのにコピーが起こるが）
ポインタ化すればコピー無しで自由に書き換えられるが

  • 空文字列の判定 s == "" より s.Length == 0 のほうが速い
    それはそう。でも知るまで気づかんかった

  • IndexOfで文字列を検索するときはStringComparison.Ordinalを忘れずにね

  • 上にも書いてあるがSubStringはOmitされるべきでAsSpanを使う

  • ループで文字列を結合するならStringBuilder
    いちいち新インスタンスつくるよりはましだが本気で高速化するならStringBuilderもアロケーション。stackalloc Span<char>を使うべき

  • 文字列は+で連結すると４つまでならstring.Concatになりはやいが５以上だとparamsで配列ができて遅い
    // おいでよparams Span<T>

  • string + int は operator +(string, object)が呼ばるからゴルフでなければToString()をサボるな
    $"{int}"もToStringを呼ぶべき
    //文字列処理アロケーション多過ぎ問題isuee上がってたな

  • Split遅い？
    https://yukicoder.me/submissions/307211/diff/266474
    (2021-01-11)Frameworkのソース見るとSplit(char)のオーバーロードがなくてSplit(params char[])だわ。
    現代のC#ではありえないパフォーマンスへの無頓着さ。

アロケーション除け（スタック領域、構造体）

  • スタックはヒープより速い
    現状ValueXorshiftがXorshiftより5%速い。Object Stack Allocationが入ったらかわるかな
    計測時のインスタンスはどちらもクラスのメンバーのはずだが･･･
    stackallocとnewはnewのほうがはやい？確保した配列へのアクセスはstackallocのほうが速いはずだが
    要検証https://yukicoder.me/submissions/350632

  • メンバー変数よりローカル変数のほうが速い
    intなどの小さい構造体ならメンバーアクセスよりもメソッドが呼ばれるたびに変数を確保したほうが速い
    Xorshiftのtを毎回メソッド内で宣言しないでメンバー変数にするか、とかよかれと思ってやると遅くなる。 (2021-01-09)今見ると自明。

  • 防衛的コピー
    フィールドの構造体がreadonlyで宣言されているとき構造体のインスタンスメソッドを呼ぶとメソッドによって変数が書き換えられないことを保証するために バックアップコピーが発生する。in引数で受け取った変数も同様。readonlyローカル変数が入ってもそうなるのかな
    readonlyは読み取り専用であって不変の保証ではない。そのスコープで書き換えられないことを保証しているが外部からの書き換えは可能

  • forの外で宣言した変数に再代入するよりforの内部でいちいち宣言したほうが速い？
    普通そんなことはない
    //forやif　メソッドをifで囲むだけで高速化した事例あり（HTTF予選）
    (2019/05/24)これあまりわかってない頃に書いたが、今考えると、高レイヤーでの変数宣言の位置はスコープを縛るだけで、低レイヤーでは関数の先頭で宣言されるから変数宣言の位置はパフォーマンスに影響しないはず。for内でアロケーション起こしてたら元より遅くなるはず

null

  • T?のValueはGetValueOrDefaultのほうが速い
    らしい

  • 型引数Tの最速の参照型判定 typeof(T).IsValueType 普通だ･･･
    以前の最速（汎用性が劣る） if (default(T) == null) （ILではボックス化しているがJIT時定数でif分岐自体が消滅）
    typeof(T).IsValueTypeがJIT時定数になる最適化

  • 最速(sealed型のみ？)共変チェック判定 obj.GetType() != typeof(X) それ以外にどう書くの
    これも上と同じJIT時定数になる最適化。上の方に書いてあるけど。
    obj.GetType() != typeof(X)がJIT時定数になる最適化

  • ==をオーバーロードしていてインライン化ができないとき、nullチェック（0比較）が遅くなる。x is nullとする

脱仮想化

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

sealed class

派生しない型はsealedを付けた方が色々速くなる 現代の視点ではなにも修飾していないデフォルトがそうであるべきだが。

その他

  • conv.iを避ける Avoid conv.i opcodes in hot paths in CoreLib #51190
    正であることが分かっているintをulongに変換するときは符号拡張よりゼロ拡張の方が速いのでは？という話。
    movsxdがmovになるから
    余談：以下の罠。たまに踏む。ゼロ拡張されると思うじゃん？
int n = -1;
Console.WriteLine((ulong)n);//符号拡張される･･･
var div = a / b;
var rem = a % b;

みたいなとき

var div = a / b;
var rem = a - b * div;

の方が速いという話。

ulongのa % mよりa - a / m * mの方が速いんだけど･･･なんで･･･

  • デリゲートは遅い
    クラスを生成するので。
    [雑記] 匿名関数のコンパイル結果 - C# によるプログラミング入門 | ++C++; // 未確認飛行 C
    ここでは書かれていない例としてデリゲートで再帰をする場合//TSortをSharpLabに投げるとわかる
    キャプチャした変数がフィールドになり、デリゲートで渡したラムダ式と同じロジックのメンバーメソッドができる。そのメソッドをデリゲートに代入したものをフィールドに持ち、それが呼ばれる。
    見るからにやばそう。いやなんでこんなことに･･･。マルチキャストデリゲートとかがあるから単なる関数ポインタより無駄が多い。 「unsophisticated peopleに媚びた設計」だっけ？昔のC#、パフォーマンスに無頓着で、見た目が簡単になるなら内部が複雑になってもいいやという感じでむだに高度に抽象化されたライブラリが多いな。.Netの標準ライブラリの実装を見ると内部で何重にもインターナルなメソッドの呼び出しがあったりしてね･･･。しかも引数、戻り値がobject{[]}だったり
    上でも書いたけどジェネリックがある今ならConsole.WriteLine<T>(T v) => v.ToString() + Environment.NewLine;でいいわけで･･･
    今はそんなことないけど。いや化石ライブラリOmitしてくれ

ローカル関数は構造体を生成して、デリゲート自体はstaticメソッドになる。みたところオーバーヘッドは最小限になっていそう
ローカル関数なら変数キャプチャも気にするほどではなさそう。

ところで関数ポインタはC#X.0ではいる予定

  • カリー化デリゲート
    お任せ→[雑記] デリゲートの内部 - C# によるプログラミング入門 | ++C++; // 未確認飛行 C

  • x => f(x)でキャッシュされてfより速い場合あり

  • condよりcond ? true : falseのほうがJIT最適化が効きやすいらしい
    ウケるな
    例外もdotnet/runtime#8363

  • + 0はコンパイル時に消滅するけど^ 0や| 0はJIT時でも残っている（は？）

  • Enum.HasFlags
    Core以外ではダメ

  • 分解代入によるスワップ
    最適化が甘すぎる
    要素が3以上になったり
    参照をはさんだりするともうだめ

  • Avoiding explicit static cctors
    なに

  • static とインスタンスはどっちが速い？AtCoderにC#7.0が入った場合メンバー関数とローカル関数はどっちが速い？
    (2019/07)昔の自分に回答するか･･･
    上記の理由でインスタンスメソッドのほうが速い場合がある。まぁ基本は変わらない。フィールドの読み書き速度は知らない。
    ローカル関数はstaticメソッドに展開される

  • 演算子のオーバーロードは遅い？んなことはないはずだがどっかのブログで見た
    そいつがダメコード書いてただけかもしれん

  • 手動インライン化で遅くなる例あり（XorshiftのNext()とNext(int)やNext(int)とNextDouble()をまとめると遅くなる）
    手動インライン化で自動インライン化が阻害されているのでは

  • AutoFlush

Console.SetOut(new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
//-------
//出力処理
//-------
Console.Out.Flush();

AutoFlushの有無、10^5 回の出力では500 ms以上の差
https://atcoder.jp/contests/atc001/submissions/3889552
https://atcoder.jp/contests/atc001/submissions/3889582

-構造体の`Equals`そんなに速くない
単純な`memcmp`ではないっぽい

-`new` 制約は遅い
`Activator.CreateInstance<T>()`(リフレクション)が呼ばれるので

Unsafe

pointer
Unsafe class
ref
hardware intrinsics

@iwkjosec
Copy link
Author

IndexOfはカルチャ見るから遅い

@iwkjosec
Copy link
Author

まるごと書き直したいなぁ･･･

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment