【C#】文字列の最適化手法について

今回はC# Advent Calendar 2024の20日目の記事です。テーマは文字列の最適化について。

C#において文字列を表現するstring型はクラスであり、生成のたびにヒープにアロケーションを行うためパフォーマンス低下の要因になりがちです。また、C#のstringの中身は歴史的経緯からUTF-16となっており、UTF-8を直接扱うことができないため、変換の際に余計なオーバーヘッドが発生してしまいます。

そのため、近年の.NETではSpan等を活用して効率的な文字列操作を行うAPIが多数追加されています。また、UTF-8を扱うための機能も色々と用意されています。

そこで今回の記事では、最新の.NET9を用いて文字列操作を最適化する手法を紹介していきます。普段から簡単に使える手法も多いので、是非とも覚えておきましょう。

string型

と、その前にまずはstring型について見ていきましょう。SharpLabでstring型のメモリレイアウトを確認してみます。

Inspect.Heap("str");

stringの実態はUTF-16のバイト列です。通常のオブジェクトと同じくヘッダーが置かれた後に、長さとバイト列が続きます。メモリレイアウト自体はchar配列とほとんど同じです。

また、stringはchar配列と同様にインデクサで文字を取得したり、forやforeachで全ての文字を列挙することができます。

var str = "abcde";

// 最初の文字(char)を取得
var c0 = str[0];

// for文で列挙
for (int i = 0; i < str.Length; i++)
{
    Console.WriteLine(str[i]);
}

// foreach文で列挙
foreach (var c in str)
{
    Console.WriteLine(c);
}

また、C#においてstringは不変なクラスです。ToUpperやSubstringなどのメソッドで文字列を取得する際には、毎回新たなstringがヒープ上に確保されます。

// これらは新たな文字列を生成する (アロケーションが発生)
var sub = str.Substring(0, 3);
var upper = str.ToUpper();

ReadOnlySpan<char>の活用

前の項で触れたようにstringは不変であるため、Substringで一部分を取得する際に毎回アロケーションが発生してしまいます。

そこで文字列をReadOnlySpan<char>として扱うことで、アロケーションなしで高速に部分文字列を参照することができます。(Span<char>ではないことに注意してください。stringは書き換えることができないため、AsSpan()が返す型はReadOnlySpan<char>になります)

var str = "abcde";

// これはアロケーションが発生するので極力避ける
var sub = str.SubString(0, 3);

// これはSpan経由でアクセスできるのでゼロアロケーションで高速
var span = str.AsSpan(0, 3);

また、stringはReadOnlySpan<char>への暗黙的変換がサポートされています。以下のようにReadOnlySpan<char>にそのままstringを渡すことが可能です。

// ReadOnlySpan<char>を受け取るメソッド
void Foo(ReadOnlySpan<char> span)
{
   // ...
}

// そのままstringを渡せる
Foo("abcde");

このように文字列をstringではなくSpan<T>で扱うのが現代の.NETにおけるハイパフォーマンスな文字列操作の基本になります。この後にもSpanを活用した手法は多く登場するため、覚えておきましょう。

文字列の作成

C#では、文字列(string)を作成するための方法がいくつか用意されています。

文字列リテラル

最も基本的な作成方法は文字列リテラルでしょう。C#では「”」(ダブルクォーテーション)で囲まれた部分が文字列リテラルとして認識されます。

var str = "Hello!";

インターンプール

通常、インスタンス化されたstringは同一の内容であっても別のメモリ領域に置かれます。

// 文字列リテラル
var a = "1234";

// 数値から作成した文字列
var b = 1234.ToString();

// これはfalseになる
Console.WriteLine(object.ReferenceEquals(a, b));

文字列リテラルで作成された文字列はインターンプールと呼ばれるメモリ領域に保存されます。そのため、同一の文字列リテラルが指すメモリ領域は必ず同じになります。

// 同一の文字列定数は事前にインターン化される
var a = "Hello";
var b = "Hello";

// そのためこれはtrueになる
Console.WriteLine(object.ReferenceEquals(a, b));

また、string.Intern()メソッドを用いることで文字列を手動でインターン化することができます。

// 文字列リテラル
var a = "1234";

// インターンプールから文字列を取得する
var b = string.Intern(1234.ToString());

// これはtrueになる
Console.WriteLine(object.ReferenceEquals(a, b));

インターン化した文字列は削除できないため、巨大な文字列をインターン化すると余計にメモリを消費してしまいます。使い所が難しいですが、覚えておくと役に立つかもしれません。

string.Createによる初期化

.NET Standard 2.1以降では、string.Create()の新たなオーバーロードが追加されています。

public static string Create<TState> (int length, TState state, System.Buffers.SpanAction<char, TState> action);

このメソッドは新たに確保した文字列領域にSpanActionを用いて直接書き込みを行います。これを用いることで、余計なバッファを使うことなく高速に文字列を初期化することが可能になります。

SpanAction<T, TState>のTStateはクロージャを避けるための引数です。デリゲート内で外部変数にアクセスしたい場合はstate引数に値を渡します。

int[] values = [0, 1, 2, 3, 4, 5];

var str = string.Create(values.Length, values, (buffer, values) =>
{
    // デリゲート内で初期化を行う
    for (int i = 0; i < values.Length; i++)
    {
        // 文字列領域(Span<char>)に直接書き込む
        buffer[i] = (char)('0' + values[i]);
    }
});

ただし、このstring.Create()で確保される文字列領域はゼロ初期化されていません。デリゲート内でSpan<char>の全ての要素に書き込む必要があることに注意してください。(そうしないとランダムな文字列が含まれる可能性があります)

[余談] string.FastAllocateString(int length)について

.NET内部では、new string()とは別にstring.FastAllocateStringというinternalメソッドが用意されています。

internal static extern string FastAllocateString(int length);

本来stringは不変ですが、内部ではFastAllocateStringで確保したstringを書き換えることで高速な文字列操作を行なっています。例えば、先ほどのstring.Create()の実装は以下のようになっています。

public static string Create<TState>(int length, TState state, SpanAction<char, TState> action)
    where TState : allows ref struct
{
    // nullチェック
    if (action is null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.action);
    }

    // lengthのチェック
    if (length <= 0)
    {
        if (length == 0)
        {
            return Empty;
        }

        ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.length);
    }

    // FastAllocateStringを用いてstringを確保
    string result = FastAllocateString(length);

    // GetRawStringData()から_firstの参照を取り出し、string内部にアクセス可能なSpan<char>を作成
    action(new Span<char>(ref result.GetRawStringData(), length), state);
    return result;
}

しかし、本来不変であるstringを書き換えることは非常に危険であるため、それを助長させるFastAllocateStringは使われるべきではないとしてinternalとなっています。以前FastAllocateStringをpublicにする提案がされていましたが、上記の理由で却下されています。

文字列の連結

C#では文字列を連結するための手段がいくつか存在し、パフォーマンスもそれぞれ異なります。一つずつ順番に見ていきましょう。

+演算子 / string.Concat()

C#で文字列を結合する最も簡単な方法は+演算子を用いることです。他の言語と同様、文字列同士を+演算子で結合することができます。数値が含まれる場合は自動的にToString()で文字列に変換されます。

var foo = "foo";
var bar = "bar";
var two = 2;

// +演算子を用いて結合する
var foobar2 = foo + bar + two;

非常に簡単なのでやりがちですが、

これはコンパイル時にstring.Concat()に変換されます。

// +結合はstring.Concat()に変換される
var foobar2 = string.Concat(foo, bar, two.ToString());

古いバージョンのコンパイラではobjectを引数にとるオーバーロードが用いられたためBoxingが発生していましたが、現在はToString()で事前に文字列化したものを渡すようになっているため効率的です。

ただし、string.Concat()は4引数まではオーバーロードが個別に用意されているため高速ですが、それ以上の場合はstring[]が作成されるため、余計なアロケーションが発生します。

var a = "a";
var b = "b";
var c = "c";
var d = "d";
var e = "e";

// 5個の変数を+で結合
var abcde = a + b + c + d + e;

// これはstring.Concat(string[] values)が用いられる
var abcdef = string.Concat(new string[] { a, b, c, d, e });

また、+=でも結合が可能ですが、これはConcatの多段呼び出しになるため += ごとに余計な文字列が生成されてしまいます。

var a = "a";
var b = "b";
var c = "c";

// これは毎回文字列が生成されてしまう！
var str = "";
str += a;
str += b;
str += c;

このような場合は後述するStringBuilderやDefaultInterpolatedStringHandlerを利用しましょう。

StringBuilder

連結後のstringのサイズが決まっていない場合などでは、StringBuilderを利用することで効率的な文字列連結を実現できます。

// 新しいStringBuilderを作成
var builder = new StringBuilder();

// builderに文字列を追加していく
builder.Append("foo");
builder.Append("bar");
builder.Append(2);

// stringを作成
var str = builder.ToString();

StringBuilderは内部でchar配列をバッファとして抱えており、追加時の文字列化を避けた効率的な連結を実現できます。また、Append()には様々なオーバーロードが用意されており、可能な限りToString()を避けるようになっています。

なお、StringBulderはclassであるため上のコードはbuilder自体のアロケーションがあります。アロケーションを削減したい場合は都度builderを生成するのではなく、Clear()で使い回すようにしましょう。

// StringBuilderの状態をリセットする
builder.Clear();

また、.NET 6以降ではStringBuilderの代わりにDefaultInterpolatedStringHandlerを用いることでより効率的な文字列連結を行うことができます。これは後の文字列補間の項目で紹介します。

文字列補間

C# 6以降の文字列リテラルでは文字列補間を利用できます。

var apples = 4;

// $"... {} ..."のような形で文字列補間を行うことができる
// これは"I have 4 apples"が表示される
Console.WriteLine($"I have {apples} apples");

これのコンパイル結果はC#10以前と以降では大きく異なり、パフォーマンスもかなり変わってきます。具体的な処理内容について、順番に見ていきましょう。

C#10以前 / string.Format()

C#10以前の補間文字列はstring.Format()に展開されます。コードにすると以下のような感じです。

var a = 10;
var b = "foo";

// 文字列補間式
var str = $"{a}, {b}";

// C#10以前では、これは以下のように展開される
var str = string.Format("{0}, {1}", a, b);

string.Format()は引数3つまではオーバーロードが用意されていますが、それ以上は可変長引数になるため余計なアロケーションが追加されます。また、string.Format()の引数はobject型であるため、値型を渡すとBoxingが発生してしまいます。

そのため補間文字列はあまり高速であるとは言えず、パフォーマンスが重要な場面ではこれを避ける必要がありました。

C#10以降 / DefaultInterpolatedStringHandler

そこで、C#10 / .NET6で補間文字列の大幅な高速化が図られました。C# 10以降の補間文字列はコンパイル時に以下のように展開されます。

var a = 10;
var b = "foo";

// 文字列補間式
var str = $"{a}, {b}";

// C#10以降では以下のように展開される
var handler = new DefaultInterpolatedStringHandler(2, 2);
handler.AppendFormatted(a);
handler.AppendLiteral(", ");
handler.AppendFormatted(b);
var str = handler.ToStringAndClear();

string.Format()の代わりにDefaultInterpolatedStringHandlerという構造体が用いられています。これは軽量なStringBuilderのようなもので、AppendLiteral()とAppendFormatted()を用いて順番に値を書き込みます。また、DefaultInterpolatedStringHandlerは内部でArrayPool<T>.Sharedから借りたバッファを用いるため、書き込みにおけるアロケーションは一切ありません。

そのため、C#10 / .NET 6以降の環境では補完文字列は高いパフォーマンスを発揮します。これらの環境では積極的に使っていくと良いでしょう。(ただし、C#10以降でコンパイルしたとしても、DefaultInterpolatedStringHandlerが存在しない場合はstring.Format()にフォールバックされることに注意してください)

また、DefaultInterpolatedStringHandlerはコンパイラ側での利用を想定した型ではありますが、StringBuilderの代替として利用することも可能です。StringBuilderとは異なりこちらは構造体であるため、アロケーションを気にせずに使うことができます。

// DefaultInterpolatedStringHandlerを作成する
// コンストラクタの引数は順に
// int literalLength: 補間文字列のリテラル部分($"" の中から {} を除いた部分)の文字列の長さ
// int formattedCount: {}の個数
// となっているが、不足分は自動で拡張されるので(0, 0)でも問題ない
var builder = new DefaultInterpolatedStringHandler(6, 1);

builder.AppendLiteral("foo");
builder.AppendLiteral("bar");
builder.AppendFormatted(2);

// 作成時は必ずToStringAndClear()を用いること
// これを呼び出すことで内部バッファがArrayPoolに返却される
var foobar2 = builder.ToStringAndClear();

[余談] InterpolatedStringHandlerを自作する

InterpolatedStringHandlerは補完文字列の高速化のために導入された機能ですが、これを利用することで補完文字列のコンパイル結果をカスタマイズすることができます。InterpolatedStringHandlerはAsyncMethodBuilderなどと同じくパターンベースの実装となっており、必要なメソッドさえあれば自分で実装したhandlerで補完文字列を使うことも可能です。

代表的な例としては構造化ログ(Structure Logging)の実装で、Cysharp/ZLoggerというライブラリではInterpolatedStringHandlerを用いてハイパフォーマンスな構造化ログを実現しています。

以下は最小限のコードで構成されたInterpolatedStringHandlerの実装です。

// InterpolatedStringHandler属性をつける
[System.Runtime.CompilerServices.InterpolatedStringHandler]
public struct CustomInterpolatedStringHandler
{
    // int literalLength, int formattedCountをコンストラクタ引数として持つ必要がある
    // 追加の引数を追加することも可能だがここでは省略
    public CustomInterpolatedStringHandler(int literalLength, int formattedCount)
    {
        ... 
    }

    // AppendLiteral()とAppendFormatted<T>()は必須
    // オーバーロードを追加したり、alignmentとformatの引数を追加することも可能
    public void AppendLiteral(string s) { ... }
    public void AppendFormatted<T>(T x) { ... }
}

こうして作成したInterpolatedStringHandlerは以下のように利用できます。

var a = 10;
var b = 20;

// InterpolatedStringHandlerの型で補完文字列を受け取ることが可能
CustomInterpolatedStringHandler handler = $"a:{a}, b:{b}";

// これは以下のような形に展開される
var temp = new CustomInterpolatedStringHandler(6, 2);
temp.AppendLiteral("a:");
temp.AppendFormatted(a);
temp.AppendLiteral(", b:");
temp.AppendFormatted(b);
var handler = temp;

この他にもInterpolatedStringHandlerには色々な仕様がありますが、長くなるため詳細はここでは触れません。詳しく知りたい方はImprovement Interpolated Strings 完全に理解したという非常にわかりやすい記事があるため、そちらを読んでみると良いでしょう。

文字列と値の変換

jsonやcsv等のテキストデータの読み書きを行うときなど、文字列と値を相互に変換したい場面はよくあります。ここでは文字列と値の相互変換の方法と、その最適化手法について見ていきましょう。

値→文字列の変換

ToString() / IFormattable

C#ではobjectがToString()を持つため、全ての型に対してToString()を通じた文字列への変換がサポートされています。

// int -> string
var str = 10.ToString();

また、単にToString()するだけではなく、書式を指定して文字列化したいことも多いでしょう。また、カルチャによって文字列の形式を変更したい場合もありえます。

これは対象の型がIFormattableを実装していれば、ToString()に書式を表すstringとIFormatterProviderを指定するオーバーロードを使うことができます。

public interface IFormattable
{
    string ToString(string? format, IFormatProvider? formatProvider);
}

以下はfloatを書式とカルチャを指定してstringに変換するコードです。

// 書式文字列とカルチャを指定してstringに変換する
var str = 1.23456789f.ToString("F2", CultureInfo.InvariantCulture);

しかし、ToString()は新たなstringを生成するためアロケーションが発生します。多少であれば問題にはなりませんが、頻繁に呼ばれる箇所ではなるべく避けたいところです。

ISpanFormattable

そこで.NET 6からISpanFormattableというインターフェースが追加されました。(実はそれ以前からinternalで存在していたのですが、InterpolatedStringHandlerの導入に従って正式なAPIとして公開されました。詳細はこのissueで確認できます)

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

TryFormatメソッドではSpan<char>を書き込み用のバッファとして受け取り、書き込んだ文字数をcharsWrittenで返します。また、書式文字列はstringではなくReadOnlySpan<char>で受け取ります。これによってstringの生成を無くし、ゼロアロケーション化することが可能になりました。

主要な数値型はこのISpanFormattableを実装しています。以下はintをTryFormatで文字列に変換するコードです。

// 適当な書き込み用のバッファを用意する
// 実際に使うときはArrayPool<char>やIBufferWriterなどから取得する
var buffer = new char[10];

var value = 10000;

// TryFormatでバッファに書き込む
// バッファの長さが足りない場合はfalseを返す (不正な書式に対してはfalseではなく例外をスローする)
if (value.TryFormat(buffer, out var charsWritten, "N"))
{
    // 10,000.00
    Console.WriteLine(buffer.AsSpan(0, charsWritten).ToString());
}

また、DefaultInterpolatedStringHandlerを用いて文字列補完を行う場合、対象の型がISpanFormattableを実装している場合はこれを優先して利用します。もしカスタム型を文字列補完に使う場合は、その型でISpanFormattableを実装しておくと良いでしょう。

文字列→値の変換

C#では多くの数値型に対してParse() / TryParse()が用意されており、文字列から値へ変換することができます。

var str = "10000";

// string -> intの変換
var num0 = int.Parse(str);

// Tryもある
if (int.TryParse(str, out var num1))
{
    // 変換成功時の処理...
}

もちろん、これらのメソッドにはReadOnlySpan<char>を受け取るオーバーロードも用意されています。

また、.NET 7からはこれらのParse処理を抽象化するためのIParsable<T> / ISpanParsable<T>が追加されました。(これにはC#11からの新機能であるstatic abstractが用いられています)

public interface IParsable<TSelf>
    where TSelf : IParsable<TSelf>
{
    static abstract TSelf Parse(string s, IFormatProvider? provider);
    static abstract bool TryParse(string? s, IFormatProvider? provider, out TSelf result);
}

public interface ISpanParsable<TSelf> : IParsable<TSelf>
    where TSelf : ISpanParsable<TSelf>
{
    static abstract TSelf Parse(ReadOnlySpan<char> s, IFormatProvider? provider);
    static abstract bool TryParse(ReadOnlySpan<char> s, IFormatProvider? provider, out TSelf result);
}

IParsable<T>とISpanParsable<T>の違いは、受け取る文字列がstringかReadOnlySpan<char>かどうかです。Spanの方がパフォーマンスに優れるため、可能な限りISpanParsable<T>を用いると良いでしょう。

UTF-8

現在ではUTF-8が文字コードのデファクトスタンダードとなっていますが、C#が登場した当時は固定長であるUTF-16が広く用いられていたため、プリミティブ型であるstringのバイト列はUTF-16となっています。

そのため、UTF-8のテキストをstringで扱おうとするとbyte[]とstringを相互変換する必要が生じてきます。

// byte[] -> string
var str = Encoding.UTF8.GetString(bytes);

// string -> bytes[]
var bytes = Encoding.UTF8.GetBytes(string);

これは変換の処理分だけオーバーヘッドがあるだけでなく、変換時にstringとbyte[]のアロケーションが発生してしまいます。

そのため、C#でUTF-8をどのように扱うかに関しては長らく議論が繰り広げられていました。Utf8Stringの導入や、そもそもstringの中身をUTF-8に変えてしまうなどの様々な案がありましたが、結局はReadOnlySpan<byte>を直接UTF-8バイト列として扱う手法が定着してしまったため、未だUtf8Stringは実現していません。

このような複雑な経緯があるため、C#のUTF-8周りは扱いづらい部分があることは否定できません。しかし、パフォーマンスを考えると可能な限りstringを通さずに扱うべきでしょう。近年の.NETではUTF-8を扱うAPIも増えてきたため、一度慣れてしまえば困ることはないはずです。

ReadOnlySpan<byte> / UTF-8リテラル

先ほど述べた通り、現代のC#ではUTF-8を直接バイト列として扱うことが一般的です。例えばint.Parse()はReadOnlySpan<byte>のオーバーロードが用意されているため、stringを経由することなく直接変換することが可能です。

// "100"を表すUTF-8バイト列を作成
byte[] utf8 = [(byte)'1', (byte)'0', (byte)'0'];

// そのままint.Parse()に渡せる
var value = int.Parse(utf8);

// 100
Console.WriteLine(value);

また、C#11以降ではUTF-8リテラルが利用できます。これを用いることで、文字列リテラルからUTF-8バイト列を取得できます。

// 文字列リテラルの最後にu8をつける
// 型はReadOnlySpan<byte>になる
ReadOnlySpan<byte> = "100"u8;

IUtf8SpanFormattable / IUtf8SpanParsable

また、.NET8からはUTF-8版のISpanFormattable<T> / ISpanParsable<T>である、IUtf8SpanFormattable<T> / IUtf8SpanParsable<T>が用意されています。

public interface IUtf8SpanFormattable
{
    bool TryFormat(Span<byte> utf8Destination, out int bytesWritten, ReadOnlySpan<char> format, IFormatProvider? provider);
}

public interface IUtf8SpanParsable<TSelf>
    where TSelf : IUtf8SpanParsable<TSelf>?
{
    static abstract TSelf Parse(ReadOnlySpan<byte> utf8Text, IFormatProvider? provider);
    static abstract bool TryParse(ReadOnlySpan<byte> utf8Text, IFormatProvider? provider, [MaybeNullWhen(returnValue: false)] out TSelf result);
}

使い方は通常のISpanFormattable<T> / ISpanParsable<T>とほとんど同じですが、バッファの型がSpan<byte> / ReadOnlySpan<byte>になっています。

文字列のルックアップ

最後に文字列辞書の探索に関する話にも触れておきましょう。

Dictionaryを利用する場合、文字列をキーにする場面はよくあります。その場合、基本的にはstring型をキーにしたDictionaryを使うことになるでしょう。

// stringをキーにした辞書
Dictionary<string, User> dictionary = new();

ほとんどの場合はこれで問題ありませんが、テキストを解析する場面などでは、スライスした文字列を都度stringにデコードする必要が生じてしまいます。また、ReadOnlySpan<char>はref structであるため、その制約から辞書のキーとして利用することができません。

さらにテキストがUTF-8の場合、stringで持とうとするとbyte[]→stringの変換を行うことになり、かなり大きめのアロケーションが発生してしまいます。

これらの問題を避けるため、シリアライザなどのパフォーマンスが要求されるライブラリでは、文字列に特化した辞書を自作するテクニックがよく使われていました。

GetAlternateLookUp (.NET 9)

そこで、.NET 9ではDictionaryのTKeyとは別の型でルックアップを行うためのGetAlternateLookUp()メソッドが追加されました。

public System.Collections.Generic.Dictionary<TKey, TValue>.AlternateLookup<TAlternateKey> GetAlternateLookup<TAlternateKey>();

これを利用するには、辞書内での比較に用いるEqualityComparer<T>がIAlternateEqualityComparerを実装している必要があります。

public interface IAlternateEqualityComparer<in TAlternate, T>
    where TAlternate : allows ref struct
    where T : allows ref struct
{
    bool Equals(TAlternate alternate, T other);
    int GetHashCode(TAlternate alternate);
    T Create(TAlternate alternate);
}

標準ではstringの比較に利用するEqualityComparerがIAlternateEqualityComparer<ReadOnlySpan<char>, string>を実装しています。そのため、GetAlternateLookupを用いてstringキーのDictionaryをReadOnlySpan<char>で探索することが可能になります。

var dictionary = new Dictionary<string, int>
{
    { "foo", 10 },
    { "bar", 20 },
    { "baz", 30 }
};

var keys = "foo,bar,baz";

// ReadOnlySpan<char>をキーにしたAlternateLookupを取得
var lookUp = dictionary.GetAlternateLookup<ReadOnlySpan<char>>();

// stringを使わずReadOnlySpan<char>で辞書の操作が行える
if (lookUp.TryGetValue(keys.AsSpan(0, 3), out var value))
{
    Console.WriteLine(value);
}

まとめ

今回はC#の文字列について、かなり細かい部分まで踏み込んだ解説になりましたが、いかがだったでしょうか。長々と書きましたが、「Span<T>を活用してstringの生成を可能な限り避ける」ということを押さえてもらえれば十分です。

文字列の効率的な扱い方を覚え、よりパフォーマンスの良いコードを書いていきましょう。