【C#】ループの最適化手法 ③Span<T>編 ～配列をSpan<T>にするだけで早い～

はじめに

この記事は 配列編、List編の続きです。最初から読まれることをおすすめします。

Span<T> の謎

さて、前回 Span<T> 化した List<T> が配列より早いという不思議な結果を出してしまったので、その謎を研究していきます。
まず、ベンチマーク結果を確認しましょう。特に配列の方に関しては、何か変なことをしたわけではなく、単に Span<int> に一回キャストしただけです。

public bool SpanArray()
{
    return SpanInternal(array);
}

public bool SpanList()
{
    return SpanInternal(System.Runtime.InteropServices.CollectionsMarshal.AsSpan(list));
}

private static bool SpanInternal(Span<int> span)
{
    for (var i = 0; i < span.Length; i++)
    {
        if (span[i] == target)
        {
            return true;
        }
    }
    return false;
}

public unsafe bool PtrArray()
{
    fixed (int* ptr = array)
    {
        for (var i = 0; i < testSize; i++)
        {
            if (ptr[i] == target)
            {
                return true;
            }
        }
    }
    return false;
}

Method	Mean	Error	StdDev
ArrayFor	530.3 μs	7.36 μs	6.89 μs
ListFor	625.0 μs	10.18 μs	9.03 μs
SpanArray	294.9 μs	5.61 μs	5.25 μs
SpanList	289.3 μs	0.83 μs	0.65 μs
PtrArray	293.7 μs	5.45 μs	5.10 μs

結果のポイントは

• Span にするだけで早い。それも結構大差で早い。
• Span と ポインタで同じ速度。

というところです。

これは正直なところ、全く予想していなかった結果です。境界値チェックが絡むシーンで Span<T> が有効であることは周知の事実(?)だとしても、もともと境界値チェックが最適化で消失する配列よりも Span<T> が早いため、境界値チェック最適化以外の別の理由が潜んでいることになります。

逆アセンブルと 0x10

ひとまず、Span<T> の場合の逆アセンブル結果を見てみましょう。

Benchmark.SpanInternal (Span )

L0000    mov    rax, [rdx]
L0003    mov    edx, [rdx+8]
L0006    xor    ecx, ecx
L0008    test    edx, edx
L000a    jle    short L001f
L000c    movsxd    r8, ecx
L000f    cmp    dword ptr [rax+r8*4], 0xf423f
L0017    je    short L0022
L0019    inc    ecx
L001b    cmp    ecx, edx
L001d    jl    short L000c
L001f    xor    eax, eax
L0021    ret    
L0022    mov    eax, 1
L0027    ret    

かなりシンプルなアセンブリが生えています。しかし、配列のときも同じくらいシンプルだった気がします。比較してみましょう。
比較のため、配列でもループ処理だけを関数に切り出して逆アセンブルします。

Benchmark.ArrayForInternal (Int32[])

L0000    xor    eax, eax
L0002    mov    ecx, [rdx+8]
L0005    test    ecx, ecx
L0007    jle    short L001d
L0009    movsxd    r8, eax
L000c    cmp    dword ptr [rdx+r8*4+0x10], 0xf423f
L0015    je    short L0020
L0017    inc    eax
L0019    cmp    ecx, eax
L001b    jg    short L0009
L001d    xor    eax, eax
L001f    ret    
L0020    mov    eax, 1
L0025    ret    

と、そっくりです。ループ本体に限ってはほぼ同じです。しかしただ一点、cmp 命令のオペランドの 0x10 の有無が異なります。
逆にこれ以外の違いはありません。

この 0x10 の正体にはおよそ検討が付きます。64ビット環境での配列の先頭には、仮想関数テーブルへのポインタ(8byte)と、配列長(4byteを超えることはないが、領域は8byte)が記録されています。
この辺は以前の記事に詳しいです(宣伝)(二回目)

したがって、配列オブジェクトのインスタンス(ポインタ)から、配列の中身までにはちょうど 0x10 byteのオフセットがあります。
一方、Span<T> は、長さを構造体側で保持するため、中身の開始位置のアドレスそのものを保持しています。ゆえにオフセットは不要です。

このような構造の違いにより、コンパイル結果に差が生じたのだと考えられます。
なお、ポインタを使用した場合も 0x10 のオフセットは発生しません。序盤の fixed 部分のコンパイル結果で少し見にくいですが、ループの本体は Span<T> の場合と同じアセンブリです。

Benchmark.PtrArray ()

L0000    sub    rsp, 0x28
L0004    xor    eax, eax
L0006    mov    [rsp+0x20], rax
L000b    mov    rcx, 0x7ff847e3cea8
L0015    mov    edx, 1
L001a    call    0x00007ff8a709dae0
L001f    mov    rax, [rax]
L0022    mov    [rsp+0x20], rax
L0027    test    rax, rax
L002a    je    short L0037
L002c    mov    rax, [rsp+0x20]
L0031    cmp    dword ptr [rax+8], 0
L0035    jne    short L003b
L0037    xor    eax, eax
L0039    jmp    short L004f
L003b    mov    rax, [rsp+0x20]
L0040    cmp    dword ptr [rax+8], 0
L0044    jbe    short L008c
L0046    mov    rax, [rsp+0x20]
L004b    add    rax, 0x10
L004f    xor    edx, edx
L0051    nop    [rax]
L0058    nop    [rax+rax]
L0060    movsxd    rcx, edx
L0063    cmp    dword ptr [rax+rcx*4], 0xf423f
L006a    je    short L0082
L006c    inc    edx
L006e    cmp    edx, 0xf4240
L0074    jl    short L0060
L0076    xor    eax, eax
L0078    mov    [rsp+0x20], rax
L007d    add    rsp, 0x28
L0081    ret    
L0082    mov    eax, 1
L0087    add    rsp, 0x28
L008b    ret    
L008c    call    0x00007ff8a709f120
L0091    int3    

本当に 0x10 だけ？

しかし、この 0x10 のアドレスのオフセット計算だけで 1.6倍もパフォーマンス差がつくのかに関しては依然疑問が残ります。
こんな記事を書いておきながら申し訳ないのですが、この疑問は依然疑問のままです。考えられる他の原因として

• Span だと、GC用の参照管理のコストが低い可能性
• オペランドに 0x10 が生えたことで、アセンブリのアラインメントが崩れ実行効率が落ちた可能性

などなど考えられるのですが、現状結論は不明です。詳しい人がいたら教えてください。

Span と境界値

さて、話を少し戻しましょう。Span<T> を使用することで、境界値チェックのないアセンブリを生成することができました。
Span<T> を使用すると、for (var i = 0; i < span.Length; i++) の最適化が入る形式のループで処理することができるのです。
これは、一部分だけを舐める場合でも、予め適切なサイズの Span<T> にスライスしておけば可能です。

ということで、境界値チェックの最適化をランタイム側の改修コストが少ない形で、配列以外の型に適用することができるのです。
その型には、List<T> の他、配列の部分ビューや読み取り専用形などが含まれます。
ref struct ゆえの制約があり、使用者側のスキルが問われるところではありますが、ループ最適化の力強い道具であることは間違いないです。

Interface抽象化

ところで、パフォーマンスを抜きにすれば、できるだけ IEnumerable<T> などの緩いインターフェイスで受けて、抽象化を掛けてあげたいところです。
しかしながら、Span<T> と IEnumerable<T> には 15倍程度のパフォーマンス差があり、これはかなり大きいです。
この状況下でのベストプラクティスを考えてみます。

まず、パフォーマンスの確保が必須である場合は、従来はこのシーンでは配列を要求していましたが、可能ならば(=フィールドなどで保持しなくていいなら)、 Span<T> を要求するのがよいでしょう。
そうすることで、 List<T> なども渡すことが、「高パフォーマンスなコレクション」という観点で、Span<T> は IEnumerable<T> 並みの広範囲な抽象化として機能するはずです。

一方、パフォーマンスが必須ではないが、可能ならパフォーマンスを上げたい場合を考えます。これは、その代表である Linq の実装にならうのがよさそうです。
Linq のメソッドの中には、IEnumerable<T> を取るけれど、型判定を掛けて特定の型なら特殊化して最適化するものが少なくありません。

今回の場合は、

public static bool IEnumerableIs(IEnumerable<int> arg)
{
    if (arg is int[] arr)
    {
        return SpanInternal(arr);
    }
    if (arg is List<int> list)
    {
        return SpanInternal(System.Runtime.InteropServices.CollectionsMarshal.AsSpan(list));
    }

    // default
    foreach (var n in arg)
    {
        if (n == target)
        {
            return true;
        }
    }
    return false;
}

のように、特定の型かどうか見てしまうのも一つの策です。動的型判定のコストはリフレクション類の中ではかなり低いですし、Span<T> 化に成功すればかなりの恩恵が受けられます。そして現実的に、C# での IEnumerable<T> の中身は大抵、配列・リスト・(Tがcharなら)string・イテレーター・Linqクエリのどれかです。
ただし、この最適化は利用者側から見えないことに注意してください。利用者に意識してもらう必要があるなら、やはり Span<T> で受けるのがいいでしょう。

最後に、params(可変長引数) 問題です。paramsで受け取る引数の型は、いまだに配列に限定されており、要望は上がっているようですが Span<T> が許可される具体的な見込みはありません。そもそもただの糖衣構文ですし、使わなくていいというのが本音なのかもしれません。

結局専用メソッドが早い

なお、今回のベンチマークで題材としている「要素の検索」に限って言えば、専用のメソッドがあります。Contains とか IndexOf ですね。
ループの汎用的な最適化手法という今回の題材からは少しそれますが、最終的にこれが一番早いので、存在するなら専用のメソッドを使うのがベストプラクティスです。

Method	Mean	Error	StdDev
ArrayFor	530.3 μs	7.36 μs	6.89 μs
ListFor	625.0 μs	10.18 μs	9.03 μs
SpanArray	294.9 μs	5.61 μs	5.25 μs
SpanList	289.3 μs	0.83 μs	0.65 μs
ArrayIndexof	173.2 μs	1.10 μs	0.86 μs
ListContains	175.3 μs	2.82 μs	2.64 μs
ArrayLinq	175.7 μs	3.38 μs	3.16 μs
ListLinq	162.7 μs	1.38 μs	1.23 μs

と、Contains や IndexOf 、そしてそれらの呼び出しに特殊化される Linq が一番早いです。いかにも C# らしい結論ですね。
これらの、検索特化メソッドは辿っていくと最終的に以下のメソッドに帰結します。

internal static unsafe int IndexOfValueType<T>(ref T searchSpace, T value, int length) where T : struct, IEquatable<T>
{
    Debug.Assert(length >= 0);

    nint index = 0; // Use nint for arithmetic to avoid unnecessary 64->32->64 truncations
    if (Vector.IsHardwareAccelerated && Vector<T>.IsSupported && (Vector<T>.Count * 2) <= length)
    {
        Vector<T> valueVector = new Vector<T>(value);
        Vector<T> compareVector;
        Vector<T> matchVector;
        if ((uint)length % (uint)Vector<T>.Count != 0)
        {
            // Number of elements is not a multiple of Vector<T>.Count, so do one
            // check and shift only enough for the remaining set to be a multiple
            // of Vector<T>.Count.
            compareVector = Unsafe.As<T, Vector<T>>(ref Unsafe.Add(ref searchSpace, index));
            matchVector = Vector.Equals(valueVector, compareVector);
            if (matchVector != Vector<T>.Zero)
            {
                goto VectorMatch;
            }
            index += length % Vector<T>.Count;
            length -= length % Vector<T>.Count;
        }
        while (length > 0)
        {
            compareVector = Unsafe.As<T, Vector<T>>(ref Unsafe.Add(ref searchSpace, index));
            matchVector = Vector.Equals(valueVector, compareVector);
            if (matchVector != Vector<T>.Zero)
            {
                goto VectorMatch;
            }
            index += Vector<T>.Count;
            length -= Vector<T>.Count;
        }
        goto NotFound;
    VectorMatch:
        for (int i = 0; i < Vector<T>.Count; i++)
            if (compareVector[i].Equals(value))
                return (int)(index + i);
    }

    while (length >= 8)
    {
        if (value.Equals(Unsafe.Add(ref searchSpace, index)))
            goto Found;
        if (value.Equals(Unsafe.Add(ref searchSpace, index + 1)))
            goto Found1;
        if (value.Equals(Unsafe.Add(ref searchSpace, index + 2)))
            goto Found2;
        if (value.Equals(Unsafe.Add(ref searchSpace, index + 3)))
            goto Found3;
        if (value.Equals(Unsafe.Add(ref searchSpace, index + 4)))
            goto Found4;
        if (value.Equals(Unsafe.Add(ref searchSpace, index + 5)))
            goto Found5;
        if (value.Equals(Unsafe.Add(ref searchSpace, index + 6)))
            goto Found6;
        if (value.Equals(Unsafe.Add(ref searchSpace, index + 7)))
            goto Found7;

        length -= 8;
        index += 8;
    }

    while (length >= 4)
    {
        if (value.Equals(Unsafe.Add(ref searchSpace, index)))
            goto Found;
        if (value.Equals(Unsafe.Add(ref searchSpace, index + 1)))
            goto Found1;
        if (value.Equals(Unsafe.Add(ref searchSpace, index + 2)))
            goto Found2;
        if (value.Equals(Unsafe.Add(ref searchSpace, index + 3)))
            goto Found3;

        length -= 4;
        index += 4;
    }

    while (length > 0)
    {
        if (value.Equals(Unsafe.Add(ref searchSpace, index)))
            goto Found;

        index += 1;
        length--;
    }
NotFound:
    return -1;

Found: // Workaround for https://github.com/dotnet/runtime/issues/8795
    return (int)index;
Found1:
    return (int)(index + 1);
Found2:
    return (int)(index + 2);
Found3:
    return (int)(index + 3);
Found4:
    return (int)(index + 4);
Found5:
    return (int)(index + 5);
Found6:
    return (int)(index + 6);
Found7:
    return (int)(index + 7);
}

現代の一般的なCPUで実行している場合、int へのベクトル演算がサポートされますから、最初の if 文の内部の処理が使用されます。
そして、ベクトル演算を使用した検索処理が入ります。最新のCPUで実行していれば、一度に8個の int が比較されるでしょう。
最速であった Span<T> によるループでさえ、結局ループである以上 int を1個ずつちまちま取り出すことになるため、ベクトル演算には勝てません。

ベクトル演算の話は過去記事でネタにしているのでよければ見てください(宣伝)

ループは抽象的であるということ

ループは、とても抽象的で汎用的な手法です。ゆえに、「何のための」ループなのかは、コードからは自明ではありません。
目的がより具体的であるほど、ベクトル演算のように、使える最適化手法が広がり、パフォーマンスが改善する場合もあります。
何より、抽象的なループは、目的が自明な専用メソッドや Linq より可読性が悪いケースが大半です。
そもそもループを回避できないか考えてみるのが、C#er らしい発想でしょう。