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

Last updated at 2024-09-10Posted at 2024-09-09

NonAllocStringSplitter^※ソースを使うと文字列を分割して解析する際のメモリ消費をゼロにすることが出来ます。また、マイクロ秒レベルですが処理も速くなります。

【追記】 .NET 9 の SpanSplitEnumerator 実装が素晴らしい。

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

つかいかた

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

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

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

// 拡張メソッド
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 さんのコメント参照のこと。

URLの分解

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

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);

結果

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

追記

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

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

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

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

パフォーマンス比較

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

.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

.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

ベンチマークコード

見てみる

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;
}

文字列の構築方法の比較

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

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

.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

.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

`StringBuilder` の再利用方法

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

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

[ThreadStatic] static StringBuilder? ts_sb;

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

    ...

    return sb.ToString();
}

微妙なヘルパー

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

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() { ... }
}

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

Unity と `ISpanFormattable`

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

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

// 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 拡張メソッドを実装すべき型一覧

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

一番パフォーマンスが良かった実装

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

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();

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

`NonAllocStringSplitter` ソースコード

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

おわりに

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

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

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

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

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

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

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

つかいかた

追記

パフォーマンス比較

.NET Core 3（Unity 想定）

.NET 8

ベンチマークコード

文字列の構築方法の比較

.NET Core 3

.NET 8

StringBuilder の再利用方法

Unity と ISpanFormattable

一番パフォーマンスが良かった実装

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

NonAllocStringSplitter ソースコード

おわりに

`StringBuilder` の再利用方法

Unity と `ISpanFormattable`

`NonAllocStringSplitter` ソースコード