C# で配列を Unshift しても大丈夫なのか

Unshift メソッドは Javascript 等に存在する、配列の全要素を一つ後ろにずらして先頭に新しい値を入れる処理です。List<T>.Insert(0, value) の配列版ですね。

C# には Unshift が存在しないので、同様の事を行おうとした場合は以下のようになるでしょう。（配列長は変えずに溢れたものは破棄）

array.AsSpan(0, Math.Min(consumedLength, array.Length - 1))
     .CopyTo(array.AsSpan(1));

array[0] = value;

Span<T>.CopyTo(...) だとオフセットを指定できないのでこんな感じになりますが、色々と気になりますね？？

• Span<T> 配列のオーバーラップ
  • 結果
  • パフォーマンス比較： 配列（Unshift）リスト（Insert）
• Unity の場合
• おまけ： Unity と IL2CPP と Span<T> で気になること
  • 範囲演算子
  • 番外：タプルを使った値のスワップ
    • ビット演算を使った値のスワップ
  • for 文ではスパンを使うと良いらしいぞ！
  • 配列なら foreach で良いらしいぞ！

Span<T> 配列のオーバーラップ

上記の例ではコピー元とコピー先の配列が同じモノですね。どうなるんでしょうか。

スパンの処理はベクトル化（と言って良いのか？）されていて高速！ ということで、例えば

var array = new short[]{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

がある場合、配列要素を nint == IntPtr == CPU のビット数ずつ処理することが期待されるわけです。64ビット CPU の場合は

• 0, 1, 2, 3（long）と 4, 5, 6, 7（long）と残りの 8, 9（short x2）ですね。

４要素毎に一つずつずらすと、、、

• 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
• 0, 0, 1, 2, 3, 5, 6, 7, 8, 9
• 0, 0, 1, 2, 3, 3, 5, 6, 7, 9
• 0, 0, 1, 2, 3, 3, 5, 6, 7, 7

て、コト！？

^{※１要素ずつの場合も同じ話でその場合は全て 0 になる}

結果

そんなことはないです。C# は以下の通り、オーバーラップを考慮して処理してくれます。（ちゃんと 0, 0, 1 ~ 8 になります）

Array.CopyTo と違って Span.CopyTo にはコピー先のオフセットを指定できないので不安がありましたが、使っても大丈夫です。イイですね！

スパンで高速に処理したい的な意味では、ネイティブ側が何をやってるか不明なのでなんとも。
オフセットが正の場合は配列の後ろから順に nint 毎にコピー、ってしてくれていると良いんだけど、そういうパッと思い付くレベルの最適化はネイティブ側でも当然に行われていそうではある。
簡単なパフォーマンス比較は次項に。

public void CopyTo(Span<T> destination)
{
    // Using "if (!TryCopyTo(...))" results in two branches: one for the length
    // check, and one for the result of TryCopyTo. Since these checks are equivalent,
    // we can optimize by performing the check once ourselves then calling Memmove directly.

    if ((uint)_length <= (uint)destination.Length)
    {
        Buffer.Memmove(ref destination._reference, ref _reference, (uint)_length);
    }
    else
    {
        ThrowHelper.ThrowArgumentException_DestinationTooShort();
    }
}

👇 Buffer.Memmove

[Intrinsic] // Unrolled for small constant lengths
internal static unsafe void Memmove(ref byte dest, ref byte src, nuint len)
{
    // P/Invoke into the native version when the buffers are overlapping.
    if (((nuint)(nint)Unsafe.ByteOffset(ref src, ref dest) < len) || ((nuint)(nint)Unsafe.ByteOffset(ref dest, ref src) < len))
    {
        goto BuffersOverlap;
    }

    // Use "(IntPtr)(nint)len" to avoid overflow checking on the explicit cast to IntPtr

    ref byte srcEnd = ref Unsafe.Add(ref src, (IntPtr)(nint)len);
    ref byte destEnd = ref Unsafe.Add(ref dest, (IntPtr)(nint)len);

    if (len <= 16)
        goto MCPY02;
    if (len > 64)
        goto MCPY05;

MCPY00:
    ...
    ...

パフォーマンス比較： 配列（Unshift）リスト（Insert）

配列（Span）とリストでの Unshift（配列長は維持）のパフォーマンスを比較してみます。

結果的にはリストの方が速いですね。構造的にも前後や先頭・末尾の参照先を書き換えるだけのリストに比べて、配列要素全てをアサインしなおすので当然ではありそうです。

32バイトが1,000要素（32KB） x 一千万 = 320,000,000,000（320GB）
メモリの読み書き速度はざっくり 10GB/s として、配列のコピーはなんか早い。
逆にリストはなんか遅くない？、っていう。

追記： LinkedList<T> を使ったら正に上に書いた通りの処理が行われて、10,000 要素に対して１億回 Unshift を行っても４秒で終わる。

一千万回実行	Type	10 items	100 items	1,000 items
Span.CopyTo	int	0.33s	0.37s	0.71s
List.RemoveAt+Insert	int	0.30s	0.31s	0.69s
Span.CopyTo	long	0.36s	0.42s	1.20s
List.RemoveAt+Insert	long	0.34s	0.39s	1.13s
Span.CopyTo	string	0.39s	0.53s	2.66s
List.RemoveAt+Insert	string	0.32s	0.50s	2.62s
Span.CopyTo	32 bytes	0.41s	0.66s	3.80s
List.RemoveAt+Insert	32 bytes	0.36s	0.61s	3.75s

とはいえサイズの大きな構造体だとかなりの差が出そうだと思ったんですが、そんなこともないですね。構造上の差がずっと維持され続けている感じです。

リストが値そのものと、加えてそのコンテナオブジェクトを保持することを考えたら単純でメモリー消費が少なそうな配列の Unshift で良いかもですね。

👇 確認に使ったコード 👉 実行環境： https://dotnetfiddle.net/

using System;
using System.Collections.Generic;

class Program
{
	struct ThirtyTwo {
		public int A;
		public int B;
		public long C;
		public long D;
		public short E;
		public short F;
		public short G;
		public short H;
	}
	
    static void Main()
    {
		var array = new ThirtyTwo[10];
		for (int i = 0; i < array.Length; i++)
		{
			array[i] = new();
		}
		var list = new List<ThirtyTwo>(array);

		for (int i = 0; i < 10_000_000; i++)
		{
			array.AsSpan(0, array.Length - 1).CopyTo(array.AsSpan(1));
			array[0] = new();

			//list.RemoveAt(list.Count - 1);
			//list.Insert(0, new());
		}
	}
}

Unity の場合

Unity の使っている .NET Standard 2.1 と C# オリジナルのライブラリは 微妙に違う（Unity 2022 の時点で C# 8.0 をベースに 9.0 の一部機能を先取り）ということで、Unity が実際に使用・生成する IL コードがどうなっているのかデコンパイルして確認してみます。（Unity 2021.3 で確認）

void Start()
{
    short[] array = new short[]{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    array.AsSpan(0, array.Length - 1).CopyTo(array.AsSpan(1));
    Debug.WriteLine(string.Join(", ", array) );
}

// 👇 AOT 最適化後の C# コード

private void Start()
{
    short[] values = new short[10]
    {
        (short) 0,
        (short) 1,
        (short) 2,
        (short) 3,
        (short) 4,
        (short) 5,
        (short) 6,
        (short) 7,
        (short) 8,
        (short) 9
    };
    MemoryExtensions.AsSpan<short>(values, 0, values.Length - 1).CopyTo(MemoryExtensions.AsSpan<short>(values, 1));
    
    Debug.WriteLine(string.Join<short>(", ", (IEnumerable<short>) values));
}

👇 オーバーラップの確認など行い MemoryExtensions が最終的に辿り着く先はコチラ

なんで src と dest のアドレスを同じにしてんだ、と思ったら値のコピー。[0] 付けろ

internal static unsafe void Memcpy(byte* dest, byte* src, int len)
{
    // 編注：32バイト以上はネイティブへ（64bitでビルドしてるのに？
    if (len > 32)
    {
        Buffer.InternalMemcpy(dest, src, len);
    }
    else
    {
        // 編注：どちらかまたは両方のアドレスが４で割り切れない
        if ((((int) dest | (int) src) & 3) != 0)
        {
            // 編注：どちらのアドレスも奇数で len が１以上の場合
            if (((int) dest & 1) != 0 && ((int) src & 1) != 0 && len >= 1)
            {
                *dest = *src;
                ++dest;
                ++src;
                --len;
            }
            // 編注：偶数にそろえたアドレスがどちらも４バイト境界に揃っておらず len が２以上の場合
            if (((int) dest & 2) != 0 && ((int) src & 2) != 0 && len >= 2)
            {
                *(short*) dest = *(short*) src;
                dest += 2;
                src += 2;
                len -= 2;
            }
            // 編注：どちらのアドレスも奇数
            if ((((int) dest | (int) src) & 1) != 0)
            {
                Buffer.memcpy1(dest, src, len);
                return;
            }
            // 編注：どちらのアドレスも４バイト境界に揃っていない
            if ((((int) dest | (int) src) & 2) != 0)
            {
                Buffer.memcpy2(dest, src, len);
                return;
            }
        }
        Buffer.memcpy4(dest, src, len);
    }
}

👇 64-bit でビルドしたけど short の配列を使ったせいか、なんか思ったのと違う。。。64ビット版が無い。全体的に 32 ビットをターゲットにしたようなコードが生成されているような？ memcpy1 は long としてドカッとコピーじゃダメなのか？

ともあれ結果は問題なし。

private static unsafe void memcpy1(byte* dest, byte* src, int size)
{
    for (; size >= 8; size -= 8)
    {
        *dest = *src;
        dest[1] = src[1];
        dest[2] = src[2];
        dest[3] = src[3];
        dest[4] = src[4];
        dest[5] = src[5];
        dest[6] = src[6];
        dest[7] = src[7];
        dest += 8;
        src += 8;
    }
    for (; size >= 2; size -= 2)
    {
        *dest = *src;
        dest[1] = src[1];
        dest += 2;
        src += 2;
    }
    if (size <= 0)
        return;
    *dest = *src;
}

internal static unsafe void memcpy2(byte* dest, byte* src, int size)
{
    for (; size >= 8; size -= 8)
    {
        *(short*) dest = *(short*) src;
        *(short*) (dest + 2) = *(short*) (src + 2);
        *(short*) (dest + (new IntPtr(2) * 2).ToInt64()) = *(short*) (src + (new IntPtr(2) * 2).ToInt64());
        *(short*) (dest + (new IntPtr(3) * 2).ToInt64()) = *(short*) (src + (new IntPtr(3) * 2).ToInt64());
        dest += 8;
        src += 8;
    }
    for (; size >= 2; size -= 2)
    {
        *(short*) dest = *(short*) src;
        dest += 2;
        src += 2;
    }
    if (size <= 0)
        return;
    *dest = *src;
}

internal static unsafe void memcpy4(byte* dest, byte* src, int size)
{
    for (; size >= 16; size -= 16)
    {
        *(int*) dest = *(int*) src;
        *(int*) (dest + 4) = *(int*) (src + 4);
        *(int*) (dest + (new IntPtr(2) * 4).ToInt64()) = *(int*) (src + (new IntPtr(2) * 4).ToInt64());
        *(int*) (dest + (new IntPtr(3) * 4).ToInt64()) = *(int*) (src + (new IntPtr(3) * 4).ToInt64());
        dest += 16;
        src += 16;
    }
    for (; size >= 4; size -= 4)
    {
        *(int*) dest = *(int*) src;
        dest += 4;
        src += 4;
    }
    for (; size > 0; --size)
    {
        *dest = *src;
        ++dest;
        ++src;
    }
}

おまけ： Unity と IL2CPP と Span<T> で気になること

ついでに Span<T> で気になるコトもこの機会に見てみます。

JetBrains dotPeek はデフォルト設定のままだとデコンパイル結果ではなくオリジナルのソースコードを表示してしまうし、以下に示すような余計な改変も加えてデコンパイル結果を表示するなど、ちょっと「賢すぎる」きらいがあります。
他のデコンパイラの方が IL 中間言語を素直に C# コードに変換してくれるので、Unity が実際に書き出す IL コードを確認する、IL2CPP が何を元に C++ コードを生成しているかを確認する、という目的なら dotPeek は使わない方が良さそう。

範囲演算子

以下のようなコード、Slice を使うか範囲演算子を使うか（提案で出てきますね）ですが、範囲演算子は Range 構造体を使うということで、Slice のが良いんじゃないか？ と思えます。

Debug.Log(array.AsSpan().Slice(0, 3).ToArray());

Debug.Log(array.AsSpan()[..3].ToArray());

上記のコードは最終的に AOT 最適化された結果、以下のように Slice を使うコードに変換されるので、 Range 構造体は生成されません。どっちも変わんないですね。

Range 型は開発環境での構文チェックの為に便宜上存在する感じでしょうか。

Span<short> span = MemoryExtensions.AsSpan<short>(values);
span = span.Slice(0, 3);
Debug.Log((object) span.ToArray());

// 範囲演算子の方は謎の減算はあるが span の確保はしない
Debug.Log((object) MemoryExtensions.AsSpan<short>(values).Slice(0, 3 - 0).ToArray());

つまり、範囲演算子は使った方がイイということですね！ でも範囲でマイナスを使っている場合は別です。

// マイナス（[..^3]）を使った場合は span + int 確保、両方マイナスだと span + int x2 確保
Span<short> span1 = MemoryExtensions.AsSpan<short>(values);
int num1 = span1.Length - 3 - 0;
Debug.Log((object) span1.Slice(0, num1).ToArray());

範囲演算子は後ろからカウントしたい時だけで、普段使いは Slice の方が単純でイイかもですね。

^{ちなみに C# 再変換コードで変数を確保していなくても、ILコード的にスタックは同じ数だけ使ってる感じがあるから気にしなくても良いかも。}

番外：タプルを使った値のスワップ

提案されること繋がりで、ずっと気になっていた値のスワップも見てみます。

var tmp = array[1];
array[1] = array[0];
array[0] = tmp;

// 👇 提案内容（タプルに包んで Deconstruct

(array[0], array[1]) = (array[1], array[0]);

これは従わないほうが良さそうです。

short num1 = values[1];
values[1] = values[0];
values[0] = num1;

// なんで提案した？？
ref short local1 = ref values[0];
ref short local2 = ref values[1];
short num2 = values[1];
short num3 = values[0];
local1 = num2;
int num4 = (int) num3;
local2 = (short) num4;

ビット演算を使った値のスワップ

分かりそうで分からないビット演算を使った値のスワップ。こっちは特に提案されないですが見てみます。

array[0] ^= array[1];  // var diff = a ^ b;  // a と b のビット毎の差異を求める
array[1] ^= array[0];  // b = b ^ diff;      // b の差異を解消すると a になる
array[0] ^= array[1];  // a = a ^ diff;      // a の差異を解消すると b になる

特に AOT での最適化は行われませんね。

IL コード的には一時変数に退避してアサインし直すのとほぼ変わんないですね。ビット演算の方が気持ち文面が長いか？

CPU 命令レベルだと XOR のが速い説があるけど、気にしてもしょうがないレベルですね。

for 文ではスパンを使うと良いらしいぞ！

範囲チェックが行われなくなるらしいです。i = 0; i < array.Length でも範囲チェックが無くなると言われています。

デコンパイルして見たところ、そもそも境界チェックなどしていないように見えます。IL コード的にも何もしていないように見受けられるので、上記の最適化は「JIT 時」の話で IL2CPP 目線では無意味、Mono バックエンドでビルドしているなら、、、という感じでしょう。

var span = array.AsSpan(3, 3);
for (int i = 0; i < span.Length; i++)
{
    Debug.Log(span[i]);
}

for (int i = 3; i < 7; i++)
{
    Debug.Log(array[i]);
}

👇

Span<short> span3 = MemoryExtensions.AsSpan<short>(values, 3, 3);
for (int index = 0; index < span3.Length; ++index)
    Debug.Log((object) span3[index]);

for (int index = 3; index < 7; ++index)
    Debug.Log((object) values[index]);

C++ コードを見ると span を使用するしないに関わらず、常にヌルェックを挟んでいる節があるので span 化するぐらいなら配列に直でアクセスの方がイイんでは？

配列なら foreach で良いらしいぞ！

これは JIT 時最適化ですねー、と思ったら、、、

foreach (var v in array)
    Debug.Log(v);

var list = new List<short>(array);
foreach (var v in list)
    Debug.Log(v);

👇

foreach (int message in numArray)   // IL コードでは想定通り for 文になっているのに、、、
    Debug.Log((object) (short) message);

foreach (int message in new List<short>((IEnumerable<short>) numArray))
    Debug.Log((object) (short) message);

dotPeek が気を利かせて foreach を復元してしまっているだけっぽいので、言われている通り foreach して問題なさそう。

デコンパイラに for -> foreach 変換なんてもの求めてる人間は果たしてどの位いるのだろうか。。。

オリジナルのコードでは array は short[] なんですけどね。nint なら分かるけど何故 int。

なんか dotPeek は使いどころが分からないデコンパイラですね。その辺から拾ってきたアセンブリから可能な限りオリジナルを再現するべく改変、加えてプラットフォームで最適な型を使う（でも nint を使わず 32 ビットターゲット決め打ち？）どういうこと？

Span<T>.CopyTo が辿り着く unsafe コード内でもアドレスを int にキャストしてるけど、64bit 環境だとオーバーフローしないか？ コード的にはアライメントを確認するだけだから問題はないんだけども。。。

変に改変したデコンパイル結果を表示することにユーザーはキレないのかな？？ それとも IL コードを読めるようになるべきって話？

ちなみに dnSpy だと適切に for 文に展開されて、型も自然。イイね！

--

AOT 最適化後の IL コードを C# に再変換したモノを手軽に確認したいですね。

JetBrains 系のエディターはその辺手厚そうだけど、AndroidStudio を使ってると感じる何とも言えない手に馴染まない感、、、Kotlin だとスコープ内の this、it（イテレーターの it だと思ってたけど形式主語の it っぽい） の内容を表示してくれるのが分かりやすくて良いけど、C# はスコープ関数が無いから意味なしだしなー。

--

以上です。お疲れ様でした。