ZString – Unity/.NET CoreにおけるゼロアロケーションのC#文字列生成

Posted on
このエントリーをはてなブックマークに追加

Cy#の河合です。今回、文字列生成におけるメモリアロケーションをゼロにする「ZString」というライブラリを公開しました。そこで、この記事ではZStringの紹介の他に、あらためてC#の文字列についてを深く分解して解説し、Stringの複雑さと落とし穴、そしてZStringの必要性について解説します。

[GitHub – Cysharp/ZString]

以下の表は `”x:” + x + ” y:” + y + ” z:” + z` という単純な文字列連結においてのパフォーマンス計測です。
zstring_01_table

それぞれ

  • “x:” + x + ” y:” + y + ” z:” + z
  • ZString.Concat(“x:”, x, ” y:”, y, ” z:”, z)
  • string.Format(“x:{0} y:{1} z:{2}”, x, y, z)
  • ZString.Format(“x:{0} y:{1} z:{2}”, x, y, z)
  • new StringBuilder(), Append(), .ToString()
  • ZString.CreateStringBuilder(), Append(), .ToString()

におけるメモリアロケーション量と速度の図になっています。ZStringはどのケースにおいても、連結後文字列の56B以外のアロケーションがありません。また、APIの使用勝手としてもStringBuilderあるいはString.Format、String.Concat、String.Joinをそのまま置き換えることができます。

String型の構造と生成

C#のString型は内部的にはUTF-16のバイト列となっています。
zstring_02
通常のオブジェクトと同じようにオブジェクトヘッダを持ちヒープ領域に確保され、同様に、原則new stringのみで生成可能です。StringBuilder.ToStringやEncoding.GetStringなども、最終的にnew stringを呼んで、新たな文字列を確保しています。

正確には、一部の.NET Framework内部のメソッドは String.FastAllocateString(int length)というinternalメソッドで確保された文字列領域に直接書き込みを行っています。このメソッドは外部に公開されていませんが、.NET Standard 2.1 ではString.Create<TState>(int length, TState state, SpanAction<char, TState>action)メソッドが追加され、これを呼ぶことで、新規の文字列領域に直接書き込みができます。

new stringで生成した文字列は、文字列の値として同一のものも、異なるメモリ領域に確保しています。ただし定数文字列のみ、インターンプールと呼ばれるアプリケーション共有の領域から、一意の参照を取得します。

var x = new string(new[] { 'f', 'o', 'o' });
var y = new string(new[] { 'f', 'o', 'o' });
var z = "foo";
var u = "foo";
var v = String.Intern(x);

// different reference: x != y != z
Console.WriteLine(Object.ReferenceEquals(x, y)); // false
Console.WriteLine(Object.ReferenceEquals(x, z)); // false

// same reference: z == u == v
Console.WriteLine(Object.ReferenceEquals(z, u)); // true
Console.WriteLine(Object.ReferenceEquals(z, v)); // true

// same value
Console.WriteLine(x == y && x == z && x == u && x == v); // true

実行時に生成した文字列を、インターンプールの指す文字列に変更するには String.Internメソッドが使用できます。Internメソッドはインターンプールから取得、存在しなかった場合は登録して、登録した参照を返します。

インターンプールに登録したメモリ領域は削除することができないため、通常うまく活用することは難しいでしょう。ただし弊社で開発しているインメモリデータベースである「MasterMemory」では、展開した文字列はマスタデータとして、アプリケーション実行中ずっと参照し続けるという性質を活かし、全ての文字列をインターン化しています。

internal class InternStringFormatter : 
IMessagePackFormatter<string>
{
    string IMessagePackFormatter<string>.Deserialize(
        ref MessagePackReader reader, ...)
    {
        var str = reader.ReadString();
        if (str == null) return null;
        return string.Intern(str);
    }
    // snip...
}

また、.NET Coreのランタイムでは「String Deduplication」という、GC時に重複した文字列を取り除く（単一の参照に置き換える）機能が提案されていますが、実装の完了にはもう少し時間がかかるでしょう。

+連結とString.Concat

Stringの+連結はC#コンパイラが特殊な処理を行い、String.Concatに変換します。

string.Concat(object arg0, object arg1)
string.Concat(object arg0, object arg1, object arg2)
string.Concat(params object[] values)
string.Concat(string str0, string str1)
string.Concat(string str0, string str1, string str2)
string.Concat(string str0, string str1, string str2, string str3)
string.Concat(params string[] values)

"x:" + x + " y:" + y + " z:" + zは6引数の連結のため、 string.Concat(string[] values)に変換されています(Visual Studio 2019 Version 16.4.2のC#コンパイラの場合。詳しくは後述）。つまり以下のような結果になります。

string.Concat(new string[]{"x:", x.ToString(), "y:", y.ToString(), "z:", z.ToString() } );

C#コンパイラによる+連結の最適化は、現在のものと昔のものとで異なる結果となる場合があります。たとえばVisual Studio 2019のC#コンパイラは (int x) + (string y) + (int z) の結果がString.Concat(x.ToString(), y, z.ToString())となりますが、Visual Studio 2017 のC#コンパイラは String.Concat((object)x, y, (object)z) と、連結対象に非stringの引数が含まれている場合にobjectのオーバーロードを採用するため、構造体のボクシングが発生してしまいます。Unityを使用する場合は、Unityに同梱されているC#コンパイラのバージョンによって結果が異なることに注意が必要です。

Concatのオーバーロードとして、3引数（古いコンパイラでobjectのオーバーロードが使われる場合）、あるいは4引数（新しいコンパイラでstringのオーバーロードが使われる場合）までは可変長引数を通さないため、より高速に処理されます。

StringBuilderとSpanFormatter

StringBuilderの実体は、一時的なバッファとしてchar[]を持ったクラスで、Appendでバッファに書き込み、ToStringで最終的な文字列を生成します。

public class SimpleStringBuilder
{
    char[] buffer;
    int offset;
    int index;

    public void Append(string value)
    {
        value.CopyTo(0, buffer, offset, value.Length);
        index += value.Length;
    }

    public override string ToString()
    {
        return new string(buffer, 0, index);
    }
}

複数のStringを連結する際に+=を使用すべきでないのは、+=のたびに新しい文字列を生成するからです。

string BuildDescription(Enemy enemy, bool addStatus)
{
    var desc = enemy.Name;
    desc += " Current HP:" + enemy.Hp; // allocate new string
    desc += " Current MP:" + enemy.Mp; // allocate new string
    if(addStatus)
    {
        desc += " Status:" + enemy.Status; // allocate new string
    }
    return desc;
}

StringBuilderは、この一時的な新しい文字列の生成を避け、代わりにchar[]へのコピーを行います。

string BuildDescription(Enemy enemy, bool addStatus)
{
    var sb = new StringBuilder();
    sb.Append(enemy.Name);
    sb.Append(" Current HP:");
    sb.Append(enemy.Hp);
    sb.Append(" Current MP:");
    sb.Append(enemy.Mp);
    if(addStatus)
    {
        sb.Append(" Status:");
        sb.Append(enemy.Status);
    }
    return sb.ToString();
}

この際に注意する必要があるのはsb.Append(" Current HP:" + enemy.Hp);などと書いてしまうと、連結した一時的な文字列を作ってしまうので、極力+の利用も避けましょう。

数値型などをAppendする場合は、.NET Standard 2.0（Unityなど）と .NET Standard 2.1（.NET Core 3.0など）では挙動が異なります。

// .NET Standard 2.0
public StringBuilder Append(int value)
{
    return Append(value.ToString(CultureInfo.CurrentCulture));
}

// .NET Standard 2.1
public StringBuilder Append(int value)
{
    return AppendSpanFormattable(value);
}

private StringBuilder AppendSpanFormattable<T>(T value)
    where T : ISpanFormattable
{
    if (value.TryFormat(RemainingCurrentChunk, 
        out int charsWritten, format: default, provider: null))
    {
        m_ChunkLength += charsWritten;
        return this;
    }
    return Append(value.ToString());
}

.NET Standard 2.0では単純にToStringした結果を追加している、つまり文字列化によるアロケーションが発生していますが、.NET Standard 2.1では ISpanFormattable.TryFormatにより文字列を介さず直接バッファに書き込みしています。ISpanFormattable自体はinternalですが、 「ISpanFormattable.references」を確認することにより、どの型がこうした直接書き込みを実装しているかを確認することができます。

ZStringでは、.NET Standard 2.1ではそれぞれのTryFormatを、.NET Standard 2.0では移植したTryFormatメソッドにより、Unity環境下でも数値型を追加する際の文字列アロケーションを避けています。

API自体はStringBuilderとほぼ同一ですが、usingで囲む必要があります。

// using ZString.CreateStringBuilder instead of new StringBuilder
using (var sb = ZString.CreateStringBuilder())
{
    sb.Append(enemy.Name);
    sb.Append(" Current HP:");
    sb.Append(enemy.Hp);
    sb.Append(" Current MP:");
    sb.Append(enemy.Mp);
    if (addStatus)
    {
        sb.Append(" Status:");
        sb.Append(enemy.Status);
    }
    return sb.ToString();
}

CreateStringBuilderの戻り値であるUtf16ValueStringBuilderは、structであるため、StringBuilder自体のヒープへのアロケーションが避けられていることと、内部で書き込みに使用するchar[]バッファをArrayPoolから取得することにより、バッファそれ自体のアロケーションを避けています（ただし、そのためusingで使用後にバッファを返却する必要がある）。

また、ZString.Concatは内部でUtf16ValueStringBuilderを利用していることと、15引数までジェネリックでオーバーロードを用意しているため、Unity環境下においても数値型の文字列変換アロケーションを完全に避けることが可能です。

// many allocation(especially on Unity)
enemy.Name + " Current HP:" + enemy.Hp + " Current Mp:" + enemy.Mp;

// zero allocation
// ZString.Concat<T0~T15>(T0 arg0, T1 arg1, T2 arg2,..,T15 arg15)
ZString.Concat(enemy.Name, " Current HP:", enemy.Hp, " Current Mp:", enemy.Mp);

FormatとReadOnlySpan<char>

String interpolationはString.Formatに変換されるため、それ自体のオーバーヘッドはありませんが、String.Format自体の引数がobjectしか受け入れないため、ボクシングは発生します。

// String interpolationによる文字列変換はC#コンパイラによって下記のコードに置き換えられる
$"{enemy.Name} Current Hp:{enemy.Hp} Current Mp:{enemy.Mp}";

// string.Object(string, object, object, object)
String.Format("{0} Current Hp:{1} Current Mp:{2}", enemy.Name, enemy.Hp, enemy.Mp);

// String.Format自体は3引数までは可変長引数を避けられる
string string.Format(string format, object arg0)
string string.Format(string format, object arg0, object arg1)
string string.Format(string format, object arg0, object arg1, object arg2)
string string.Format(string format, params object[] args)

また、StringBuilder.Appendと同様に、.NET Standard 2.0では更に文字列変換のアロケーションが発生します。

ZString.FormatはZString.Concatと同様に15引数までジェネリックでオーバーロードが存在することと、.NET Standard 2.0環境でもTryFormatによる直接変換を実装することでゼロアロケーションを実現しています。

// ZString.Format<string, int, int>(string format, T0 arg0, T1 arg1, T2 arg2);
ZString.Format("{0} Current Hp:{1} Current Mp:{2}", enemy.Name, enemy.Hp, enemy.Mp);

String.Formatは「複合書式指定文字列（Composite Formatting）」をサポートしています。{ index[,alignment][:formatString]}で表現する複合書式文字列は、日付を任意のフォーマットに整形したり、数値の桁数を固定することに使えます。

var x = 123.454321;
var y = 12.34;

// x:123.45, y:0012.3
string.Format("x:{0:.##}, y:{1:0000.#}", x, y);

ZString.FormatはformatStringはサポートしますが、alignmentのサポートはありません。

最終的にこの複合書式文字列は.##のように抽出されて TryFormat に渡されるのですが、改めて ISpanFormattable の定義を見てみましょう。

internal interface ISpanFormattable
{
    bool TryFormat(Span<char> destination, out int charsWritten,
            ReadOnlySpan<char> format, IFormatProvider? provider);
}

string formatではなくてReadOnlySpan<char> formatなことがポイントです。これは文字列を解析した際に得られる書式文字列が、部分的なスライスだからです。上記例の文字列で考えると [x:][.##][, y:][0000.#] というスライスに分割され、それぞれ [x:]と[, y:]はそのままコピー、[.##]と[0000.#]はフォーマット文字列としてTryFormatに渡されます。このように、フォーマット文字列をReadOnlySpan<char>で表現することにより、文字列のアロケーションを避けています。

冒頭で説明したようにStringの実体はUTF-16のバイト列であるため、ReadOnlySpan/Span<char>で表現することができます。ReadOnlySpan<char>はstringと違って、部分的な取得が可能なこと、char[]そのものを使用することができるため、プールからの利用が容易になるのが特徴です。

そのためstringをReadOnlySpan<char>として受け取るAPIを用意したほうが性能を出しやすいですが、ref structのためフィールドに保持したりはできないことと、.NET Standard 2.1ではstring -> ReadOnlySpan<char>の暗黙的変換が用意されているためReadOnlySpan<char>を受け取るAPIだけでも使い勝手を損ねませんが、.NET Standard 2.0では.AsSpan()を明示的に記述しないと渡せないため、ユーザービリティは悪くなります。よく注意した設計が必要になるでしょう。

Stringを通さない直接的な書き込み

ZStringの内部実装はゼロアロケーションですが、最終的にstringを生成するところでアロケーションしています。これは、ほとんどのAPIが文字列を要求するためです。しかし、対象ライブラリがstring以外を受け入れるAPIを持っている場合は、この最後の文字列生成も避けて、完全なゼロアロケーションを達成できます。例えばUnityのTextMeshProは SetCharArray(char[] sourceText, int start, int length)というAPIを持っているため、string生成を避けて直接渡すことができます。

TMP_Text tmp;

// create StringBuilder
using(var sb = ZString.CreateStringBuilder())
{
    sb.Append("foo");
    sb.AppendLine(42);
    sb.AppendFormat("{0} {1:.###}", "bar", 123.456789);

    // direct write(avoid string alloc) to TextMeshPro
    tmp.SetText(sb);

    // SetText(Utf16ValueStringBuilder) is the same as following
    var buffer= sb.AsArraySegment();
    tmp.SetCharArray(buffer.Array, buffer.Offset, buffer.Count);
}

// convinient helper to use ZString.Format
tmp.SetTextFormat("Position: {0}, {1}, {2}", x, y, z);

// other ZString direct write utilities
.AsSpan()
.AsMemory()
.TryCopyTo(Span<char>, out int writtenChars);

.NET CoreにおいてもReadOnlySpan<char>を受け取るAPIが増えてきていますし、こうしたstringを避けるアプローチが増えていけば、アプリケーション全体としてより高性能になっていくはずです。

Utf8StringとReadOnlySpan<byte>

ネットワークやファイル入出力においては、最終的に要求されるデータはString(UTF-16)ではなくてbyte[](UTF-8)の場合も多いでしょう。その場合に、 Encoding.UTF8.GetBytes(stringBuilder.ToString())としていたら、char[]書き込み→string生成→UTF-8エンコーディングと、かなりの無駄があります。直接UTF-8で書き込めばオーバーヘッドはゼロになります。そのためにZStringではCreateUtf8StringBuilderというメソッドを用意しています。

using(var sb = ZString.CreateUtf8StringBuilder())
using(var fs = File.Open("foo.txt", FileMode.OpenOrCreate))
{
    sb.Append("foo");
    sb.AppendLine(42);
    sb.AppendFormat("{0} {1:.###}", "bar", 123.456789);

    // write inner Utf8 buffer to stream
    await sb.WriteToAsync(fs);

    // or get inner buffer
    // .AsSpan(), .AsMemory(), TryCopyTo
}

頻繁な書き込みが必要なネットワークにおくるメトリクスデータ生成や、テンプレートエンジンのバックエンドなどで有効に使えるはずです。

数値型のUTF-8への直接書き込みには System.Buffers.Text.Utf8Formatterを使用しています。これらは Span<byte>に書き込むためのTryFormatメソッドを持っています。

public static bool TryFormat(int value, Span<byte> destination,
    out int bytesWritten, StandardFormat format = default)

つまり、string(Utf16)がReadOnlySpan<char>と表せるように、UTF-8はReadOnlySpan<byte>として表せるということです。

まとめ

C#のString完全に理解した。と言える程度に踏み込んで解説しました。Stringは基本の型ですが、基本の型であるがゆえに、単純なようで多くの特殊な動作が詰まっています。そして、普通に使っているだけでは、それらの落とし穴をすべて避けるのは不可能と言っていいでしょう。ZStringはString/StringBuilderと似たようなAPIを提供することで、ここで述べた複雑な詳細について考えなくても、単純に置き換えるだけでベストなパフォーマンスを叩き出せるように設計されています。

Cygamesでも既にプロジェクトのパフォーマンス最適化のため使用を始めています。ぜひ、皆さんもお試しいただければ幸いです。

このエントリーをはてなブックマークに追加