StringBuilderよりもメモリアロケーションを少なく文字列を結合する

## はじめに

C#の文字列結合と言えば皆様は何を思い浮かべるでしょうか。
`+` 演算子に `string.Concat()` メソッド，こなれたC#erなら `StringBuilder` クラスの利用を考えるでしょう。
本記事では一定の条件を満たした場合の文字列結合として，より最適な手法である `string.Create<TState>(int, TState, SpanAction<char, TState>)` メソッドを紹介したいと思います。

**本ドキュメントの対象バージョン**
|項目名|バージョン|
|-:|:-:|
|.NET|.NET7.0|
|C#|11|

## `string.Create<TState>(int, TState, SpanAction<char, TState>)` について

`string.Create()` メソッドはオーバーロードが複数ありますが，本記事で扱うのは[型引数の用意されているもの](https://learn.microsoft.com/ja-jp/dotnet/api/system.string.create?view=net-7.0#system-string-create-1(system-int32-0-system-buffers-spanaction((system-char-0))))です。以降本記事で「`Create()` メソッド」とした場合はこの `string.Create<TState>(int, TState, SpanAction<char, TState>)` メソッドを指すとお考え下さい。

このメソッドは，第一引数で指定した長さの文字列を `Span<char>` として第三引数の関数で受け取り，文字列の初期化処理を行うというものです。
文章で書かれても分かりづらいと思うので，以下に文字列 `0123456789` を生成するサンプルを示します。

```cs
using System;

// 文字列を生成
string s = string.Create<string>(10, "Progress: {0}", (Span<char> span, string state) =>
{
    for (int i = 0; i <= 9; i++)
    {
        // 文字列を編集
        i.ToString().CopyTo(span[i..]);
        // 途中経過を出力
        Console.WriteLine(state, span.ToString().Replace('\0', '_'));
    }
});

// 生成された文字列を出力
Console.WriteLine("Result: {0}", s);

/* 出力
Progress: 0_________
Progress: 01________
Progress: 012_______
Progress: 0123______
Progress: 01234_____
Progress: 012345____
Progress: 0123456___
Progress: 01234567__
Progress: 012345678_
Progress: 0123456789
Result: 0123456789
 */
```

第一引数は生成する文字列長なので，ここでは `10` を指定しています。
第三引数で与えた関数では実際に文字列長10の文字列を `Span<char>` として編集しています。第三引数は `SpanAction<char, TState>` となっていますが，これは `Action<Span<char>, TState>` と捉えてください（`ref struct` である `Span<char>` は型引数にできないため，このような専用のデリゲートが定義されています）。このデリゲートが取る引数は編集する文字列である `Span<char>` と， `Create()` メソッドに与えられる第二引数（サンプルでいう `"Progress: {0}"`）となっています。デリゲートに与える引数が態々用意されているのは，ローカル変数のキャプチャを回避するためです。

出力を見ると，forループが進むごとに文字列が編集されていくのが見て取れます。尚，未編集の文字はヌル文字（`\0`）となっています。

## 本手法が役立つ条件

`Create()` メソッドが有効と考えられる条件（AND条件）を以下に列挙します。

1. 結合後の文字列長が既に分かっている
1. `StringBuilder.ToString()` を一度しか実行しない

まず，条件1に関しては手法の都合上どうしようもないです。
詳細は後述しますが，この手法では最初に結合後のサイズ分メモリを確保します。

条件2がこの手法が有利となる一番の理由です。
その理由を以下で説明します。

### StringBuilderの問題点

`StringBuilder` は大量の文字列を結合する際に有用です。
例えば以下のような，10～99迄の数値を順番に結合して文字列にするケースです。

<details open>
<summary>サンプル</summary>

```cs
using System.Collections.Generic;
using System.Linq;
using System.Text;

IEnumerable<int> range = Enumerable.Range(10, 90);
var builder = new StringBuilder();

// 一つずつ数値を結合
foreach (int current in range) builder.Append(current);

// 結合後の文字列を取得
string combined = builder.ToString();
```

</details>

ここでは最初に `StringBuilder` のインスタンスを生成，
次に `foreach` 内で `Append()` して数値を追加，
最後に `ToString()` で結果を取得しています。

ここまでは皆さんのよくやる書き方かと思われます。
これ以降まだ `builder` を使うならこれで問題ありませんが，これ以上 `builder` を使わない場合はメモリアロケーションの回数という面で不利になる場合があります。
上記のサンプルでは，メモリアロケーションは

1. `Append()` で `StringBuilder` の内部文字列を拡張する際
1. [`ToString()` する際](https://github.com/dotnet/runtime/blob/release/7.0/src/libraries/System.Private.CoreLib/src/System/Text/StringBuilder.cs#L334-L370)

の二つのフェーズで発生します。
かなり雑に言うと，`StringBuilder` は `List<T>` のように処理を行っており，予め大きめにメモリを確保しておく→要素追加時にメモリ領域が足りない場合は再アロケーションしています。
こちらは `StringBuilder` のコンストラクタで `capacity` を予め指定すれば避けられます。

次に， `ToString()` を行う際のアロケーションは， `StringBuilder` の汎用性故のことです。
`ToString()` をした後にインスタンスが使われなくなる場合はアロケーションを行わずに内部の文字列をそのまま出力してしまっても良いですが， `StringBuilder` は `ToString()` の後も使われることを考慮し， `ToString()` の際に一旦メモリ領域を確保してから内部文字列をコピーする処理を行っています。
これは `ToString()` を一回行ったらお役御免になる使い方をしたい際に不利になることがあります。`string.Create()` メソッドを使えばこの余分なアロケーションを回避することができます。

## 最後に

まとめると，(1)文字列長が決まっており (2) `StringBuilder` で結合する場合でも一度しか `ToString` しない 場合は `string.Create()` メソッドを使うとメモリアロケーションを減らせるということになります。

この記事の最初のバージョンでは `Create()` メソッドの存在を知らずunsafe黒魔術を使って無理くりいじるものを公開していました。ご指摘ありがとうございます。

<details>
<summary>以前のバージョンで紹介していた手法</summary>

### 実際の結合処理

本手法は主に以下の流れからなっています
1. 最初に `string` インスタンスを生成
1. `string` を `Span<char>` に変換し，編集できる状態にする
1. `Span<char>` に編集処理を行い，結果 `string` も編集される

先ほどのサンプルに本手法を適用した場合はこのようになります。

<details open>
<summary>サンプル</summary>

```cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;

IEnumerable<int> range = Enumerable.Range(10, 90);
// 操作対象の文字列
// メモリアロケーションはここだけ
string combined = new string('\0', 2 * 90);

// combinedを表すSpan<char>を取得
Span<char> span = Unsafe.As<string, DummyString>(ref combined).AsSpan();
// 書き込む領域のオフセット
int offset = 0;

// 一つずつ数値を結合
foreach (int current in range)
{
    // 結合する文字列
    string currentStr = current.ToString();
    // 文字列をコピー
    currentStr.CopyTo(span[offset..]);

    offset += 2;
}

Console.WriteLine(combined);
Console.ReadKey();

internal sealed class DummyString
{
    private readonly int length; // 文字列長
    private char firstChar;      // 一文字目

    public int Length => length;

    public Span<char> AsSpan()
    {
        return MemoryMarshal.CreateSpan(ref firstChar, length);
    }
}
```

</details>

一つずつ説明していきます。

```cs
// 操作対象の文字列
// メモリアロケーションはここだけ
string combined = new string('\0', 2 * 90);
```

ここでは結合後の文字列のインスタンスを先に生成してしまっています。
メモリアロケーションを行うのはここだけです。
コンストラクタには特定の文字だけからなる特定の長さを持つ文字列を初期化するものを使用しています。
コンストラクタの第一引数ではヌル文字[^1]を指定しています。
<details open>
<summary>ヌル文字を指定する理由</summary>

[ `string` のコンストラクタのソースコード](https://github.com/dotnet/runtime/blob/release/7.0/src/libraries/System.Private.CoreLib/src/System/String.cs#L278-L295)は以下のようになっています。

```cs
/*
The MIT License (MIT)

Copyright (c) .NET Foundation and Contributors

All rights reserved.

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
*/

[MethodImpl(MethodImplOptions.InternalCall)]
[DynamicDependency("Ctor(System.Char,System.Int32)")]
public extern String(char c, int count);

private static string Ctor(char c, int count)
{
    if (count <= 0)
    {
        if (count == 0)
            return Empty;
        throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_NegativeCount);
    }

    string result = FastAllocateString(count);
    if (c != '\0')
    {
        SpanHelpers.Fill(ref result._firstChar, (uint)count, c);
    }
    return result;
}
```

`extern` 句など紛らわしいですが，実際の処理はコンストラクタの真下にある `Ctor(char c, int count)` メソッド内に記述されています。
ここではまず最初に `count` ぶんのメモリを確保して文字列インスタンスを初期化し，次に `c` で指定した文字でインスタンスを埋めます。
但し `FastAllocateString(int)` を行った段階で確保されたメモリは既にゼロ埋めがされているため， `c` にヌル文字を指定した場合は `c` で全文字を埋める処理が行わないのです。
本手法ではこれを利用し，第一引数にヌル文字を指定することで処理の高速化を図っています。

</details>

第二引数には最終的な文字列長を指定します。
このサンプルでは，各数値を文字列に変換した時に2文字になり，それが90個分あるため `2 * 90` としました。

`char[]` や `char*` から `string` を生成することも考えましたが， `string` のコンストラクタは何れも与えられた文字列をメモリアロケーションを行ってからそこへコピーする処理となっています。
そのため，メモリアロケーションを回避するためには `string` インスタンスを先に生成して，それを無理矢理いじる必要があるのです。

```cs
// combinedを表すSpan<char>を取得
Span<char> span = Unsafe.As<string, DummyString>(ref combined).AsSpan();
```

ここでは黒魔術を駆使して，本来Immutableである `string` をMutableである `Span<char>` に無理矢理変換しています。
まず最初に[ `Unsafe.As<TFrom, TTo>(ref TFrom)` メソッド](https://learn.microsoft.com/ja-jp/dotnet/api/system.runtime.compilerservices.unsafe.as?view=net-7.0#system-runtime-compilerservices-unsafe-as-2(-0@))で `string` を `DummyString` に変換しています。
`DummyString` クラスは以下のようになっています。

```cs
internal sealed class DummyString
{
    private readonly int length; // 文字列長
    private char firstChar;      // 一文字目

    public int Length => length;

    public Span<char> AsSpan()
    {
        return MemoryMarshal.CreateSpan(ref firstChar, length);
    }
}
```

この `DummyString` クラスは， `stirng` クラスとヒープ上のメモリ構造が同じになるようになっています（[参考](https://github.com/dotnet/runtime/blob/release/7.0/src/libraries/System.Private.CoreLib/src/System/String.cs#L42-L52)）。
こうすることによって `Unsafe.As<TFrom, To>(ref TFrom)` で `string` から変換された `DummyString` インスタンスが直接 `string` クラスのメンバ変数にアクセスできるようになります。
`DummyString` の `firstChar` は最初の文字を表しており，`ref firstChar` とすることで文字列全体の参照へ変換することができます[^2]。
これを利用して `AsSpan()` メソッドでは文字列を表す `Span<char>` を提供することができます。
[`MemoryMarshal.CreateSpan<T>(ref T, int)` メソッド](https://learn.microsoft.com/ja-jp/dotnet/api/system.runtime.interopservices.memorymarshal.createspan?view=net-7.0)は `ref T` とメモリ領域長から `Span<T>` を生成するメソッドです。
第一引数に先頭要素のポインタである `ref firstChar` を，第二引数に `length` を指定することで文字列のメモリ情報をそのまま表す `Span<char>` を生成することができるのです。

:::note warn
`Unsafe.As<TFrom, TTo>(ref TFrom)` メソッドでダミークラスに変換する処理は，対象クラスのメモリレイアウトが変更されることで破綻する可能性があります。
`string.AsSpan()` で生じる `ReadOnlySpan<char>` から `MemoryMarshal.GetReference<T>(Span<T>)` で `ref char` を引き抜く方がメモリレイアウト変更に対して堅牢です。
ご指摘ありがとうございます。
:::


```cs
// 書き込む領域のオフセット
int offset = 0;

// 一つずつ数値を結合
foreach (int current in range)
{
    // 結合する文字列
    string currentStr = current.ToString();
    // 文字列をコピー
    currentStr.CopyTo(span[offset..]);

    offset += 2;
}
```

ここでは先ほど生成した `Span<char>` の内容を実際に書き換えています。
やっていることは `string.CopyTo(Span<char>)` で文字列をコピーしているだけなので解説は省略します。

### おまけ：一文字ずつ結合する場合のプログラム

<details open>
<summary>サンプル</summary>

```cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.CompilerServices;

IEnumerable<int> range = Enumerable.Range(0, 100);
// 操作対象の文字列
// メモリアロケーションはここだけ
string combined = new string('\0', 100);

// combinedを表すSpan<char>を取得
ref char reference = ref Unsafe.As<string, DummyString>(ref combined).GetReference();
// 書き込む領域のオフセット
int offset = 0;

// 一つずつ数値を結合
foreach (int current in range)
{
    // 結合する文字
    char c = Math.Sqrt(current) % 1 == 0 ? '!' : '.';
    // 文字を設定
    Unsafe.Add(ref reference, offset++) = c;
}
```

</details>

0～99の値を一つ一つ判定し，値が平方数である場合は `!` を，それ以外で `.` を結合するものです。
`Span<char>.CopyTo(Span<char>)` の方が速いかどうかは計測していないのでアレですが，一文字ずつ埋める場合は `Unsafe.Add<T>(ref T, int)` でポインタっぽくいじれますよということだけ置いておきます。

</details>

## 参考資料

- [string.Createメソッド - Microsoftドキュメント](https://learn.microsoft.com/ja-jp/dotnet/api/system.string.create?view=net-7.0#system-string-create-1(system-int32-0-system-buffers-spanaction((system-char-0))))
- .NET7.0 ソースコード
  - [String.cs](https://github.com/dotnet/runtime/blob/release/7.0/src/libraries/System.Private.CoreLib/src/System/String.cs)
  - [StringBuilder.cs](https://github.com/dotnet/runtime/blob/release/7.0/src/libraries/System.Private.CoreLib/src/System/Text/StringBuilder.cs)
- 前バージョンで使った黒魔術メソッドの皆様
  - [Unsafe.As<TFrom, TTo>(ref TFrom)](https://learn.microsoft.com/ja-jp/dotnet/api/system.runtime.compilerservices.unsafe.as?view=net-7.0#system-runtime-compilerservices-unsafe-as-2(-0@))
  - [MemoryMarshal.CreateSpan<T>(ref T, int)](https://learn.microsoft.com/ja-jp/dotnet/api/system.runtime.interopservices.memorymarshal.createspan?view=net-7.0)

[^1]: `default(char)` と同じ
[^2]: 実際はメモリ上に二文字目以降が `firstChar` の後に配置されているため