ネコのために鐘は鳴る

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

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

c# .NET programming

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解体新書でした。