【C#】 System.Span とパフォーマンスの話


みなさんはじめまして、会津ラボの阿部です。普段はバックエンドエンジニアをしています。 今回は C# の啓蒙活動を行おうと思います。

はじめに

C# もとい .NET Framework(v1.0、2002年1月) は .NET(v1.0、2016年6月) に名前が変わりました。よりアグレッシブに機能追加するよう舵切りがなされ、特にパフォーマンスが改善されています。今回は .NET のパフォーマンス改善の目玉である System.Span<T> に関する四方山話です。

Note
四方山話(よもやまばなし)
種々雑多な話。 世間話。 雑談。 よもの話。

C# は生産性を重視した言語であり、パフォーマンス改善の優先度はそれほど高くありませんでした。しかし C# コンパイラが C++ から C# で書かれるようになりパフォーマンスが重視されるようになります。つまり C# におけるパフォーマンス改善の流れは C# 開発チームの内需だったわけです。
その他、昨今のクラウドコンピューティングの隆盛によってパフォーマンスがよくないと開発言語として選ばれにくいという側面もあります(最近だと AOT も盛んです)。

Span<T> とは、要は配列

Span<T> は連続したメモリを表します。読み取り専用の ReadOnlySpan<T> もセットで存在します。配列の使いにくかった部分を改善した型です。

  • 擬似コード
// 中身はこんな感じ
ref readonly struct Span<T>
{
    // 対象の先頭のアドレス、void* みたいなもの
   readonly ref T pointer;

   // 長さ
   public readonly int Length { get; }
}
  • マネージ・アンマネージ配列(ポインタ)を一緒くたに扱える
// マネージ配列から
Span<int> arraySpan = new int [100];

unsafe
{
    void* GetPointer() => /* アンマネージな配列のポインタを返す */ null;

    // アンマネージポインタから
    // 画像処理でよく使う
    Span<int> pointerSpan = new Span<int>(GetPointer(), 100);

    // 構造体を byte 配列に読み替える
    // シリアル化でよく使う
    int num = 0;
    Span<byte> byteSpan = new Span<byte>(&num, 4);
}

// stackalloc から
Span<int> stackallocSpan = stackalloc int[100];

// string から
ReadOnlySpan<char> str = "hoge".AsSpan();
  • 指定された範囲を参照できる
ReadOnlySpan<char> slice = "hoge".AsSpan().Slice(1, 2); /* slice は "og" */
  • 配列のように操作できる
Span<string> span = new [] {"a", "b", "c", };
// インデックスにアクセス
span[1] = "d";

// ループ処理
foreach(var n in span)
{
    Console.Write(n);
}
// "adc" が出力される

後述のとおり Span<T> はパフォーマンス改善に繋がります。
しかしながら、リストやシーケンスを使う場面では System.Collections.Generic.IEnumerable<T> を使ったほうがクエリ並列処理イテレーターなど自由度が高く、共変性もあります。
結論として、Span<T> を使うのはライブラリ作成者が主体になりそうです。一方でライブラリ利用者は、Span<T> を意識せずパフォーマンス改善の恩恵を受けられます。

文字列を例に考える

Span<T> によるパフォーマンス改善の例として、文字列を見ていきましょう。

C# の文字列型(string)は不変な参照型です。詳細は省きますが、かなり特殊な型で内部的には読み取り専用の文字配列(char[])のようになっています。
これは参照先で書き換えられることがないためコピーを渡す必要がないこと、コードを簡潔にできることが利点としてありますが、意図しないオブジェクトの生成が起こりやすい欠点もあります。

var str = "abc";
// string は書き換えることができない
str[0] = 'b'; // エラー!

str = "a" + "b" + "c" + "d" + "e";
// str は "abcde" だが、"ab" "abc" "abcd" のオブジェクトが作られすぐにガベージになる

// ループでは非常に沢山のオブジェクトが作られ、破棄されがち
for(int i = 0; i < 100; i++) {
    str += i.ToString(); // ここで新しいオブジェクト
    str += "\n"; // ここで新しいオブジェクト
}

この問題は System.Text.StringBuilder を使うことで回避できます。

var builder = new System.Text.StringBuilder();

for(int i = 0; i < 100; i++) {
    builder.Append(i);
    builder.Append('\n');
}

var str = builder.ToString();

補完文字列(interpolated string)を使うことでも回避できます。

var now = DateTime.Now;
var str = $"今日は {now.Year} 年 {now.Month} 月 {now.Day} 日です。";

C# 10.0 から補完文字列はかなり効率的に処理できるようになり、System.Text.StringBuilder を使用するよりもガベージが出にくくなっています。
(C# 9.0 までの補間文字列はあまり効率的でなかった https://ufcpp.net/study/csharp/start/improvedinterpolatedstring/

System.IO.Path に追加されたオーバーロードも活用できます。

var path = @"C:\Directory\MyImage.jpg";

// ReadOnlySpan<char> で元の文字列メモリから範囲が参照されるためオブジェクトが生成されない
ReadOnlySpan<char> fileName = System.IO.Path.GetFileName(path.AsSpan());

Assert.True(fileName.SequenceEqual("MyImage.jpg"));

独自実装の BufferStringBuilder

以下に Span<T> のテクニックを使った、BufferStringBuilder を記載しました。使い方は解説を御覧ください。

Warning
以下のコードは十分な検証がなされていないため、製品コードには使用しないでください

BufferStringBuilder.cs
// <TargetFramework>net8.0</TargetFramework>
// <Nullable>enable</Nullable>
// <ImplicitUsings>enable</ImplicitUsings>
// <AllowUnsafeBlocks>true</AllowUnsafeBlocks>

namespace Lab;

/// <summary>
/// 内部バッファに Span を使用する StringBuilder
/// バッファ長を超えて Append すると新しいバッファを確保する(new char[this.Capacity * 2])
/// </summary>
public ref struct BufferStringBuilder
{
    private Span<char> _buffer;
    private int _length;

    /// <summary>
    /// 文字列長
    /// </summary>
    public readonly int Length => this._length;

    /// <summary>
    /// Span
    /// </summary>
    public readonly Span<char> Span => this._buffer.Slice(0, this._length);

    /// <summary>
    /// 内部配列長
    /// </summary>
    public readonly int Capacity => this._buffer.Length;

    private readonly Span<char> NextSpan => this._buffer.Slice(this._length);

    /// <summary>
    /// コンストラクタ
    /// 指定のスバンをバッファとして使用する
    /// </summary>
    /// <param name="buffer"></param>
    /// <param name="length"></param>
    /// <exception cref="ArgumentOutOfRangeException"></exception>
    public BufferStringBuilder(Span<char> buffer, int length = 0)
    {
        ArgumentOutOfRangeException.ThrowIfLessThan(length, 0);
        ArgumentOutOfRangeException.ThrowIfGreaterThan(length, buffer.Length);

        this._buffer = buffer;
        this._length = length;
    }

    private unsafe ref BufferStringBuilder RefThis
    {
        get
        {
            ref var ptr = ref this;
#pragma warning disable
            return ref ptr;
#pragma warning restore
        }
    }

    /// <summary>
    /// 文字列化
    /// </summary>
    /// <returns></returns>
    public readonly override string ToString() => this.Span.ToString();

    /// <summary>
    /// バッファをクリア
    /// </summary>
    /// <returns></returns>
    public ref BufferStringBuilder Clear()
    {
        this._length = 0;
        return ref this.RefThis;
    }

    /// <summary>
    /// 文字列化してバッファをクリア
    /// </summary>
    /// <returns></returns>
    public string ToStringAndClear()
    {
        var result = this.ToString();
        this.Clear();
        return result;
    }

    private void SizeUp(int next = 0)
    {
        var capacity = this.Capacity;
        if (capacity is 0)
            capacity = 10;
        else
            capacity *= 2;
        capacity = Math.Max(capacity, next);

        var oldBuffer = this._buffer;
        Span<char> newBuffer = new char[capacity];
        oldBuffer.Slice(0, this.Length).CopyTo(newBuffer);
        this._buffer = newBuffer;
    }

    /// <summary>
    /// 文字列を追加
    /// </summary>
    /// <param name="value"></param>
    /// <returns></returns>
    public ref BufferStringBuilder Append(ReadOnlySpan<char> value)
    {
        var max = this._length + value.Length;
        if (max > this.Capacity)
            this.SizeUp(max);
        value.CopyTo(this.NextSpan);
        this._length += value.Length;

        return ref RefThis;
    }

    /// <summary>
    /// 改行
    /// </summary>
    /// <returns></returns>
    public ref BufferStringBuilder AppendLine() => ref this.Append(Environment.NewLine);

    /// <summary>
    /// 末尾に文字列を追加して改行
    /// </summary>
    /// <param name="value"></param>
    /// <returns></returns>
    public ref BufferStringBuilder AppendLine(ReadOnlySpan<char> value) => ref this.Append(value).AppendLine();

    /// <summary>
    /// 末尾に文字を追加
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="value"></param>
    /// <param name="format"></param>
    /// <param name="provider"></param>
    /// <returns></returns>
    public ref BufferStringBuilder Append<T>(T value, ReadOnlySpan<char> format = default, IFormatProvider? provider = null) where T : ISpanFormattable
    {
        int count;
        while (!value.TryFormat(this.NextSpan, out count, format, provider))
            this.SizeUp();

        this._length += count;

        return ref RefThis;
    }

    /// <summary>
    /// 末尾に文字を追加して改行
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="value"></param>
    /// <param name="format"></param>
    /// <param name="provider"></param>
    /// <returns></returns>
    public ref BufferStringBuilder AppendLine<T>(T value, ReadOnlySpan<char> format = default, IFormatProvider? provider = null) where T : ISpanFormattable
    => ref this.Append<T>(value, format, provider).AppendLine();

    /// <summary>
    /// 指定位置に文字を追加
    /// </summary>
    /// <param name="index"></param>
    /// <param name="c"></param>
    /// <returns></returns>
    public ref BufferStringBuilder Insert(int index, char c)
    {
        ArgumentOutOfRangeException.ThrowIfLessThan(index, 0);
        var size = this._length;
        ArgumentOutOfRangeException.ThrowIfGreaterThanOrEqual(index, size);

        if (this.Length == this.Capacity)
        {
            this.SizeUp(size + 1);
        }

        this._length = size + 1;

        var destination = this.Span.Slice(index + 1);
        var source = this.Span.Slice(index, destination.Length);
        for (int n = 0; n < destination.Length; ++n)
            destination[n] = source[n];

        this._buffer[index] = c;

        return ref this.RefThis;
    }

    /// <summary>
    /// 指定位置に文字列を追加
    /// </summary>
    /// <param name="index"></param>
    /// <param name="span"></param>
    /// <returns></returns>
    public ref BufferStringBuilder InsertRange(int index, ReadOnlySpan<char> span)
    {
        ArgumentOutOfRangeException.ThrowIfLessThan(index, 0);
        ArgumentOutOfRangeException.ThrowIfGreaterThan(index, this._length);
        var size = this.Length;

        var newLength = this._length + span.Length;
        if (this.Capacity < newLength)
            this.SizeUp(newLength);

        this._length = newLength;
        var len = size - index;
        var source = this.Span.Slice(index, len);
        var destination = this.Span.Slice(index + span.Length, len);
        for (int n = source.Length - 1; n >= 0; --n)
            destination[n] = source[n];

        var newDestination = this.Span.Slice(index, span.Length);
        span.CopyTo(newDestination);

        return ref this.RefThis;
    }

    /// <summary>
    /// 指定位置の文字を削除
    /// </summary>
    /// <param name="index"></param>
    /// <returns></returns>
    /// <exception cref="ArgumentOutOfRangeException"></exception>
    public ref BufferStringBuilder RemoveAt(int index)
    {
        ArgumentOutOfRangeException.ThrowIfLessThan(index, 0);
        ArgumentOutOfRangeException.ThrowIfGreaterThanOrEqual(index, this._length);

        this._length--;
        if (index < this._length)
        {
            for (int n = index; n < this._length; ++n)
                this._buffer[n] = this._buffer[n + 1];
        }

        return ref this.RefThis;
    }

    /// <summary>
    /// 指定位置の文字列を削除
    /// </summary>
    /// <param name="index"></param>
    /// <param name="length"></param>
    /// <returns></returns>
    /// <exception cref="ArgumentOutOfRangeException"></exception>
    public ref BufferStringBuilder RemoveAtRange(int index, int length)
    {
        ArgumentOutOfRangeException.ThrowIfLessThan(index, 0);
        ArgumentOutOfRangeException.ThrowIfGreaterThan(index, this._length - 1);
        ArgumentOutOfRangeException.ThrowIfLessThan(length, 0);
        ArgumentOutOfRangeException.ThrowIfGreaterThan(index + length, this._length);

        var len = this._length - index - length;
        var items = this.Span;
        for (int n = 0; n < len; ++n)
        {
            var destinationIndex = index + n;
            var sourceIndex = destinationIndex + length;
            items[destinationIndex] = items[sourceIndex];
        }

        this._length -= length;
        return ref this.RefThis;
    }

    /// <summary>
    /// Span への暗黙の変換
    /// </summary>
    /// <param name="value"></param>
    public static implicit operator Span<char>(in BufferStringBuilder value) => value.Span;

    /// <summary>
    /// ReadOnlySpan への暗黙の変換
    /// </summary>
    /// <param name="value"></param>
    public static implicit operator ReadOnlySpan<char>(in BufferStringBuilder value) => value.Span;
}
BufferStringBuilder.Test.cs
// <PackageReference Include="xunit" Version="2.5.1-pre.20"/>
// <PackageReference Include="xunit.core" Version="2.5.1-pre.20"/>
// <PackageReference Include="xunit.runner.visualstudio" Version="2.5.1-pre.10"/>
// <PackageReference Include="Microsoft.NET.Test.Sdk" Version="17.8.0-preview-23371-04"/>

using Xunit;
namespace Lab;

public record BufferStringBuilderTest(Xunit.Abstractions.ITestOutputHelper Helper)
{
    [Fact]
    void HowToUse()
    {
        var builder = new BufferStringBuilder(stackalloc char[10]);
        builder.Append("PI=");
        // 数値型(System.ISpanFormattable)をサポート
        builder.Append(3.14);
        Assert.Equal("PI=3.14", builder.ToString());

        void NeedCharSpanMethod(Span<char> span) { }
        // Span<char> に暗黙的に変換される
        NeedCharSpanMethod(builder);

        // 内部バッファを超える場合、new char[] でヒープにバッファが作成される
        builder.Append("1234567890");

        // メソッド連結可能
        builder.Clear().Append("decimal:").Append(1.0M).ToString();

        Span<char> buffer = stackalloc char[] { 'a', 'b', 'c' };
        // 最初から "abc" が入っているバッファを使用
        builder = new BufferStringBuilder(buffer, buffer.Length);
        // "abc"
        var str = builder.ToString();
        Assert.Equal("abc", str);
    }

    [Fact]
    void TestConstructor()
    {
        Assert.Throws<ArgumentOutOfRangeException>(() => new BufferStringBuilder(stackalloc char[10], 11));
        Assert.Throws<ArgumentOutOfRangeException>(() => new BufferStringBuilder(stackalloc char[10], -1));

        Assert.Equal(0, new BufferStringBuilder(stackalloc char[10]).Length);
        Assert.Equal(3, new BufferStringBuilder(stackalloc char[3], 3).Length);
    }

    [Fact]
    void LengthSpanCapacity()
    {
        var builder = new BufferStringBuilder(stackalloc char[10]);
        Assert.Equal(0, builder.Length);
        Assert.Equal("", builder.Span.ToString());
        Assert.Equal(10, builder.Capacity);

        builder.Append("abc");
        Assert.Equal(3, builder.Length);
        Assert.Equal("abc", builder.Span.ToString());
        Assert.Equal(10, builder.Capacity);
    }

    [Fact]
    void Clear()
    {
        var builder = new BufferStringBuilder(stackalloc char[10]);
        builder.Append("abc");
        Assert.Equal("abc", builder.Span.ToString());
        builder.Clear();
        Assert.Equal("", builder.Span.ToString());
    }

    [Fact]
    void ToStringAndClear()
    {
        var builder = new BufferStringBuilder(stackalloc char[10]);
        builder.Append("abc");
        Assert.Equal("abc", builder.ToStringAndClear());
        Assert.Equal("", builder.Span.ToString());
    }

    [Fact]
    void BuilderToString()
    {
        var builder = new BufferStringBuilder(stackalloc char[10]);
        builder.Append("abc");
        Assert.Equal("abc", builder.ToString());
    }

    [Fact]
    void AppendString()
    {
        var builder = new BufferStringBuilder(stackalloc char[10]);
        builder.Append("abc");
        Assert.Equal("abc", builder.Span.ToString());
    }

    [Fact]
    void SizeUp()
    {
        var builder = new BufferStringBuilder(stackalloc char[3]);
        builder.Append("123");
        Assert.Equal("123", builder.Span.ToString());
        Assert.Equal(3, builder.Capacity);
        var capacity = builder.Capacity;

        builder.Append("4567");
        Assert.Equal("1234567", builder.Span.ToString());
        Assert.True(capacity < builder.Capacity);
    }

    [Fact]
    void AppendLine()
    {
        var builder = new BufferStringBuilder(stackalloc char[3]);
        builder.AppendLine();
        Assert.Equal(Environment.NewLine, builder.Span.ToString());
    }

    [Fact]
    void AppendLineString()
    {
        var builder = new BufferStringBuilder(stackalloc char[3]);
        builder.AppendLine("abc");
        Assert.Equal("abc" + Environment.NewLine, builder.Span.ToString());
    }

    [Fact]
    void AppendT()
    {
        var builder = new BufferStringBuilder(stackalloc char[3]);
        builder.Append("n=");
        builder.Append(123456789);
        Assert.Equal("n=123456789", builder.Span.ToString());
    }

    [Fact]
    void AppendLineT()
    {
        var builder = new BufferStringBuilder(stackalloc char[3]);
        builder.Append("n=");
        builder.AppendLine(123456789);
        Assert.Equal("n=123456789" + Environment.NewLine, builder.Span.ToString());
    }

    [Fact]
    void Insert()
    {
        Assert.Throws<ArgumentOutOfRangeException>(() => new BufferStringBuilder(default).Insert(-1, 'a'));
        Assert.Throws<ArgumentOutOfRangeException>(() => new BufferStringBuilder(stackalloc char[2], 2).Insert(5, 'a'));

        var builder = new BufferStringBuilder(stackalloc char[10]);
        builder.Append("13");
        builder.Insert(1, '2');
        Assert.Equal("123", builder.Span.ToString());
    }

    [Fact]
    void InsertRange()
    {
        Assert.Throws<ArgumentOutOfRangeException>(() => new BufferStringBuilder(default).InsertRange(-1, "123"));
        Assert.Throws<ArgumentOutOfRangeException>(() => new BufferStringBuilder(stackalloc char[2], 2).InsertRange(5, "123"));

        var builder = new BufferStringBuilder(stackalloc char[10]);
        builder.Append("123890");
        builder.InsertRange(3, "4567");
        Assert.Equal("1234567890", builder.Span.ToString());
    }

    [Fact]
    void RemoveAt()
    {
        Assert.Throws<ArgumentOutOfRangeException>(() => new BufferStringBuilder(default).RemoveAt(-1));
        Assert.Throws<ArgumentOutOfRangeException>(() => new BufferStringBuilder(default).RemoveAtRange(0, 1));

        var builder = new BufferStringBuilder(stackalloc char[10]);
        builder.Append("123");
        builder.RemoveAt(1);
        Assert.Equal("13", builder.Span.ToString());
    }

    [Fact]
    void RemoveAtRange()
    {
        Assert.Throws<ArgumentOutOfRangeException>(() => new BufferStringBuilder(default).RemoveAtRange(-1, 1));
        Assert.Throws<ArgumentOutOfRangeException>(() => new BufferStringBuilder(default).RemoveAtRange(1, 1));
        Assert.Throws<ArgumentOutOfRangeException>(() => new BufferStringBuilder(stackalloc char[10], 10).RemoveAtRange(0, 11));
        Assert.Throws<ArgumentOutOfRangeException>(() => new BufferStringBuilder(stackalloc char[10], 10).RemoveAtRange(10, 5));

        var builder = new BufferStringBuilder(stackalloc char[10]);
        builder.Append("123456");
        builder.RemoveAtRange(1, 2);
        Assert.Equal("1456", builder.Span.ToString());
    }

    [Fact]
    void ImplicitOperatorSpan()
    {
        var builder = new BufferStringBuilder(stackalloc char[10]);
        builder.Append("abc");
        Span<char> span = builder;
        Assert.Equal("abc", span.ToString());
    }

    [Fact]
    void ImplicitOperatorReadOnlySpan()
    {
        var builder = new BufferStringBuilder(stackalloc char[10]);
        builder.Append("abc");
        ReadOnlySpan<char> span = builder;
        Assert.Equal("abc", span.ToString());
    }

    [Fact]
    void RefThis()
    {
        var builder = new BufferStringBuilder(stackalloc char[10]);
        builder.Append("abc").Append("def");
        Assert.Equal("abcdef", builder.Span.ToString());
    }
}
解説

BufferStringBuilderref 構造体 です。コンストラクタに stackalloc char[N] を渡して使用します。

Note
stackalloc メモリをスタック上に確保するという珍しい機能です。
https://ufcpp.net/study/csharp/sp_unsafe.html#stackalloc

// 十分な長さのバッファを渡す
var builder = new BufferStringBuilder(stackalloc char[10]);
builder.Append("PI=");
// 数値型(System.ISpanFormattable)をサポート
builder.Append(3.14);

void NeedCharSpanMethod(Span<char> span) { }
// Span<char> に暗黙的に変換される
NeedCharSpanMethod(builder);

// 内部バッファを超える場合、new char[] でヒープにバッファが作成される
builder.Append("1234567890");

// メソッド連結可能
builder.Clear().Append("decimal:").Append(1.0M).ToString();

Span<char> buffer = stackalloc char[] { 'a', 'b', 'c' };
// 最初から "abc" が入っているバッファを使用
builder = new BufferStringBuilder(buffer, buffer.Length);
// "abc"
var str = builder.ToString();

.NET 6 から System.ISpanFormattable インターフェイスが導入されました。これは int.ToString(“000”) と似たもので、引数に渡した Span<char> に指定したフォーマットの文字列を出力するものです。戻り値に string を使用しないためガベージが発生しません。これによって数値を文字列化するときのガベージを抑制できます。

コードを読んでいくと Span<char> をジェネリックで Span<T> に置き換えた汎用的な BufferList<T> を作れそうです。それは別の機会に。

パフォーマンス比較

次の表は、単位時間に各テストが何回ループしたかを計測したパフォーマンス比較です。
スコアは高いほどパフォーマンスがよいです。
GC0 は、ガベージコレクション回数を表します(少ないほどパフォーマンスがよい)。

テスト名スコアスコア比GC0説明
AppendString9,211100.0%115+ による文字列連結
StringBuilder16,504179.2%6System.Text.StringBuilder
BufferStringBuilder19,697213.8%2独自実装の BufferStringBuilder
  • AppendString はスコアの低さに加え、GC 回数も多い。だがボトルネックというほど遅くもない
  • StringBuilder はスコアもよく、GC 回数も抑えられている。標準ライブラリで書けるため第一の選択肢と言える
  • BufferStringBuilder は最も良いパフォーマンスながら、コードの複雑さを考慮する必要がある。ToString() が不要な場面では GC 回数 0 になる
パフォーマンス比較に使用したテストコード
file class TestString {
    static Action AppendString() {
        return () => {
            string result = "";
            for(int n = 0; n < 100; ++n) {
                result += n.ToString("00");
                result += "\n";
            }

            result.ToString();
        };
    }

    static Action StringBuilder() {
        return () => {
            var sb = new System.Text.StringBuilder();
            for(int n = 0; n < 100; ++n) {
                sb.Append($"{n:00}\n");
            }

            sb.ToString();
        };
    }

    static Action BufferStringBuilder() {
        return () => {
            var sb = new Lab.BufferStringBuilder(stackalloc char[1000]);
            for(int n = 0; n < 100; ++n) {
                sb.Append(n, "00");
                sb.Append('\n');
            }

            sb.ToString();
        };
    }
}

おわりに

今回は C# のパフォーマンスに関する話題で Span<T> をご紹介しました。今後も面白そうな話題を取り上げていきたいと思います。

  • 構造体の参照渡しと隠れコピー(hidden copy
  • 構造体のボックス化・ボックス化解除
  • 無名メソッドのクロージャ生成パターン
  • ループとパフォーマンス
  • メソッドの仮想呼び出しを消し去る

Leave a Reply

Your email address will not be published. Required fields are marked *