Go to Qiita Advent Calendar 2024 Top
LoginSignup
11
6

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

@Funny_Silkie

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

Last updated at Posted at 2023-11-23

はじめに

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() メソッドはオーバーロードが複数ありますが，本記事で扱うのは型引数の用意されているものです。以降本記事で「Create() メソッド」とした場合はこの string.Create<TState>(int, TState, SpanAction<char, TState>) メソッドを指すとお考え下さい。

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

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. 結合後の文字列長が既に分かっている
  2. StringBuilder.ToString() を一度しか実行しない

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

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

StringBuilderの問題点

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

サンプル 
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();

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

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

  1. Append() で StringBuilder の内部文字列を拡張する際
  2. ToString() する際

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

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

最後に

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

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

以前のバージョンで紹介していた手法

実際の結合処理

本手法は主に以下の流れからなっています

  1. 最初に string インスタンスを生成
  2. string を Span<char> に変換し，編集できる状態にする
  3. Span<char> に編集処理を行い，結果 string も編集される

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

サンプル 
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);
    }
}

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

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

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

ヌル文字を指定する理由

string のコンストラクタのソースコードは以下のようになっています。

/*
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 で全文字を埋める処理が行わないのです。
本手法ではこれを利用し，第一引数にヌル文字を指定することで処理の高速化を図っています。

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

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

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

ここでは黒魔術を駆使して，本来Immutableである string をMutableである Span<char> に無理矢理変換しています。
まず最初に Unsafe.As<TFrom, TTo>(ref TFrom) メソッドで string を DummyString に変換しています。
DummyString クラスは以下のようになっています。

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 クラスとヒープ上のメモリ構造が同じになるようになっています（参考）。
こうすることによって Unsafe.As<TFrom, To>(ref TFrom) で string から変換された DummyString インスタンスが直接 string クラスのメンバ変数にアクセスできるようになります。
DummyString の firstChar は最初の文字を表しており，ref firstChar とすることで文字列全体の参照へ変換することができます2。
これを利用して AsSpan() メソッドでは文字列を表す Span<char> を提供することができます。
MemoryMarshal.CreateSpan<T>(ref T, int) メソッドは ref T とメモリ領域長から Span<T> を生成するメソッドです。
第一引数に先頭要素のポインタである ref firstChar を，第二引数に length を指定することで文字列のメモリ情報をそのまま表す Span<char> を生成することができるのです。

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

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

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

    offset += 2;
}

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

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

サンプル 
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;
}

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

参考資料

  1. default(char) と同じ ↩

  2. 実際はメモリ上に二文字目以降が firstChar の後に配置されているため ↩

11
6
6

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
11
6

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?