ネコのために鐘は鳴る

寺院に住み着くパソコ〇好き

(C#) ArrayPool<T>.Shared 解体新書

ArrayPool<T>.Shared

みなさんはSystem.Buffers.ArrayPool<T>.Shared使ってますか?使ってない?なら使いましょう。 ArrayPool<T>.Sharedは短期間だけ利用するようなバッファを貸してくれるものです。 new T[N]と違い、一度使った配列を使いまわすことができるのでガベージにならず、メモリ効率がよいです。

// Length = 20 以上のバッファを取得
byte[] array = ArrayPool<byte>.Shared.Rent(20);

// 借りたバッファを返す
ArrayPool<byte>.Shared.Return(array);

ArrayPool<T>のミソは、長さ20を要求した時に20以上の長さの配列が返ってくるのは保証されてますが、長さ20の配列が来るとは限らない点。要求した以上の長さの配列が返ってきても、目的はバッファなので困らないです。また、一つ注意点があり、ここで取得できる配列は0初期化されていないということです。たまたま全部0だった場合、あなたの今日のラッキーナンバーは0です。

ArrayPool<T>.Shared.Rentで取得できる配列の長さはランダムではなく実は決まっていて、先ほどの20を要求した場合は配列長32の配列が返ってきます。とりあえず、要求した長さ以上の長さの良い感じの配列が返ってきます。

「良い感じの長さ」という説明で納得できた方は、この記事をここまで読んでいただきありがとうございます、お疲れさまでした。ブラウザの戻るボタンを押していただいて大丈夫です。

納得できない方は続きをどうぞ。

内部実装

中がどうなっているのか、解体新書と名乗ったからにはArrayPool<T>の中身を見ます。 実際のソースコードは以下のリンクからどうぞ。

(注) 本記事執筆時点でのランタイムのソースコードをもとに解説しています (.NET Core 3.1 ~ .NET5 preview ぐらいの時期)。最新の実装とは異なっている可能性があります。

github.com

ArrayPool<T>.SharedインスタンスTlsOverPerCoreLockedStacksArrayPool<T>クラスで、重要なとこだけ分かりやすく抜き出すとこんな感じ。

class TlsOverPerCoreLockedStacksArrayPool<T> : ArrayPool<T>
{
    [ThreadStatic]
    private static T[]?[]? t_tlsBuckets= new T[17][];
}

バケツは長さ17で、ここに17個の配列がプールされています。

ここについているThreadStaticAttributeは、ざっくりいうとフィールドをスレッド内シングルトンにできる属性。 ThreadStaticAttributeをつけたフィールドは OS の Thread Local Storage メモリ領域に割り当てられ、C#的にはスレッドごとに独立した変数が存在している状態になるため簡単にスレッドセーフにできる優れモノ。

このバケツにプールされる17個の配列が、ArrayPool<T>.Shared.Rent(int)で貸し出され、ArrayPool<T>.Shared.Return(T[])でプールに戻ってきます。

Rent/Returnメソッド

Rentメソッドは、まず要求された配列長にあういい感じの配列をバケツから探します。

17個の配列はそれぞれ異なる配列長になっており、具体的には、長さが16, 32, 64, ..., 220 の17個の配列がプールされています。先ほど長さ20を要求した場合、長さ32の配列が返ってくるのはこのため。

プールされている配列が2nなのは、要求に合う配列をビット演算で高速に見つけられるため (だと思う)。 要求された長さmに合う配列がバケツの何番目にあるかは、ビット演算でmの上位ビット側に0がいくつあるかを数えることで求められます。そしてなんと、上位ビットの0の個数を数えるのは、たとえば x86 だとLZCNTというCPU のハードウェア命令1語でできて超高速。ただしここはハードウェア依存なのでIntrinsicで実装されています。

Hardwere Intrinsic については以下に記事を参照。

ufcpp.net

ArrayPool<T>.Share.Rent(int)は長さの合う配列を見つけると、その配列が貸し出されます。

ReturnメソッドはRentの逆の操作を行います。戻ってきた Pooled な配列がバケツの何番目に戻るかを求めてバケツに配列を格納します。

一度生成した配列をプールして使いまわすため、ゼロアロケーションでパフォーマンスが良いのですが、必ずしも速いかというと実はそうではない場合もあります。

以前の記事で実際にベンチマークを取ったものを見ると、単純な速度では1024バイト程度までならnew T[N]する方が速かったりします。ただし、このベンチマークGC にかかる時間は含まれていません。というのも、GC にかかる時間はメモリの状態によっていろいろ変わるので、ここで生成したnew T[N]単体を回収するのにかかる時間というのは測定できるようなものではないためです。

gen0 の GC はかなり高速なのでサイズが小さい場合はそこまで厳密に気にしなくてもいいのですが、ゼロアロケーションというのはとりあえず気持ちがいいですし、ArrayPool<T>.Sharedが遅いかというと、別に遅くはないです。バッファ目的で配列が欲しい時は、とりあえず何も考えずArrayPool<T>.Sharedを積極的に使ってください。

もっと解体新書

ArrayPool<T>.Sharedをもっと知りたい。

  • Rentで既に貸し出されている状態でさらにRentするとどうなる?
  • Rentから取得したものではない配列をReturnするとどうなる?

前述の通り、ArrayPool<T>.Sharedの中身は、それぞれ長さの違う17個の配列をプールしており、それぞれの配列は独立しています。つまり、

var array16 = ArrayPool<int>.Shared.Rent(16);
var array32 = ArrayPool<int>.Shared.Rent(32);
var array64 = ArrayPool<int>.Shared.Rent(64);
ArrayPool<int>.Shared.Return(array16);
ArrayPool<int>.Shared.Return(array32);
ArrayPool<int>.Shared.Return(array64);

は何の不都合もなく、問題ありません。しかし、以下の借り方は多少のロスが出ます。

var array20 = ArrayPool<int>.Shared.Rent(20);
var array30 = ArrayPool<int>.Shared.Rent(30);
ArrayPool<int>.Shared.Return(array20);
ArrayPool<int>.Shared.Return(array30);

長さ20で配列を要求した時に実際に得られる配列は、前述の通り長さ32です。同様に30を要求した時も32です。この時、2回目のRentでは32の配列は既に貸し出されており、ArrayPool<T>.Sharedは持っていません。この場合、新たに長さ32の配列を生成して返します。

この時、長さ32の配列は2つ貸し出されている状態ですが、ArrayPool<T>.Sharedはこの2つの配列を特に区別はしません。配列の長さのみによって区別され、先に返却された方が再びプールされます。そして、2つ目の配列が返却されたときは、既に内部に別の長さ32の配列がプールされているため、無視されます。特に例外が発生したりはしません。その後、返却はされた2つ目の配列はプールされることなくめでたくガベージとなり…………ません。(!?) ArrayPool<T>.Sharedはそう簡単にはガベージにさせてくれません。(後述)

では、借りていない配列を返した場合はどうなるのでしょうか?

// 借り物ではない配列を返す (配列長 32)
ArrayPool<int>.Shared.Return(new int[32]);

// 借り物ではない配列を返す (配列長 30)
ArrayPool<int>.Shared.Return(new int[30]);

1つ目の長さ32の配列の方は、特に問題ありません。先ほどと同様、配列は長さのみによって区別されるため、長さ32の配列が内部にない場合はこの借り物ではないのに返却した配列がプールされ、既に内部にプールされている場合は無視されます。

2つ目の長さ30の配列は例外が発生します。プールされる配列は長さが 2n (n=4, ... , 20) の物しか受け付けません。とはいえ、よっぽど酔っぱらってもいない限り、借りてもいない配列を返すようなことは普通しないため、問題にはなりません。

TlsOverPerCoreLockedStacksArrayPool<T>

最初の方にサラッと名前を出しましたが、ArrayPool<T>.Sharedの実体はTlsOverPerCoreLockedStacksArrayPool<T>という名前長すぎのインスタンスです。

'Tls' はおそらく Thread Local Storage のことで、スレッドごとに独立してる、つまりThreadStatic属性の意味するところであり、先ほどまで説明していたArrayPool<T>の基本的な機能のことでしょう。

そして、’PerCoreLockedStacks’ ってなんぞ?って話ですが、実装を見れば本当に per core で locked な stacks の ArrayPool という名前のまんまです。そして、これがArrayPool<T>.Sharedの2段目のプールで、1段目のプールからこぼれ落ちた配列を受け止めます。

2段目のプールの機能だけを簡略化すると、下のような実装です。

class TlsOverPerCoreLockedStacksArrayPool<T> : ArrayPool<T>
{
    const int NumBuckets = 17;  // 2^4 ~ 2^20 の17個
    private PerCoreLockedStacks?[] _buckets
        = new PerCoreLockedStacks[NumBuckets];
}

class PerCoreLockedStacks
{
    private LockedStack[] _perCoreStacks
        = new LockedStack[Math.Min(Environment.ProcessorCount, 64)];

    public void TryPush(T[] array) { ... }
    public T[]? TryPop() { ... }
}

class LockedStack
{
    private T[]?[] _arrays = new T[8][];

    public void TryPush(T[] array)
    {
        lock(this) { ... }
    }

    public T[]? TryPop()
    {
        lock(this) { ... }
    }
}

つまり、TlsOverPerCoreLockedStacksArrayPool<T>の中に17個 (各配列の長さ用) のPerCoreLockedStacksがあり、それぞれその中には CPU のコアの数だけLockedStackがあり、さらにそれぞれのその中に8個まで配列を保持でき、それがlockによってスレッドセーフに守られているというとんでもない構造です。

ここまで見ればTlsOverPerCoreLockedStacksArrayPool<T>という名前が名前の通りの機能すぎて笑います。 (よい命名だと思います)

とにかく執拗なまでのプールの頑張りなのですが、プールから目的の配列を取り出したり戻したりするまでに必要な処理が多く、またlockも入っている (実際のソースはMonitorで書かれてましたが糖衣構文なので同じ) ので、1段目よりも遅いです。1段目のプールで済むならそれに越したことはなく、そのためには、同じ長さの配列を二重に借りない、きちんと返す、をしていれば2段目には入りません。

また、2段目のプールが1段目と異なる点として、gen2 の GC が発生するたびに少しずつガベージになって消えていくということです。gen2 の GC が発生したタイミングで2段目に保持されている配列を全てガベージに流してしまうと、GC の停止時間を大幅に増加させてしまうことになるため、良い感じにちょっとずつ放流されていくようになっています。実装が気になる人はソースを見てください。

余談ですが、この gen2 の GC を検知する方法が面白くて、ファイナライザを実装したゴミオブジェクトを適当に捨て、ファイナライザが呼ばれるたびにコールバックを発火しつつ、GC.ReRegisterForFinalizeメソッドで再び復活するという、永遠にメモリの生死をさまよい続けるゾンビみたいなオブジェクトを使っています。

 

ということで、明日から使えるArrayPool<T>.Shared解体新書でした。

(C#) #if DEBUG を使わないデバッグ分岐

デバッグとリリースで処理を変えたいときは普通は大体以下のように書きます。

public void Foo()
{
#if DEBUG
    Console.WriteLine("This is Debug.");
#else
    Console.WriteLine("This is Release");
#endif
}

正直見にくいです。コンパイルされない側の記述は Visual Studio のコードアナリティクスもシンタックスハイライトもなくなり、非常に使いにくい。当然、関数名変更などのリファクタリングも効かなくなり、いつの間にかリリースビルドが通らないコードになっていたり、なんてこともあり得ます。

これぐらいの分岐なら全然いいですが、もっといくつもシンボルがあって大量に分岐があちこちに書かれているコードは非常に苦痛。おいおいここはC++じゃないんだぜ

なので、以下のように書きます。

internal static class AssemblyState
{
    public static bool IsDebug =>
#if DEBUG
    true;
#else
   false;
#endif
}

public void Foo()
{
    if(AssemblyState.IsDebug)
    {
        Console.WriteLine("This is Debug.");
    }
    else
    {
        Console.WriteLine("This is Release.");
    }
}

[2022/10/26 追記]

結構この記事を見てくれる人がいたので修正。もともと上記のコードはconst bool IsDebug =として定数で定義していましたが、static bool IsDebug =>として static な getter のみのプロパティに修正しました。 定数で定義しているとif (false) になる部分に対して、絶対に通らない分岐がありますとコンパイラに警告されてしまいます。 プロパティにしておくとこの警告は出ず、かつ実行時にはインライン展開されて最適化され定数で書いた場合と全く同一になります。

プリプロセッサディレクティブをまとめて書くために1つクラスを用意しておいて、そこに定数で定義しておくと、あとは普通にbool型として分岐できます。分岐したい部分がいくつあっても、#ifを書くのは一ヵ所で済みます。

なにより、普通のC#のコードになっているので、シンタックスハイライトが消えたり参照が効かなかったりなんてならないのがいいです。

この場合、実行時に分岐処理は発生しません。実行時に分岐が定数の場合はJITが不要なifと分岐を削除し、機械語レベルで最初のコードと同じになります。つまり、IL には分岐が存在するが、機械語には分岐がないため実行速度も落ちません。

ほんとに大丈夫なのか

将来的に JIT コンパイルの分岐削除がなくなるかもしれないじゃないですかヤダーって話ですが、たぶんそれはないです。

なぜなら .NET の中にも JIT の分岐削除を前提としたコードがpublicで存在しているからです。C#は言語的に非常に破壊的変更に敏感で、特にpublicで公開されているコードの挙動なんかはまず変わりません。

具体的に何かというと、CPU固有命令を提供している部分などです。

たとえばSystem.Runtime.Intrinsics.X86.LzcntクラスにIsSupportedというプロパティがありますが、これは実行環境の CPU が x86 の lzcnt 命令が使える場合は true になり、

if(Lzcnt.IsSupported)
    return Lzcnt.LeadingZeroCount(value);

のように分岐でき、JIT が分岐を消すことを前提にした使い方をします。わざわざ CPU 命令を持ち出すぐらいですから超パフォーマンス重視の部分に使われる想定で、分岐を消さないなんていう無駄はまずありえないです。 つまり分岐は消えます。

 

というように、うまく JIT の挙動を活用すればあちこちに#if DEBUGを書く見にくいコードから解放されます。

ただしプリプロセッサディレクティブを使えばメソッド定義自体の存在をなかったことにしたり、 C#の文法的に無理なこともメタ的に書けるので全てのケースで今回のように書けるわけではないので必要なときもありますけどねー。

Unity (.netstandard2.0) でSpan<T>を使う

Unity でAPIターゲットを.netstandard2.0にしてSpan<T>を使うときに必要なライブラリたち。

.net 4.x系をターゲットにしても使える気はする(が面倒なので確認していない)。まあ、多少依存関係が違うのでnugetのパッケージのdependencyを見て適当に必要なの持ってこればOK。monoおよびIL2CPP環境で動かなさそうなものがあったら知らぬ。

必要な物 (.net standard2.0)

nuget から必要なものを持ってくる

Span<T>自体は System.Memory.dll 内にあるが、依存関係で下の二つのdllも必要。 依存関係自体はもう1つ System.Numerics.Vectors.dll もあるがUnityの場合これはnugetから取らなくても初めから参照されている。

Unityはそのままではnugetと連携できないので上記のリンクから .nupkg ファイルを直接ダウンロードしてdllを引っこ抜いてプロジェクトに置く。.nupkg はただのzipなのでzipにリネームして解凍すればいい。

 

Span<T>だけでなくArrayPool<T>やらUnsafeやらもついてくるので楽しさ嬉しさ3倍増し。

(C#) メモリ確保ベンチマーク 6種盛り

バッファの確保用にnew byte[N]なんて書いたらモテませんよ。とはいえ正直確保するバイト数次第。ベンチマーク見ましょう。

メモリ確保 6種盛り

メモリ確保(+破棄)の方法を6種用意した。

// (1)  new
byte[] MarshalAlloc()
{
    return new byte[N];
}

// (2)  ArrayPool
void SharedPool()
{
    var array = ArrayPool<byte>.Shared.Rent(N);
    ArrayPool<byte>.Shared.Return(array);
}

// (3)  Marshal から確保
void MarshalAlloc()
{
    var array = Marshal.AllocHGlobal(N);
    Marshal.FreeHGlobal(array);
}

// (4)  (3) + Memory Pressure
void MarshalAlloc_WithGCPressure()
{
    var array = Marshal.AllocHGlobal(N);
    GC.AddMemoryPressure(N);
    Marshal.FreeHGlobal(array);
    GC.RemoveMemoryPressure(N);
}

// (5)  C++ の "std::malloc", "std::free" の呼び出し
void NativeAlloc()
{
    var array = NativeAllocator.Alloc(N);
    NativeAllocator.Free(array);
}

// (6)  (5) + Memory Pressure
void NativeAlloc_WithGCPressure()
{
    var array = NativeAllocator.Alloc(N);
    GC.AddMemoryPressure(N);
    NativeAllocator.Free(array);
    GC.RemoveMemoryPressure(N);
}

まず(1)は普通のマネージドな配列です。これをベースに他の方法の速度を比較していきます。 (2)はArrayPool<T>.Sharedからの配列取得と返却。 (3)と(4)はMarshal.AllocHGlobal(int)からのアンマネージドメモリの取得と解放で、(4)は GC に MemoryPressure をかけています。 (5)と(6)はアンマネージドメモリの確保を、C++std::mallocstd::freeするだけのdllを用意して P/Invoke しています。(3)と(4)との速度比較のために用意しました。

ベンチマーク結果

ベンチマークは BenchmarkDotNet で測定。環境は .Net Framework 4.8 (x86) です。なんで .NET Core 3.1 (x64) じゃないんだよとツッコミを入れられそうですが、たまたまローカルに転がってた過去のベンチマーク用のプログラムを適当に流用して測定したためです。Core 3.1 で測定したら全体的に1割程度は速くなりそうな気がしますが、各手法の速度比はあまり変わらない(はず)なので許して。

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.18362.778 (1903/May2019Update/19H1)
Intel Core i5-4300U CPU 1.90GHz (Haswell), 1 CPU, 4 logical and 2 physical cores
  [Host]     : .NET Framework 4.8 (4.8.4121.0), X86 LegacyJIT
  DefaultJob : .NET Framework 4.8 (4.8.4121.0), X86 LegacyJIT

f:id:ikorin2:20200513022105p:plain

(1) が線形、(2)がN=2^20までは定数なのは想定通り。(2)のArrayPool<T>はそこまで高速な処理ではないのでN=1024程度まではnew byte[N]に単純な速度では負けることが分かります。ただしガベージは0。 ArrayPool<T>N=2^20まではプールされているが、N=2^20+1からはプールされない配列を新たに生成しているため、速度が約千倍に低下していることがわかります。(プールされないためガベージになる上、85000 byte 以上なので LOH (Large Object Heap) に入り gen2 になる最悪のシナリオを踏んでいる)

(3)と(5)、および(4)と(6)はほぼ同じ動きをしており、Marshal.AllocHGlobalの中身がほぼstd::mallocと同じであると推測できます。Marshal.AllocHGlobalの中身を追うと、windows の場合 P/Invokekernel32.dllLocalAllocを呼んでいます。一方std::mallocコンパイルされたときにどうなるか正直詳しく知らないが、ベンチマークのグラフがぴったりシンクロしているの見る限りほぼ同じことをしていると思う。

(4)と(6)が(3)と(5)に比べて明らかに遅いのは、単純に処理が増えているのと、MemoryPressureがGCを誘発しているからです。

C#のレイヤーからだけ見るとアンマネージドメモリの確保も (1) と同様線形になりそうな気がするが、アンマネージドメモリはOSのメモリ管理の影響を直に受けるのでそんな単純にはいかない模様。ベンチマークを見る限りはN=2^14程度までは定数、N=2^19程度以上ではほぼ線形になってる感じがする。

最適解

  • そんなもんはない。

最適解なんてものがあれば誰もメモリ管理で苦労しない。各種方法の特性を適切に覚えておいて柔軟に使い分けしましょうねという話。しかしあまりに行き過ぎると目的に応じて自作GCに片足突っ込む不毛な沼になりかねないので、まあ柔軟に対応しましょう。大抵の目的なら .NETGC は十分高性能だし gen0 の回収は非常に速い。ただし LOH に配列確保するのはやめましょうねぇ~

余談 (Unity)

Unity の場合って GC はどうなってるんですかね。2017年ぐらいの時点ではUnityのランタイムのGCは世代別GCになってなくて、毎回フルGCが走るとかいうドン引き仕様になっていた気がするんですが、2020年現在変わってたりするんですかね。

[追記 2020/06/08]

UnityのGCは特に世代別に変わったわけではないし、実際世代別だから高性能でいいって訳でもない。とはいえUnityも一気にGCが走ることは問題になりうると認識してるのでインクリメンタルGCを取り入れた。Unity2019.1a10からインクリメンタルGCは実験的機能として実装されているが、将来的にはこちらをメインに据えたい模様。

ゲームとしての使用方法を考えると各フレームに負荷を分散させることで1回あたりのStop the Worldを軽減させるのが目的なので正しいのかなとは思う。 現在のBoehm GCをそのままにインクリメンタルGCを取り入れた理由や、他のGCアルゴリズムを採用しなかった理由については公式から一応説明が出ている。

https://blogs.unity3d.com/jp/2018/11/26/feature-preview-incremental-garbage-collection/

簡単に言うとGCアルゴリズム変更のコストとパフォーマンスを加味した結果、インクリメンタルGCにしたっぽい。

インクリメンタルGCについて特にここで解説はしないが、Mark and Sweep の処理を一気にせず細切れにすることで停止時間を分散させるもの。なので総停止時間自体は変わらない (write barrierの分多少はオーバーヘッドは増える)

(C#) Span<T> を List<T>.AddRange したい

タイトル通りですが本記事執筆時点 (2020/4/15) の最新である .NET Core 3.1 ではList<T>AddRangeメソッドにダイレクトにSpan<T>およびReadOnlySpan<T>を突っ込むことはできません。というのもList<T>AddRangeメソッドは

public void AddRange(IEnumerable<T> items);

しかオーバーロードがないためです。Span<T>ReadOnlySpan<T>foreach列挙可能ではあるがIEnumerable<T>ではありませんし、そもそもref structの制約で interface にキャスト不可によりIEnumerable<T>になりえません。

理想としてはAddRangeReadOnlySpan<T>オーバーロードが欲しい。(Span<T>ReadOnlySpan<T>への暗黙的キャストが効く上、キャストのコストは実質0なので問題ない`)

Span<int> span = ...;
List<int> list = ...;

list.AddRange(span);    // これができるとうれしい

しかし、実際はできないので、現状の回避策としてはforeachAddを使うしかない。

Span<int> span = ...;
List<int> list = ...;

foreach(var item in span)
{
    list.Add(item);
}

が、まあ当然列挙毎にAddと列挙のオーバーヘッドが入るのでAddRangeより遅い。Span<T>のもとになっているのが配列 (例えばint[]) とかなら、Span<int>にせず配列のままAddRangeすればIEnumerable<T>に入ってくれるし、AddRange内でのICollection<T>による要素数既知の最適化にハマるので十分早い。しかし、Span<T>のもとになっているのがアンマネージメモリだと配列ではないし、そもそもIEnumerable<T>ですらないのでどうしようもない。 上記のように foreachAddする以外の選択肢がない。非常に悲しい。

 

個人的には非常に欲しい API なので .NET Core の github リポジトリの issue に同様の提案が上がっていないのか調べたら、案の定あった。それがこちら。

github.com

で、内容をまとめると、

  • この API が必要という根拠、具体的なサンプルや場面が欲しい。
  • 現状回避策として、自作の List<T> で置き換えるのが妥当

というようなコメントがついてましたね。。。API の追加は簡単ではない。とはいえ、重要なのはこのリポジトリは本記事執筆時点では close されていません。というかよく見ると、.NET 5 (.NET Core 3.1 の次のメジャーバージョンの .NET) のマイルストーンに 提案 API が入っているではないですか!!歓喜

.NET 5 のリリース予定は 2020/11 までと予定されているため、それまではないですが、.NET 5 ではおそらくReadOnlySpan<T>オーバーロードが入ると思われます。

.NET Core / .NET Framework ではどうするの

前述の通り、次期リリースでは入るんでしょうが .NET Core / .NET Framework で今私は使いたいんだ!!!と、当然話はそこに帰結する。なので unsafe なC# の暗黒面の力を借りて拡張メソッドで実装した。

static class ListExtension
{
    internal static void AddRange<T>(this List<T> list, ReadOnlySpan<T> span) => list.InsertRange(list.Count, span);

    internal static void InsertRange<T>(this List<T> list, int index, ReadOnlySpan<T> span)
    {
        if(list is null) { throw new ArgumentNullException(); }
        static void EnsureCapacity(List<T> original, ListDummy<T> dummy, int min)
        {
            if(dummy._items.Length < min) {
                const int DefaultCapacity = 4;
                int newCapacity = dummy._items.Length == 0 ? DefaultCapacity : dummy._items.Length * 2;

                // Allow the list to grow to maximum possible capacity (~2G elements) before encountering overflow.
                // Note that this check works even when _items.Length overflowed thanks to the (uint) cast
                const int MaxArrayLength = 0X7FEFFFFF;      // This size is compatible with Array.MaxArrayLength. (This is internal)
                if((uint)newCapacity > MaxArrayLength) newCapacity = MaxArrayLength;
                if(newCapacity < min) newCapacity = min;
                original.Capacity = newCapacity;
            }
        }

        var dummyList = Unsafe.As<ListDummy<T>>(list);
        if((uint)index > (uint)dummyList._size) {
            throw new ArgumentOutOfRangeException();
        }
        int count = span.Length;
        if(count > 0) {
            EnsureCapacity(list, dummyList, dummyList._size + count);
            if(index < dummyList._size) {
                Array.Copy(dummyList._items, index, dummyList._items, index + count, dummyList._size - index);
            }

            span.CopyTo(dummyList._items.AsSpan(index));
            dummyList._size += count;
            dummyList._version++;
        }
    }

    private abstract class ListDummy<T>
    {
        internal T[] _items = default!;
        internal int _size;
        internal int _version;
#if NETFRAMEWORK
        internal object _syncRoot = default!;
#endif

        private ListDummy() { }
    }
}

[2020/07/25 追記]

これ、気が付いてしまったんですけど、これ単体ならおそらく問題ないような気がしますが、 以前の記事List<T>からSpan<T>を 引っこ抜いてくるのと組み合わせるとちょっとマズイ気がします。 具体的には、List<T>の自分自身から引っこ抜いたSpan<T>を自身にこのAddRangeInsertRangeすると、 容量拡大時やメモリ移動時におかしなことが起こりそうな気がします。ちょっと詳しく挙動を見ないとわからない (すいません)

これでAddRangeSpan<T>をダイレクトに入れられます。ついでにInsertRangeも使えます。上記のソースコードを見て何をやってるかは把握してください。というか見て分からない人は使ってはダメです、Unsafeを悪用しているので問題が起こった時に困ると思います。

上記ソースコード中の#if NETFRAMEWORKですが、NETFRAMEWORK .NET Framework をターゲットにコンパイルしたときには自動で追加されるシンボルです。.NET Framework .NET Core ではList<T>の持つフィールドが異なるため、必要です。

この拡張メソッドを使うとAddRangeSpan<T>をダイレクトアタックできます。

最後にベンチマークベンチマークに使ったのは以下の3つのコードで 要素数 N=10000000

  • int[]IEnumerable<T>AddRangeしたもの
  • int[]Span<T>で自作のAddRangeしたもの
  • int[]を、foreach+Addしたもの

で、 BenchmarkDotNet で測定しました。

[MemoryDiagnoser]
public class ListPerformanceTest
{
    private const int N = 10000000;
    private static int[] _items;
    private List<int> _list;

    [GlobalSetup]
    public void GlobalSetup()
    {
        _items = new int[N];
    }

    [IterationSetup]
    public void Setup()
    {
        _list = new List<int>();
    }

    [Benchmark(Baseline = true)]
    public List<int> AddRange_IEnumerable()
    {
        IEnumerable<int> items = _items;
        _list.AddRange(items);
        return _list;
    }

    [Benchmark]
    public List<int> AddRange_Span()
    {
        ReadOnlySpan<int> items = _items;
        _list.AddRange(items);
        return _list;
    }

    [Benchmark]
    public List<int> Add_SpanIter()
    {
        ReadOnlySpan<int> items = _items;
        foreach(var item in items) {
            _list.Add(item);
        }
        return _list;
    }
}

結果は以下の通り。

Method Mean Error StdDev Ratio RatioSD Gen 0 Gen 1 Gen 2 Allocated
AddRange IEnumerable 18.23 ms 2.751 ms 8.111 ms 1.00 0.00 - - - 38.15 MB
AddRange Span 17.56 ms 2.609 ms 7.692 ms 0.97 0.11 - - - 38.15 MB
Add SpanIter 81.10 ms 1.584 ms 2.168 ms 5.68 2.55 - - - 128 MB

当然のごとくforeach+Addは遅い。AddRangeIEnumerable<T>と自作のReadOnlySpan<T>は誤差の範囲内で自作の方が速い。何回か測定してもうちょっと速い時もあったがそれはまあ誤差。対象がint[]なので、ICollection<T>の型チェックによる分岐処理にハマるのでIEnumerable<T>でも十分速い。差が出るのは、IEnumerable<T>の方は他にも微妙に別の型チェックや引数チェックを行ったり、ReadOnlySpan<T>の自作メソッドより余計なことを少ししているせいだろうか。どちらにせよReadOnlySpan<T>オーバーロードAddより十分速い。

参考文献

.NET Framework .NET Core のList<T>ソースコードは以下のリンク。

.NET Framework

github.com

.NET Core

github.com

(C#) List<T>からSpan<T>を引き抜いて高速化

List<T>GetEnumerator()を実装しているため当然foreachで回せる。foreachの速度を落とさないために具象型のEnumeratorを返したりEnumeratorを構造体実装していたりと工夫は凝らされているが、それでもSpan<T>T[]には数倍~10倍程度遅い。この点に関しては、List<T>は状態をバージョン管理しており、列挙中の変更を検知しているためどうしようもない。forで回したところで、ランタイムによってインデックスの境界値チェックが消える特殊最適化がかかるSpan<T>T[]には原理的に勝てない。

 

しかし、List<T>は柔軟で使いやすい。ただ列挙速度も落としたくない。そこで列挙時だけList<T>Span<T>にしてしまおうという話。

以下List<T>の実装を簡略化したもの。

public class List<T>
{
    private T[] _items;
    // ・
    // ・
    // ・
}

List<T>の中身はただの配列なので、System.Runtime.CompilerServices.Unsafeで中身を引き抜く。 ただし、.NET Framework .NET Core でList<T>の内部実装が異なるので注意。 上記のように、先頭にT[]があるのは共通なのでそこだけ利用する。(メモリレイアウトは必ずしもソースコードの定義順に並ぶわけではないが、今回T[]は先頭に来る)

ちなみに .NET Framework のList<T>ソースはこちら。 github.com

.NET Core のList<T>ソースはこちら。

github.com

 

List<T>からSpan<T>の引き抜き方は、ダミークラスを用意して拡張メソッドを用意するだけ。

class ListDummy<T>
{
    internal T[] Items;
}

static class ListExtensions
{
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    internal static Span<T> AsSpan<T>(this List<T> list)
    {
        return Unsafe.As<ListDummy<T>>(list).Items.AsSpan(0, list.Count);
    }
}

あとはこれでforeachを回すだけ。

var list = new List<int>();
foreach(var item in list.AsSpan())
{
    Console.WriteLine(item);
}

注意点は3つ。1つはList<T>の中身をすっぽ抜いているので、容量の拡大時に参照が変わるのでSpan<T>を保持してはいけない。これは一般的な可変長配列の実装を理解していれば分かると思う。上記のAsSpan()Unsafeの力によって実質無料みたいなものなのでその都度AsSpan()してください。

2つ目はこの方法はList<T>の内部実装に依存しているため、将来的にランタイムのバージョンが上がった時にList<T>のメモリレイアウトが変わると正しく動かない点。なのでpublicなライブラリとして公開するのは怖い。自分で管理できる範囲でどうぞ。

3つ目は、yield returnできない点。これはどちらかというとref structの制約。Span<T>.Enumeratorref structなのでインスタンスがヒープに乗ってしまうyield returnはできない。

 

List<T>Span<T>にしてforeachを回すと当然Span<T>と同速が得られるため、使いどころによっては速度改善につながるかもしれない。

[2020/12/31 追記]

.NET5 からは新たに追加されたSystem.Runtime.InteropServices.CollectionsMarshal.AsSpanメソッドを使うと、Unsafeクラスを使わず合法的にList<T>からSpan<T>を取り出せます。

var list = new List<int>();
Span<T> span = CollectionsMarshal.AsSpan(list);

(C#) ラムダ式による this のキャプチャ

ラムダ式による外部変数のキャプチャは、コンパイラによって暗黙的に匿名クラスが作られ、コールされるたびに匿名クラスのインスタンスnewされるため、ヒープアロケーションが発生する。

using System;
public class Class
{    
    public Action Method(int num)
    {
        return () => Console.WriteLine(num);
    }
}

上記のコードはコンパイラによって以下のコードと同義に解釈される。(コンパイラ生成コードの名前は見やすさの為に適当に変えてある)

public class Class
{
    [CompilerGenerated]
    private sealed class HiddenClass
    {
        public int num;
        internal void A() => Console.WriteLine(num);
    }

    public Action Method(int num)
    {
        var tmp = new HiddenClass();
        tmp.num = num;
        return tmp.A;
    }
}

外部変数のキャプチャは、暗黙的に、キャプチャされた変数をメンバに持つクラスインスタンスを生成し、そのインスタンスメソッドがデリゲートとなる。無駄なガベージを生むため、パフォーマンス優先の場所では可能ならキャプチャは避けるのが良い。

 

そして本題。キャプチャは必ず暗黙的クラスインスタンスを生むのかというと、実はそうならない場合もある。その例は以下の場合。

using System;
public class Class
{
    private int _num;    
    public Action Method()
    {
        return () => Console.WriteLine(_num);
    }
}

先ほどと異なるのは、クラスのインスタンスメンバをキャプチャしている点。この場合、キャプチャされているのはthisという考え方になる。このコードのコンパイラによる解釈は以下のようになる。

using System;
public class Class
{
    private int _num;

    public Action Method()
    {
        return A;
    }

    [CompilerGenerated]
    private void A() => Console.WriteLine(_num);
}

thisのみをキャプチャしているラムダ式は、自身のクラスインスタンスメソッドに置き換わるため、無駄なアロケーションが発生しない。よかったですねぇ~