[C#] StringBuilder 분석

natae·2022년 8월 30일

Concatenation Csharp String StringBuilder library

Csharp

목록 보기

5/9

개요

C#에서 String concatenation 대신 StringBuilder를 사용하도록 권장
StringBuilder는 내부적으로 어떻게 동작하는지 코드 확인
코드 양이 많기 때문에 주석, 예외처리 체크 등 제외하고 필요한 부분만 분석

코드

Program.cs

// See https://aka.ms/new-console-template for more information
using System.Text;

var sb = new StringBuilder();
sb.Append("Hello")
Console.WriteLine(sb.ToString());

분석1: 변수 및 생성자

StringBuilder.cs

internal char[] m_ChunkChars;
internal MyStringBuilder? m_ChunkPrevious;
internal int m_ChunkLength;
internal int m_ChunkOffset;
internal int m_MaxCapacity;

internal const int DefaultCapacity = 16;
internal const int MaxChunkSize = 8000;

public int Length
{
    get => m_ChunkOffset + m_ChunkLength;
}

public StringBuilder()
{
    m_MaxCapacity = int.MaxValue;
    m_ChunkChars = new char[DefaultCapacity];
}

String을 저장을 위해 기본적으로 char[]를 사용하며 청크 기본 용량는 16, 최대 용량은 8000
- 주석에 따르면, 청크 최대 용량이 클수록 신규 할당은 줄지만, 공간 낭비도 늘기에 힙영역을 고려하여 85Kbytes 이내로 설정
청크의 현재 길이(m_ChunkLength)는 별도로 관리, m_ChunkChars.Length는 용량을 반환하기 떄문

분석2: Append()

StringBuilder.cs

public StringBuilder Append(string? value)
{
    if (value is not null)
    {
        Append(valueCount: value.Length, value: ref value.GetRawStringData());
    }
 
    return this;
}

private void Append(ref char value, int valueCount)
{
    char[] chunkChars = m_ChunkChars;
    int chunkLength = m_ChunkLength;
 
    if (((uint)chunkLength + (uint)valueCount) <= (uint)chunkChars.Length)
    {
        ref char destination = ref Unsafe.Add(ref MemoryMarshal.GetArrayDataReference(chunkChars), chunkLength);
        if (valueCount <= 2)
        {
            destination = value;
            if (valueCount == 2)
            {
                Unsafe.Add(ref destination, 1) = Unsafe.Add(ref value, 1);
            }
        }
        else
        {
            Buffer.Memmove(ref destination, ref value, (nuint)valueCount);
        }
 
        m_ChunkLength = chunkLength + valueCount;
    }
    else
    {
        AppendWithExpansion(ref value, valueCount);
    }
}

"현재 용량 >= 현재 길이와 value의 길이의 합"인 경우
- 새로 할당할 필요가 없으며, m_ChunkChars 끝에 value을 붙임
  - Buffer.Memmove()는 내부적으로 Buffer.MemoryCopy와 동일하며, 메모리 블록을 복사함
"현재 용량 < 현재 길이와 value의 길이의 합"인 경우
- 새로 할당이 필요하여 AppendWithExpansion() 함수 호출

분석3: AppendWithExpansion()

StringBuilder.cs

private void AppendWithExpansion(ref char value, int valueCount)
{
    int firstLength = m_ChunkChars.Length - m_ChunkLength;
    if (firstLength > 0)
    {
        new ReadOnlySpan<char>(ref value, firstLength).CopyTo(m_ChunkChars.AsSpan(m_ChunkLength));
        m_ChunkLength = m_ChunkChars.Length;
    }
 
    int restLength = valueCount - firstLength;
    ExpandByABlock(restLength);
 
    new ReadOnlySpan<char>(ref Unsafe.Add(ref value, firstLength), restLength).CopyTo(m_ChunkChars);
    m_ChunkLength = restLength;
}

현재 여유있는 길이(firstLength)만큼 value에서 m_ChunkChars로 복사
부족한 길이(restLength)만큼 ExpandByABlock() 함수로 추가 할당 요청
부족한 길이만큼 value에서 m_ChunkChars로 복사

분석4: ExpandByABlock()

StringBuilder.cs

private void ExpandByABlock(int minBlockCharCount)
{
    int newBlockLength = Math.Max(minBlockCharCount, Math.Min(Length, MaxChunkSize));

    char[] chunkChars = GC.AllocateUninitializedArray<char>(newBlockLength);
 
    m_ChunkPrevious = new StringBuilder(this);
    m_ChunkOffset += m_ChunkLength;
    m_ChunkLength = 0;
 
    m_ChunkChars = chunkChars;
}

private StringBuilder(StringBuilder from)
{
    m_ChunkLength = from.m_ChunkLength;
    m_ChunkOffset = from.m_ChunkOffset;
    m_ChunkChars = from.m_ChunkChars;
    m_ChunkPrevious = from.m_ChunkPrevious;
    m_MaxCapacity = from.m_MaxCapacity;            
}

부족했던 공간만큼 새로 할당
기존 StringBuilder는 m_ChunkPrevious에 다 넘기고, 현재 StringBuilder는 초기화

분석5: ToString()

StringBuilder.cs

public override string ToString()
{    
    string result = string.FastAllocateString(Length);
    StringBuilder? chunk = this;
    do
    {
        if (chunk.m_ChunkLength > 0)
        {            
            char[] sourceArray = chunk.m_ChunkChars;
            int chunkOffset = chunk.m_ChunkOffset;
            int chunkLength = chunk.m_ChunkLength;
 
            Buffer.Memmove(
                ref Unsafe.Add(ref result.GetRawStringData(), chunkOffset),
                ref MemoryMarshal.GetArrayDataReference(sourceArray),
                (nuint)chunkLength);
        }
        chunk = chunk.m_ChunkPrevious;
    }
    while (chunk != null);
 
    return result;
}

m_ChunkPrevious를 반복하며 참조하면서, m_ChunkChars값을 result에 씀
더이상 m_ChunkPrevious가 남아있지 않으면 반환

추론

분석2에서 value의 길이가 2이하인 경우는 Buffer.Memmove() 대신 Unsafe.Add()로 붙이는데 속도가 더 빠른 것으로 추정

결론

StringBuilder는 현재 용량이 가득차면, 새로운 StringBuilder를 할당 받아 값을 계속 채우고, LinkedList처럼 다른 객체를 가르키면서 하나의 체인을 형성함
이로인해 매번 새로운 메모리를 할당 받고, 가비지를 만드는 String concatenation보다 메모리 측면에서 효율적임