List<T>の高速初期化手法

はじめに

「【C#】List<T>を任意の値・要素数で初期化する」という記事に対してコメントしていた内容を記事として起こしました。

半分お遊びみたいな内容なので、気楽に読んでいただければと思います。

まず考えたこと

元記事としては、「capacity を指定して List<T> を new したときに、インデクサでその capacity 分の範囲を自由にアクセスしたい」という要件がありました。

基本的には、「capacity = 内部バッファのサイズ」であり、インデクサでアクセスする場合には capacity ではなく Countプロパティ をもとにアクセス可能かのバリデーションをします。

つまり、Countプロパティ さえ書き換えてしまえば、要件をクリアできると考えました。

実装

実装に入る前に

ただ、ここで一つ問題があります。Countプロパティ は readonly なわけです（当然といえば当然なのですが...）。

こういうときは、だいたいリフレクションを使えば何とかなります。

今回も例に洩れずどうにかなるパターンだったので、リフレクションを利用していきます。

インサイド List<T>

List<T> は _items という内部バッファ領域(= 配列)と、 _size という要素数フィールドを持っています。

List<T> は capacity を指定して new すると、capacity分の長さをもつ配列を生成し _items を初期化します。

その際、_size は要素を追加されていないため 0 のままとなります。

つまり、今回は _size フィールドをリフレクションで強制的に書き換えてしまえば、インデクサで各要素に対してアクセスすることが可能になるわけですね。

実装してみる

class Program
{
    static List<T> GenerateList<T>(int capacity)
    {
        var ls = new List<T>(capacity);
        var type = ls.GetType();

        // _size フィールドを取得
        var size = type.GetField("_size", BindingFlags.Public | BindingFlags.Instance | BindingFlags.NonPublic);
        // _size フィールドに capacity を書き込む
        size.SetValue(ls, capacity);

        return ls;
    }

    static void Main(string[] args)
    {
        // do somethings
    }
}

この GenerateList<T> を使えば、以下のようにインデクサを使ってまだ追加していない要素番号に対してもアクセスすることができるようになります。

class Program
{
    static List<T> GenerateList<T>(int capacity)
    {
        var ls = new List<T>(capacity);
        var type = ls.GetType();
        var size = type.GetField("_size", BindingFlags.Public | BindingFlags.Instance | BindingFlags.NonPublic);
        size.SetValue(ls, capacity);
        return ls;
    }

    static void Main(string[] args)
    {
        // var normal = new List<int>(100); // 普通に new すると...
        // normal[50] = 200;                // System.ArgumentOutOfRangeException で死ぬ
        // Console.WriteLine(normal[50]);

        var ls = GenerateList<int>(100);    // GenerateList<T> を使えば、
        ls[50] = 200;                       // アクセスできる！！
        Console.WriteLine(ls[50]);          // output: 200
    }
}

任意の値で初期化可能にする

元記事では「任意の値で初期化したい」という要件もあったため、これも実現してみます。

static List<T> GenerateList<T>(int capacity, T @value)
{
    var ary = new T[capacity];

    // ここで各要素を初期化.
    //    ※ C/C++ のネイティブ関数をコールすれば高速化できそう...
    for (int i = 0; i < capacity; i++)
        ary[i] = value;

    var ls = new List<T>();
    var type = ls.GetType();

    // _size フィールドを取得
    var size = type.GetField("_size", BindingFlags.Public | BindingFlags.Instance | BindingFlags.NonPublic);
    // _items フィールドを取得
    var items = type.GetField("_items", BindingFlags.Public | BindingFlags.Instance | BindingFlags.NonPublic);

    // _size フィールドに capacity を書き込む
    size.SetValue(ls, capacity);
    // _items フィールドに ary を書き込む
    items.SetValue(ls, ary);

    return ls;
}

これはお遊びの領域ですが、並列化すればもっと高速にできます。

static List<T> GenerateList<T>(int capacity, T @value)
{
    var ary = new T[capacity];

    // チャンク分けしてあげる
    Parallel.ForEach(Partitioner.Create(0, capacity), partition =>
    {
        var (start, end) = partition;
        for (int i = start; i < end; i++)
            ary[i] = value;
    });

    var ls = new List<T>();
    var type = ls.GetType();
    var size = type.GetField("_size", BindingFlags.Public | BindingFlags.Instance | BindingFlags.NonPublic);
    var items = type.GetField("_items", BindingFlags.Public | BindingFlags.Instance | BindingFlags.NonPublic);
    items.SetValue(ls, ary);
    size.SetValue(ls, capacity);
    return ls;
}

また、Func<int, T> を受け取るようにすることで、各インデックスに対して任意の値で初期化することが可能になります。

static List<T> GenerateList<T>(int capacity, Func<int, T> generator)
{
    var ary = new T[capacity];

    // チャンク分けしてあげる
    Parallel.ForEach(Partitioner.Create(0, capacity), partition =>
    {
        var (start, end) = partition;
        for (int i = start; i < end; i++)
            ary[i] = generator(i);
    });

    var ls = new List<T>();
    var type = ls.GetType();
    var size = type.GetField("_size", BindingFlags.Public | BindingFlags.Instance | BindingFlags.NonPublic);
    var items = type.GetField("_items", BindingFlags.Public | BindingFlags.Instance | BindingFlags.NonPublic);
    items.SetValue(ls, ary);
    size.SetValue(ls, capacity);
    return ls;
}

拡張メソッド化して便利にする

今回のコードを配列の拡張メソッド化することで、もう少し便利になります。

ただ ToList<T> という名前は使われている上に挙動が違うため、今回は AsList<T> という名前で作っていきます。

public static class Extensions
{
    public static List<T> AsList<T>(this T[] @this) => CreateList(@this);

    public static List<T> AsList<T>(this T[] @this, T @value)
    {
        for (int i = 0; i < @this.Length; i++)
            @this[i] = value;

        return CreateList(@this);
    }

    public static List<T> AsList<T>(this T[] @this, Func<int, T> generator)
    {
        for (int i = 0; i < @this.Length; i++)
            @this[i] = generator(i);

        return CreateList(@this);
    }

    public static List<T> AsListParallel<T>(this T[] @this, T @value)
    {
        Parallel.ForEach(Partitioner.Create(0, @this.Length), partition =>
        {
            var (start, end) = partition;
            for (int i = start; i < end; i++)
                @this[i] = value;
        });

        return CreateList(@this);
    }

    public static List<T> AsListParallel<T>(this T[] @this, Func<int, T> generator)
    {
        Parallel.ForEach(Partitioner.Create(0, @this.Length), partition =>
        {
            var (start, end) = partition;
            for (int i = start; i < end; i++)
                @this[i] = generator(i);
        });

        return CreateList(@this);
    }

    private static List<T> CreateList<T>(T[] src)
    {
        // 空配列で初期化させる.
        // capacity を指定すると, 余計な new が発生する.
        var ls = new List<T>();

        var type = ls.GetType();
        var size = type.GetField("_size", BindingFlags.Public | BindingFlags.Instance | BindingFlags.NonPublic);
        var items = type.GetField("_items", BindingFlags.Public | BindingFlags.Instance | BindingFlags.NonPublic);
        items.SetValue(ls, src);
        size.SetValue(ls, src.Length);

        return ls;
    }
}

上記のようなコードを用意してあげることで、高速に配列を List<T> に変換することが可能となります。

では実際にはどの程度の高速化となっているのでしょうか？

元記事で利用されているコードを拝借して速度比較をしてみたいと思います。

速度比較

public class BenchMark
{
    private const int _capacity = 10_000_000;
    private const int _value = 10_000_000;

    [Benchmark]
    public List<int> A() => new List<int>(new int[_capacity]);

    [Benchmark]
    public List<int> B() => new int[_capacity].ToList();

    [Benchmark]
    public List<int> C() => new List<int>(Enumerable.Repeat(_value, _capacity));

    [Benchmark]
    public List<int> D() => Enumerable.Repeat(_value, _capacity).ToList();

    [Benchmark]
    public List<int> E()
    {
        var a = new List<int>(_capacity);
        a.AddRange(Enumerable.Repeat(_value, _capacity));
        return a;
    }

    [Benchmark]
    public List<int> F()
    {
        var a = new List<int>(_capacity);
        for (int i = 0; i < _capacity; i++) a.Add(_value);
        return a;
    }

    [Benchmark]
    public List<int> AsList001() => new int[_capacity].AsList();

    [Benchmark]
    public List<int> AsList002() => new int[_capacity].AsList(500);

    [Benchmark]
    public List<int> AsList003() => new int[_capacity].AsList(idx => idx);

    [Benchmark]
    public List<int> AsListParallel001() => new int[_capacity].AsListParallel(500);

    [Benchmark]
    public List<int> AsListParallel002() => new int[_capacity].AsListParallel(idx => idx);
}

BenchmarkDotNet=v0.11.5, OS=Windows 10.0.18362
Intel Core i7-8086K CPU 4.00GHz (Coffee Lake), 1 CPU, 12 logical and 6 physical cores
.NET Core SDK=3.0.100-preview6-012264
  [Host]     : .NET Core 3.0.0-preview6-27804-01 (CoreCLR 4.700.19.30373, CoreFX 4.700.19.30308)
             , 64bit RyuJIT  [AttachedDebugger]
  DefaultJob : .NET Core 3.0.0-preview6-27804-01 (CoreCLR 4.700.19.30373, CoreFX 4.700.19.30308)
             , 64bit RyuJIT

Method	Mean	Error	StdDev
A	31.501 ms	0.6147 ms	0.7318 ms
B	31.977 ms	0.6119 ms	0.6548 ms
C	75.954 ms	0.5487 ms	0.4582 ms
D	22.177 ms	0.1895 ms	0.1680 ms
E	62.010 ms	1.1868 ms	1.2187 ms
F	21.785 ms	0.1313 ms	0.1164 ms
AsList001	1.719 ms	0.0617 ms	0.1772 ms
AsList002	14.684 ms	0.2925 ms	0.6297 ms
AsList003	26.270 ms	0.4903 ms	0.4586 ms
AsListParallel001	6.127 ms	0.1199 ms	0.1681 ms
AsListParallel002	6.170 ms	0.1077 ms	0.1007 ms

「圧倒的ではないか、我が軍は！」という結果となりました。

Func<int, T> 版は遅くなることが想定されていたので、許容範囲です。

注目すべきは、A() と AsList001() の箇所です。
同じ処理内容で圧倒的な速度差を見せつけてくれています。

そして、AsListParallel版 を見てみると、並列処理の威力を垣間見ることができます。
たかだか List<T> の初期化のためだけに並列処理を利用するというスーパーリッチなことが許容されるならば、（要素数が多い場合に）多大な恩恵を受けることができるでしょう。

おわりに

今回はお遊び半分でコードを考えてみましたが、実用の許容範囲のものができたと思います。

そして、やはりリフレクション機能は強力ですね。使い方を間違わなければ素晴らしい武器となると思います。

他にも高速化の手立てはいくらでもあると思いますので、何か考え付いた方がいらっしゃいましたらご教示をお願いいたします。