Help us understand the problem. What is going on with this article?

超危険で倍速いC#

前書き

今回の手法は危険極まりないです。

使用する場合は自己責任、、、というよりも使わないでください。

本題

高速な配列が欲しいという欲求を満たすべく、危険な遊びに手を出します。

端的に結論から言うと、構造体として確保した領域を配列として扱います。
この時点で相当危険な香りが漂っていますが仕組みを説明していきます。

なぜ構造体のメモリ領域を利用するのか、stackallocの話から説明していきます。

高速な配列がわりとして有名なstackallocですが、なぜ高速なのでしょうか。
それは名前の通り、stack領域と呼ばれるメモリの領域に配列を確保するからです。

メモリはheap領域(以下heap)とstack領域(以下stack)という二つの領域に大別でき、
heapは容量が大きくアクセスが遅く、stackはその逆の性質があります。
また、領域の確保においてもheapstackと比較にならないほど遅いです。

このstackですが、高速な代わりいろいろと制約があります。
名前の通り、値を積んでいくので、
変数はスコープの上から順に確保され、解放されてしまうため、そのスコープから出ることはできません

以上の性質から、stackallocはスコープから出ることができないですし、通常フィールドとして持つこともできません。
そのため若干の使いずらさがあります。

さて、高速な配列もどきを作るにあたって、
このstackallocと同様の性質をもつように作れば高速になるだろうと考えられます。

そして構造体は通常stack上に確保され、stackallocと同等の性質を持ちます。
それどころかインスタンスの生成は構造体のほうがより高速です。

よって、この構造体として確保した領域を活用します。
ですが構造体の領域にアクセスすることは通常できません。

そこで、構造体のポインターを取得し、それをキャストすることであたかも配列のようにアクセスします。
この手法はどこでも確保可能かつコピーが容易でありstackallocの欠点を克服しています。

それを実装したコードを示します。(重要でないところは削除しています)

public struct StackArray2048<T> : where T : unmanaged
{
    private StackBuffer2048 buffer;
    //スペースを確保するだけの構造体を用意。

    public unsafe T* Pointer => (T*)this.buffer.Pointer;
    public int ByteSize => this.buffer.ByteSize;
    public unsafe int Length => this.ByteSize / sizeof(T);
    public unsafe ref T this[int index] => ref this.Pointer[index];
    public Span<T> AsSpan() => this.buffer.AsSpan<T>();
}

//StructLayoutでサイズを指定。 8bit * 256 = 2048bit
[StructLayout(LayoutKind.Sequential, Size = 256)]
public unsafe struct StackBuffer2048
{
    public void* Pointer => Unsafe.AsPointer(ref this);
    //ポインターに変換しているのは参照の追跡を切るため。
    //そうしないと参照の漏洩をコンパイラーが感知してコンパイルエラーになる。
    //そのくらい危険なこと。
    public int ByteSize => sizeof(StackBuffer2048);

    public Span<T> AsSpan<T>() where T : unmanaged => new Span<T>(this.Pointer, ByteSize / sizeof(T));
}

検証

上で制作したコードがどの程度高速なのか計測します。
今回Spanref structでないとフィールドにもてないため、BenchmarkDotNetは使用できませんでした。
なので、アロケーションを4095回、全要素の順次/ランダムアクセスを16777215回繰り返し、それぞれ総経過時間を計測しました。

手法 アロケーション 順次アクセス ランダムアクセス
StackArray 0.0000124 06.1770022 12.3980905
stackalloc 0.0018492 13.2778460 15.4909681
Array 0.0012025 14.6611966 16.3038499

全てにおいてStackArrayが高速となりました。
ただしアロケーションの計測はブレが大きいためあまりあてにならなさそうです。
ですがおおむねStackArrayが小数点5桁、stackalloc/Arrayは小数点3桁となりました。
他は時々によって多少ぶれますがおおむねこのような結果になります。

追記

コードを変更し、一度Spanにキャストしてからアクセスする方法も追加して再計測しました。
忘れていたブランクテストも追加。

手法 順次アクセス ランダムアクセス
StackArray 10.5016237 18.4428574
StackArray(Span) 09.9922429 19.0333651
stackalloc 19.0316231 18.9713633
Array 18.1157960 20.7610231
ブランク 03.1475271 14.2017441

一度Spanにキャストしたほうがポインターのキャストがないため順次アクセスならちょっとだけ早いです。
ランダムアクセスなら境界チェックが入るのでそのままのほうが早いですね。

おまけ

StackArray2048(完全版)
StackArray.cs
using System;

[Serializable]
public struct StackArray2048<T> : IEquatable<StackArray2048<T>> where T : unmanaged
{
    private StackBuffer2048 buffer;
    public unsafe T* Pointer => (T*)this.buffer.Pointer;
    public int ByteSize => this.buffer.ByteSize;
    public unsafe int Length => this.ByteSize / sizeof(T);
    public unsafe ref T this[int index] => ref this.Pointer[index];
    public Span<T> AsSpan() => this.buffer.AsSpan<T>();


    public override bool Equals(object obj) => obj is StackArray2048<T> array && this.Equals(array);
    public bool Equals(StackArray2048<T> other) => this.buffer.Equals(other.buffer);
    public override int GetHashCode() => this.buffer.GetHashCode();


    public static bool operator ==(StackArray2048<T> left, StackArray2048<T> right) => left.Equals(right);
    public static bool operator !=(StackArray2048<T> left, StackArray2048<T> right) => !(left == right);
}
StackBuffer.cs
[Serializable, StructLayout(LayoutKind.Sequential, Size = 256)]
public unsafe struct StackBuffer2048 : IEquatable<StackBuffer2048>
{
    public static bool operator ==(StackBuffer2048 left, StackBuffer2048 right) => left.Equals(right);
    public static bool operator !=(StackBuffer2048 left, StackBuffer2048 right) => !(left == right);

    public void* Pointer => Unsafe.AsPointer(ref this);
    public int ByteSize => sizeof(StackBuffer2048);


    public Span<T> AsSpan<T>() where T : unmanaged => new Span<T>(this.Pointer, ByteSize / sizeof(T));
    public bool Equals(StackBuffer2048 other)
    {
        var p1 = (long*)this.Pointer;
        var p2 = (long*)other.Pointer;
        var length = this.ByteSize / 8;
        for (var i = 0; i < length; ++i) if (p1[i] != p2[i]) return false;
        return true;
    }

    public override bool Equals(object obj) => obj is StackBuffer2048 v && v.Equals(this);
    public override int GetHashCode()
    {
        var hash = new HashCode();
        var ptr = (long*)this.Pointer;
        var length = this.ByteSize / 8;
        for (var i = 0; i < length; ++i) hash.Add(ptr[i]);
        return hash.ToHashCode();
    }
}


計測コード
//計測するものに応じて宣言してください。
#define ALLOCATION
#define RANDOM

using System;
using System.Diagnostics;

class Program
{
    static void Main()
    {
        const int ALLOCATON_ROOP = 0xFFF;
        const int ACCESS_ROOP = 0xFFFFFF;
        const int LENGTH = 256;
        const int MASK = LENGTH - 1;

        var stopwatch = new Stopwatch();


        var stackarray = new StackArray2048<byte>();
        var stackarrayspan = stackarray.AsSpan();
        Span<byte> span = stackalloc byte[LENGTH];
        var array = new byte[LENGTH];


#if ALLOCATION
        Console.WriteLine($"Allocation({ALLOCATON_ROOP})");
        stopwatch.Restart();
        for (var j = 0; j < ALLOCATON_ROOP; ++j) stackarray = new StackArray2048<byte>();
        stopwatch.Stop();
        Console.WriteLine(stopwatch.Elapsed);


        stopwatch.Restart();
        for (var j = 0; j < ALLOCATON_ROOP; ++j) span = stackalloc byte[LENGTH];
        stopwatch.Stop();
        Console.WriteLine(stopwatch.Elapsed);


        stopwatch.Restart();
        for (var j = 0; j < ALLOCATON_ROOP; ++j) array = new byte[LENGTH];
        stopwatch.Stop();
        Console.WriteLine(stopwatch.Elapsed);
#elif RANDOM
        Console.WriteLine($"RandomAccess({ACCESS_ROOP})");
        var rand = new XorShiftShort();

        stopwatch.Restart();
        for (var j = ACCESS_ROOP; j > 0; --j)
        {
            rand.SetSeed((uint)j);
            for (var i = 0; i < stackarray.Length; ++i)
            {
                var index = (int)rand.Next() & MASK;
                stackarray[index] ^= stackarray[index];
            }
        }
        stopwatch.Stop();
        Console.WriteLine(stopwatch.Elapsed);

        stopwatch.Restart();
        for (var j = ACCESS_ROOP; j > 0; --j)
        {
            rand.SetSeed((uint)j);
            for (var i = 0; i < stackarrayspan.Length; ++i)
            {
                var index = (int)rand.Next() & MASK;
                stackarrayspan[index] ^= stackarrayspan[index];
            }
        }
        stopwatch.Stop();
        Console.WriteLine(stopwatch.Elapsed);

        stopwatch.Restart();
        for (var j = ACCESS_ROOP; j > 0; --j)
        {
            rand.SetSeed((uint)j);
            for (var i = 0; i < span.Length; ++i)
            {
                var index = (int)rand.Next() & MASK;
                span[index] ^= span[index];
            }
        }
        stopwatch.Stop();
        Console.WriteLine(stopwatch.Elapsed);

        stopwatch.Restart();
        for (var j = ACCESS_ROOP; j > 0; --j)
        {
            rand.SetSeed((uint)j);
            for (var i = 0; i < array.Length; ++i)
            {
                var index = (int)rand.Next() & MASK;
                array[index] ^= array[index];
            }
        }
        stopwatch.Stop();
        Console.WriteLine(stopwatch.Elapsed);

        stopwatch.Restart();
        for (var j = ACCESS_ROOP; j > 0; --j)
        {
            rand.SetSeed((uint)j);
            for (var i = 0; i < LENGTH; ++i)
            {
                var index = (int)rand.Next() & MASK;
            }
        }
        stopwatch.Stop();
        Console.WriteLine(stopwatch.Elapsed);
#else
        Console.WriteLine($"Access({ACCESS_ROOP})");
        stopwatch.Restart();
        for (var j = ACCESS_ROOP; j > 0; --j) for (var i = 0; i < stackarray.Length; ++i) stackarray[i] ^= stackarray[i];
        stopwatch.Stop();
        Console.WriteLine(stopwatch.Elapsed);


        stopwatch.Restart();
        for (var j = ACCESS_ROOP; j > 0; --j) for (var i = 0; i < stackarrayspan.Length; ++i) stackarrayspan[i] ^= stackarrayspan[i];
        stopwatch.Stop();
        Console.WriteLine(stopwatch.Elapsed);


        stopwatch.Restart();
        for (var j = ACCESS_ROOP; j > 0; --j) for (var i = 0; i < span.Length; ++i) span[i] ^= span[i];
        stopwatch.Stop();
        Console.WriteLine(stopwatch.Elapsed);


        stopwatch.Restart();
        for (var j = ACCESS_ROOP; j > 0; --j) for (var i = 0; i < array.Length; ++i) array[i] ^= array[i];
        stopwatch.Stop();
        Console.WriteLine(stopwatch.Elapsed);


        stopwatch.Restart();
        for (var j = ACCESS_ROOP; j > 0; --j) for (var i = 0; i < LENGTH; ++i) ;
        stopwatch.Stop();
        Console.WriteLine(stopwatch.Elapsed);
#endif

        Console.ReadLine();
    }
}


maemon
ゲームが好きな学生です。 初心者ですがよろしくお願いします。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした