アロケーションなしで文字列を分割（Split）

`NonAllocStringSplitter`[<sup>※ソース</sup>](#nonallocstringsplitter-ソースコード) を使うと文字列を分割して解析する際のメモリ消費をゼロにすることが出来ます。また、マイクロ秒レベルですが処理も速くなります。

[【追記】](#追記) .NET 9 の `SpanSplitEnumerator` 実装が素晴らしい。


- [つかいかた](#つかいかた)
- [パフォーマンス比較](#パフォーマンス比較)
- [文字列の構築方法の比較](#文字列の構築方法の比較)
- [参考）メモリ確保のベンチマーク](#参考メモリ確保のベンチマーク)
- [`NonAllocStringSplitter` ソースコード](#nonallocstringsplitter-ソースコード)
- [おわりに](#おわりに)





# つかいかた

以下のようにスペースで区切られた `[数値] [数値] [数値] [数値]` という文字列から数値を取り出す処理を、ヒープアロケーション無しでスタック上で完結することが可能になります。

```cs
var text = "10.1  20.02  30  40.0000000000";

var split = new NonAllocStringSplitter(text, ' ');
if (split.Count != 4)
    throw new NotSupportedException("unsupported format: " + text);

// int/float.Parse には ReadOnlySpan<char> のオーバーロードがある！！
var left = float.Parse(split.Value0);
var top = float.Parse(split.Value1);
var width = float.Parse(split.Value2);
var height = float.Parse(split.Value3);

Console.WriteLine($"{left}, {top}, {width}, {height}");  // 文字列の再構築を省メモリにする必要がある（後述）
// --> 10.1, 20.02, 30, 40
```


イテレーションの為のインデクサーもあります。

```cs
// 拡張メソッド
split = "ABC, DEF, GHI, JKL".SplitNonAlloc(" ,");  // シーケンスで分割（一致しないので分割されない）
split = "ABC, DEF, GHI, JKL".SplitNonAlloc(" ,".AsSpan());  // 複数の文字で分割（' ' と ','）

// .Value0~9 以外にインデクサーもある
for (int i = 0; i < split.Count; i++)
{
    var span = split[i];
    Console.WriteLine(span.ToString());
}

// 出力結果
// ABC
// DEF
// GHI
// JKL
```

> ~~`ref struct` にはインターフェイスが実装できず、しかも `ReadOnlySpan<T>` はジェネリック型の型引数にはなれないので `foreach` に対応できない。~~

追記）そんなことはなかった。@juner さんの[コメント参照](https://qiita.com/sator_imaging/items/1393aa0efa3b064d77ec#comments)のこと。


--


<p><details lang="ja" --open><summary>URLの分解</summary>

一応速くなるしアロケも減ります。便利さはないので決め打ちの処理なら。

```cs
var fullURL = "https://www.com/file.html?opt=value&other=value#anchor";

var urlAndAnchor = new NonAllocStringSplitter(fullURL, '#');
string? anchor = (urlAndAnchor.Count == 2) ? urlAndAnchor.Value1.ToString() : null;

var urlAndOpts = new NonAllocStringSplitter(urlAndAnchor.Value0, '?');
string url = urlAndOpts.Value0.ToString();

(string name, string? value)[] options = new (string, string?)[0];
if (urlAndOpts.Count == 2)
{
    var opts = new NonAllocStringSplitter(urlAndOpts.Value1, '&');
    options = new (string, string?)[opts.Count];
    for (int i = 0; i < opts.Count; i++)
    {
        var nameAndValue = new NonAllocStringSplitter(opts[i], '=');
        options[i].name = nameAndValue.Value0.ToString();
        options[i].value = nameAndValue.Count == 2 ? nameAndValue.Value1.ToString() : null;
    }
}

// 出力！
Console.WriteLine(url);
foreach (var opt in options)
{
    Console.WriteLine(opt);
}
Console.WriteLine(anchor);
```

結果

```text
https://www.com/file.html
(opt, value)
(other, value)
anchor
```

<!------- End of Details JA Tag -------></details></p>




<!-- omit in toc -->
# 追記

知らなかっただけで .NET 8 にはそもそも `ReadOnlySpan<char>.Split(...)` が存在したようです。

`NonAllocStringSplitter` と違って `ReadOnlySpan<char>` ではなくジェネリック型の型引数になれる `Range` 構造体を使っています。なるほど。

https://qiita.com/abetakahiro123/items/93f4c9cf1f2eb15531c2


そして .NET 9 では `Range` 構造体の列挙子として実装することで、巨大な文字列を都度分割できるように。

https://github.com/dotnet/runtime/blob/main/src/libraries/System.Private.CoreLib/src/System/MemoryExtensions.cs#L4375


InlineArray 的実装じゃないので要素数制限もなく、巨大な文字列に対する処理も一括ではなく都度探索するので効率も良い。素晴らしい。





# パフォーマンス比較

- `SplitDefault` は `text.Split(..., StringSplitOptions.RemoveEmptyEntries)` を実行
- `NoParse_**` はループ内で `float.Parse` を行わない
- イテレーション毎のループ回数： 100 万回
- .NET Core 3 ＝ .NET Standard 2.1


<!-- omit in toc -->
## .NET Core 3（Unity 想定）

| Method                           | Mean          | Ratio | RatioSD | Allocated   |
|--------------------------------- |--------------:|------:|--------:|------------:|
| SplitDefault                     | 259,803.20 us | 1.000 |    0.02 | 584005600 B |
| SplitNonAlloc                    | 139,487.88 us | 0.537 |    0.01 |       136 B |
| SplitNonAllocIndexer             | 143,794.13 us | 0.554 |    0.01 |       136 B |
| SplitNonAllocMultiSplitter       | 182,857.11 us | 0.704 |    0.01 |       136 B |
| -
| NoParse_SplitDefault             | 195,166.22 us | 0.751 |    0.01 | 584000104 B |
| NoParse_SplitNonAlloc            |  82,745.65 us | 0.319 |    0.00 |       136 B |
| -
| DeconstructURL_Default_x100      |      36.67 us | 0.000 |    0.00 |     79304 B |
| DeconstructURL_NonAlloc_x100     |      19.14 us | 0.000 |    0.00 |     20904 B |



<!-- omit in toc -->
## .NET 8

.NET Core 3 よりメモリ消費が増えているのは謎。何度かベンチを走らせるとインデクサー（プロパティー）の方がフィールドより速いことがあるのも謎。

マイクロ秒レベルだけど `string.Split(...)` が速くなって `ref struct` のパフォーマンスが全体的に悪くなってる。

（高速化のために実装すべきインターフェイスか何かがある？）


| Method                       | Mean          | Ratio | RatioSD | Allocated   |
|----------------------------- |--------------:|------:|--------:|------------:|
| SplitDefault                 | 235,147.43 us | 1.000 |    0.02 | 584000400 B |
| SplitNonAlloc                | 145,767.82 us | 0.620 |    0.01 |       432 B |
| SplitNonAllocIndexer         | 149,174.27 us | 0.634 |    0.01 |       432 B |
| SplitNonAllocMultiSplitter   | 175,735.93 us | 0.747 |    0.01 |       432 B |
| -
| NoParse_SplitDefault         | 190,969.08 us | 0.812 |    0.02 | 584000400 B |
| NoParse_SplitNonAlloc        | 110,554.98 us | 0.470 |    0.01 |       432 B |
| -
| DeconstructURL_Default_x100  |      61.02 us | 0.000 |    0.00 |     79600 B |
| DeconstructURL_NonAlloc_x100 |      55.92 us | 0.000 |    0.00 |     21200 B |




<!-- omit in toc -->
## ベンチマークコード

<p><details lang="ja" --open><summary>見てみる</summary>

```cs
public const int LOOP_COUNT = 1_000_000;
public static string Text = ",,,,,,,ABCDEFG,,,HIJKLMN,OPQRSTU,VWXYZ,0,123,456,,789,,,,,,,";

[Benchmark(Baseline = true)]
public void SplitDefault()
{
    string[]? split = Array.Empty<string>();
    float value = float.MinValue;
    for (int i = 0; i < LOOP_COUNT; i++)
    {
        split = Text.Split(',', StringSplitOptions.RemoveEmptyEntries);
        value = float.Parse(split[split.Length - 1]);
    }

    OUTPUT = split[7].ToString();
    VALUE = value;
}

[Benchmark]
public void SplitNonAlloc()
{
    NonAllocStringSplitter split = default;
    float value = float.MinValue;
    for (int i = 0; i < LOOP_COUNT; i++)
    {
        split = new NonAllocStringSplitter(Text, ',');
        value = float.Parse(split.Value7) + 1;
    }

    OUTPUT = split.Value7.ToString();
    VALUE = value;
}

[Benchmark]
public void SplitNonAllocIndexer()
{
    NonAllocStringSplitter split = default;
    float value = float.MinValue;
    for (int i = 0; i < LOOP_COUNT; i++)
    {
        split = new NonAllocStringSplitter(Text, ',');
        value = float.Parse(split[7]) + 1;
    }

    OUTPUT = split[7].ToString();
    VALUE = value;
}

[Benchmark]
public void SplitNonAllocMultiSplitter()
{
    ReadOnlySpan<char> splitters = "~ ,";

    NonAllocStringSplitter split = default;
    float value = float.MinValue;
    for (int i = 0; i < LOOP_COUNT; i++)
    {
        split = new NonAllocStringSplitter(Text, splitters.AsSpan());
        value = float.Parse(split.Value7) + 2;
    }

    OUTPUT = split.Value7.ToString();
    VALUE = value;
}
```

<!------- End of Details JA Tag -------></details></p>





# 文字列の構築方法の比較

数値を取り出すまでは良いとして、最終的に文字列を再構築するにはどうするべきなのかを比較。

- 速度だけ見れば `stackalloc char[]` に直接書き込むのが最も良い
    - 数値のフォーマット指定が絡む場合は特に
    - .NET 8 なら補完文字列（`$"..."`）に対して以下のハンドラーが使われるのでそれで良い
- `DefaultInterpolatedStringHandler` ハンドラーが使えるなら使う
- フォーマット指定せずに足していくだけなら `StringBuilder` で良い
    - `sb.Clear()` せず `sb.Length = 0` して内部バッファーを再利用すると省メモリ
- 以下の方法はどちらもダメ（後述）
    - StringBuilder***StrFmt***: `sb.Append(floatVar.ToString("F5"))`
        - 速いがメモリ消費が多い
    - StringBuilder***Format***: `sb.AppendFormat("{0:F5}", floatVar)`
        - 遅いがメモリ消費が抑えられる
- `_Format/Fmt` は `{0:F5}` のように書式指定を与えているか否か
- `_FmtInv` は `.TryFormat(..., NumberFormatInfo.InvariantInfo)` を実行


<!-- omit in toc -->
## .NET Core 3

| Method                     | Mean     | Ratio | Allocated | Alloc Ratio |
|--------------------------- |---------:|------:|----------:|------------:|
| StackallocChar             | 445.7 us |  1.00 |  54.69 KB |        1.00 |
| StringInterpolate          | 590.4 us |  1.32 | 203.13 KB |        3.71 |
| StringBuilder              | 455.9 us |  1.02 | 156.25 KB |        2.86 |
| StringBuilderReuse         | 448.6 us |  1.01 |  54.69 KB |        1.00 |
| StringBuilderHelper        | 443.3 us |  0.99 |  54.69 KB |        1.00 |
| -
| StackallocChar_Format      | 802.7 us |  1.80 | 101.56 KB |        1.86 |
| StringInterpolate_Format   | 979.8 us |  2.20 | 250.01 KB |        4.57 |
| StringBuilderReuse_Format  | 886.6 us |  1.99 | 195.32 KB |        3.57 |
| StringBuilderReuse_StrFmt  | 820.0 us |  1.84 | 257.81 KB |        4.71 |
| StringBuilderHelper_Format | 848.0 us |  1.90 | 101.56 KB |        1.86 |
| StringBuilderHelper_FmtInv | 857.4 us |  1.92 | 101.57 KB |        1.86 |




<!-- omit in toc -->
## .NET 8

メモリ消費は違うが処理速度はほぼ横並び。何かしら書式指定（`ISpanFormattable.TryFormat(..., "F5")`）した方が速いのは面白い。

| Method                     | Mean     | Ratio | Allocated | Alloc Ratio |
|--------------------------- |---------:|------:|----------:|------------:|
| StackallocChar             | 286.1 us |  1.00 |  54.69 KB |        1.00 |
| StringInterpolate          | 297.1 us |  1.04 |  54.69 KB |        1.00 |
| StringBuilder              | 285.9 us |  1.00 | 156.25 KB |        2.86 |
| StringBuilderReuse         | 274.2 us |  0.96 |  54.69 KB |        1.00 |
| StringBuilderHelper        | 275.2 us |  0.96 |  54.69 KB |        1.00 |
| -
| StackallocChar_Format      | 258.2 us |  0.90 | 101.56 KB |        1.86 |
| StringInterpolate_Format   | 266.3 us |  0.93 | 101.56 KB |        1.86 |
| StringBuilderReuse_Format  | 334.7 us |  1.17 | 195.31 KB |        3.57 |
| StringBuilderReuse_StrFmt  | 273.6 us |  0.96 | 257.81 KB |        4.71 |
| StringBuilderHelper_Format | 268.5 us |  0.94 | 101.56 KB |        1.86 |
| StringBuilderHelper_FmtInv | 271.4 us |  0.95 | 101.56 KB |        1.86 |




<!-- omit in toc -->
## `StringBuilder` の再利用方法

Unity の事も考えると StringBuilder の再利用を行うのが一番良い。

以下はスコープ内で `.ToString()` まで完結する前提のテンプレート。一見同一スコープ内に見える非同期メソッド内で await 越えした場合は未定義動作になるやり方なので注意。

```cs
[ThreadStatic] static StringBuilder? ts_sb;

string GetString()
{
    var sb = (ts_sb ??= new());
    sb.Length = 0;  // .Clear() すると内部バッファーが消される

    ...

    return sb.ToString();
}
```

<p><details lang="ja" --open><summary>微妙なヘルパー</summary>

ヘルパーに対して stackalloc のようにスコープ外に持ち出せないようにする制約を与えたいが、ref 構造にするだけだとスタック上に限定する制約しか与えられない。一応 `yield` `await` 越え出来なくなってラムダ式にも渡せなくなるから複数のメソッドから同時に ThreadStatic なビルダーを使われる危険性は防げる（ハズ）

```cs
using System;
using System.Text;

class Program
{
    static void Main()
    {
        var sb = GetBuilder();
    }

    static StringBuilderHelper GetBuilder()
    {
        var sb = new StringBuilderHelper(0);
        return sb;  // スコープ外に持ち出せる
    }
}

public readonly ref struct StringBuilderHelper
{
    [ThreadStatic] static StringBuilder? ts_sb;

    readonly StringBuilder sb;
    public StringBuilderHelper(int initialCapacity)
    {
        this.sb = (ts_sb ??= new(initialCapacity));
        this.sb.Length = 0;
    }

    // StringBuilder メソッドのエイリアスを定義（内部のビルダーを公開しない為に必要）

    // 自前で内部バッファーを操作するのもありか。ISpanFormattable が使えると楽だが。。。
    public void Append(int val, ReadOnlySpan<char> format...) { ... }
    public void Append(float val, ReadOnlySpan<char> format...) { ... }
    public void Append(double val, ReadOnlySpan<char> format...) { ... }
    // あいまいさの回避が難しい
    public void Append<T>(...) where T : IFormattable { ... }
    public void Append(object val)) { var s = val.ToString(); ... }
    public void NewLine() { ... }
}
```

<!------- End of Details JA Tag -------></details></p>

自前でバッファーを確保するなら、容量を拡張するたびに中身を詰め変えるよりは `ReadOnlySequence<T>` を使った方がプール（`MemoryPool<T>`）の回転率的にも良さそう。

https://qiita.com/skitoy4321/items/0fc4dc72bc50dabba92b



<!-- omit in toc -->
## Unity と `ISpanFormattable`

.NET Standard 2.1（Unity）の数値型には `.TryFormat` は実装されているが肝心の `ISpanFormattable` インターフェイスが存在しない。

なので以下の要領で `StringBuilder` の拡張メソッドを実装しておくと、Unity でも `DefaultInterpolatedStringHandler` と同等のパフォーマンスと省メモリを達成できる。


```cs
// Append** はオーバーロードが多すぎるのでネームスペースが違っても提案に表示されやすい名前にしておくと良い
public static StringBuilder AppendFormatFast(this StringBuilder sb, float val, ReadOnlySpan<char> format)
{
    Span<char> buffer = stackalloc char[64];
    val.TryFormat(buffer, out var written, format);

    sb.Append(buffer.Slice(0, written));
    return sb;
}

// Unity でも `where T : ISpanFormattable` が使えれば。。。
public static StringBuilder AppendFormatFast<T>(this StringBuilder sb, T val, ReadOnlySpan<char> format)
    where T : ISpanFormattable
{
    Span<char> buffer = stackalloc char[64];
    val.TryFormat(buffer, out var written, format);

    sb.Append(buffer.Slice(0, written));
    return sb;
}
```

StringBuilder 拡張メソッドを実装すべき型一覧

https://learn.microsoft.com/ja-jp/dotnet/api/system.ispanformattable

https://learn.microsoft.com/ja-jp/dotnet/api/system.iutf8spanformattable


--

またはフォーマッターで良く求められる型リストを参考に

https://learn.microsoft.com/ja-jp/dotnet/api/system.buffers.text.utf8formatter.tryformat





<!-- omit in toc -->
## 一番パフォーマンスが良かった実装

ほんの少しだけ速いけどあまりに面倒なので、StringBuilder の再利用とフォーマット指定の拡張メソッドの組み合わせで十分。

```cs
Span<char> buffer = stackalloc char[256];
int consumed = 0;
int written;

left.TryFormat(buffer.Slice(consumed), out written, "F5");
consumed += written;

", ".AsSpan().CopyTo(buffer.Slice(consumed));
consumed += 2;

top.TryFormat(buffer.Slice(consumed), out written, "F5");
consumed += written;

", ".AsSpan().CopyTo(buffer.Slice(consumed));
consumed += 2;

width.TryFormat(buffer.Slice(consumed), out written, "F5");
consumed += written;

", ".AsSpan().CopyTo(buffer.Slice(consumed));
consumed += 2;

height.TryFormat(buffer.Slice(consumed), out written, "F5");
consumed += written;


result = buffer.Slice(0, consumed).ToString();
```



# 参考）メモリ確保のベンチマーク

https://ikorin2.hatenablog.jp/entry/2021/12/20/225208

https://learn.microsoft.com/ja-jp/dotnet/api/system.gc.allocateuninitializedarray





<a id="non-alloc-string-splitter"></a>

# `NonAllocStringSplitter` ソースコード

実装は `[System.Runtime.CompilerServices.InlineArray(10)]` に近く、分割結果が 10 個以上の場合は例外が発生します。

https://learn.microsoft.com/ja-jp/dotnet/csharp/whats-new/csharp-12#inline-arrays

--

https://gist.github.com/sator-imaging/e1f9559b483a8c49b9af7cccd713f282





# おわりに

~~`ref struct` はスタック上にしか置けない制約があるということで、`stackalloc char[] { ... }` を渡しても大丈夫だと思うんですが以下のコードはエラーが出ます。何故？~~


```cs
split = "ABC, DEF, GHI, JKL".SplitNonAlloc(stackalloc char[] { ' ', ',' });

// これもダメ
ReadOnlySpan<char> splitters = stackalloc char[] { ' ', ',' };
split = "ABC, DEF, GHI, JKL".SplitNonAlloc(splitters);
```

~~（Unity から起動した Visual Studio の場合は IDE 上ではエラーが出ないけどコンパイルでコケる）~~

用意したオーバーロードの引数があいまいで呼び出し先を解決できていないだけだった。



--

以上です。お疲れ様でした。