源碼上看 .NET 中 StringBuilder 拼接字元串的實現
前幾天寫了一篇StringBuilder與TextWriter二者之間區別的文章（鏈接）。當時提了一句沒有找到相關源碼，於是隨後有很多熱心人士給出了相關的源碼鏈接（鏈接），感謝大家。這幾天抽了點時間查看了下StringBuilder是如何動態構造字元串的，發現在.NET Core中字元串的構建似乎和我原先猜想的並不完全一樣，故此寫了這篇文章，如有錯誤，歡迎指出。
StringBuilder欄位和屬性
字元數組
明確一點的是，StringBuilder的內部確實使用字元數組來管理字元串資訊的，這一點上和我當時的猜測是差不多的。相較於字元串在大多數情況下的不變性而言，字元數組有其優點，即修改字元數組內部的數據不會全部重新創建字元數組（字元串的不變性）。下面是StringBuilder的部分源碼，可以看到，內部採用m_ChunkChars欄位存儲字元數組資訊。
public sealed class StringBuilder
{
internal char[] m_ChunkChars;
...
}
然而，採用字元數組並不是沒有缺點，數組最大的缺點就是在在使用前就需要指定它的空間大小，這種固定大小的數組空間不可能有能力處理多次的字元串拼接，總有某次，數組中的空餘部分塞不下所要拼接的字元串。如果某次拼接的字元串超過數組的空閑空間時，一種易想到做到的方法就是開闢一個更大的空間，並將原先的數據複製過去。這種方法能夠保證數組始終是連續的，然而，它的問題在於，複製是一個非常耗時的操作，如非必要，儘可能地降低複製的頻率。在.NET Core中，StringBuilder採用了一個新方法避免了複製操作。
單鏈表
為了能夠有效地提高性能，StringBuilder採用鏈表的形式規避了兩個字元數組之間的複製操作。在其源程式碼中，可以發現每個StringBuilder內部保留對了另一個StringBuilder的引用。
public sealed class StringBuilder
{
internal StringBuilder? m_ChunkPrevious;
...
}
在StringBuilder中，每個對象都維護了一個m_ChunkPrevious引用，按欄位命名的意思來說，就是每個類對象都維護指向前一個類對象的引用。這一點和我們常見的單鏈表結構有點一點不太一樣，常見的單鏈表結構中每個節點維護的是指向下一個節點的引用，這和StringBuilder所使用的模式剛好相反，挺奇怪的。整理下，這部分有兩個問題：
- 為什麼說採用單鏈表能避免複製操作？
- 為什麼採用逆向鏈表，即每個節點保留指向前一個節點的引用？
對於第一個問題，試想下，如果又有新的字元串需要拼接且其長度超過字元數組空閑的容量時，可以考慮新開闢一個新空間專門存儲超額部分的數據。這樣，先前部分的數據就不需要進行複製了，但這又有一個新問題，整個數據被存儲在兩個不相連的部分，怎麼關聯他們，採用鏈表的形式將其關聯是一個可行的措施。以上就是StringBuilder拼接字元串最為核心的部分了。
那麼，對於第二個問題，採用逆向鏈表對的好處是什麼？這裡我給出的原因屬於我個人的主觀意見，不一定對。從我平時使用上以及一些開源類庫中來看，對StringBuilder使用最廣泛的功能就是拼接字元串了，即向尾部添加新數據。在這個基礎上，如果採用正向鏈表（每個節點保留下一個節點的引用），那麼多次拼接字元串在數組容量不夠的情況下，勢必需要每次循環找到最後一個節點並添加新節點，時間複雜度為O(n)。而採用逆向鏈表，因為用戶所持有的就是最後一個節點，只需要在當前節點上做些處理就可以添加新節點，時間複雜度為O(1)。因此，StringBuilder內的字元數組可以說是字元串的一個部分，也被稱為Chunk。
舉個例子，如果類型為
Stringbuilder變數sb內已經保存了HELLO字元串，再添加WORLD時，如果字元數組滿了，再添加就會構造一個新StringBuilder節點。注意的是調用類方法不會改變當前變數sb指向的對象，因此，它會移動內部的字元數組引用，並將當前變數的字元數組引用指向WORLD。下圖中的左右兩圖是添加前後的說明圖，其中黃色StringBuilder是同一個對象。
當然，採用鏈表並非沒有代價。因為鏈表沒有隨機讀取的功能。因此，如果向指定位置添加新數據，這反而比只使用一個字元數組來得慢。但是，如果前面的假設沒錯的話，也就是最頻繁使用的是尾部拼接的話，那麼使用鏈表的形式是被允許的。根據使用場景頻率的不同，提供不同的實現邏輯。
各種各樣的長度
剩下來的部分，就是描述各種各樣的長度及其他數據。主要如下：
public sealed class StringBuilder
{
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;
}
...
}
m_ChunkLength描述當前Chunk存儲資訊的長度。也就是存儲了字元數據的長度，不一定等於字元數組的長度。m_ChunkOffset描述當前Chunk在整體字元串中的起始位置，方便定位。m_MaxCapacity描述構建字元串的最大長度，通常設置為int最大值。DefaultCapacity描述默認設置的空間大小，這裡設置的是16。MaxChunkSize描述Chunk的最大長度，也就是Chunk的容量。Length屬性描述的是內部保存整體字元串的長度。
構造函數
上述講述的是StringBuilder的各個欄位和屬性的意義，這裡就深入看下具體函數的實現。首先是構造函數，這裡僅列舉本文所涉及到的幾個構造函數。
public StringBuilder()
{
m_MaxCapacity = int.MaxValue;
m_ChunkChars = new char[DefaultCapacity];
}
public StringBuilder(string? value, int startIndex, int length, int capacity)
{
...
m_MaxCapacity = int.MaxValue;
if (capacity == 0)
{
capacity = DefaultCapacity;
}
capacity = Math.Max(capacity, length);
m_ChunkChars = GC.AllocateUninitializedArray<char>(capacity);
m_ChunkLength = length;
unsafe
{
fixed (char* sourcePtr = value)
{
ThreadSafeCopy(sourcePtr + startIndex, m_ChunkChars, 0, length);
}
}
}
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;
...
}
這裡選出了三個和本文關係較為緊密的構造函數，一個個分析。
- 首先是默認構造函數，該函數沒有任何的輸入參數。程式碼中可以發現，其分配的長度就是16。也就是說不對其做任何指定的話，默認初始長度為16個Char型數據，即32位元組。
- 第二個構造函數是當構造函數傳入為字元串時所調用的，這裡我省略了在開始最前面的防禦性程式碼。這裡的構造過程也很簡單，比較傳入字元串的大小和默認容量
DefaultCapacity的大小，並開闢二者之間最大值的長度，最後將字元串複製到數組中。可以發現的是，這種情況下，初始字元數組的長度並不總是16，畢竟如果字元串長度超過16，肯定按照更長的來。 - 第三個構造函數專門用來構造
StringBuilder的節點的，或者說是StringBuilder的複製，即原型模式。它主要用在容量不夠構造新的節點，本質上就是將內部數據全部賦值過去。
從前兩個構造函數可以看出，如果第一次待拼接的字元串長度超過16，那麼直接將該字元串以構造函數的參數傳入比構建默認
StringBuilder對象再使用Append方法更加高效，畢竟默認構造函數只開闢了16個char型空間。
Append方法
這裡主要看StringBuilder Append(char value, int repeatCount)這個方法（位於第710行）。該方法主要是向尾部添加char型字元value，一共添加repeatCount個。
public StringBuilder Append(char value, int repeatCount)
{
...
int index = m_ChunkLength;
while (repeatCount > 0)
{
if (index < m_ChunkChars.Length)
{
m_ChunkChars[index++] = value;
--repeatCount;
}
else
{
m_ChunkLength = index;
ExpandByABlock(repeatCount);
Debug.Assert(m_ChunkLength == 0);
index = 0;
}
}
m_ChunkLength = index;
AssertInvariants();
return this;
}
這裡僅列舉出部分程式碼，起始的防禦性程式碼以及驗證程式碼略過。看下其運行邏輯：
- 依次循環當前字元
repeatCount次，對每一次執行以下邏輯。（while大循環） - 如果當前字元數組還有空位時，則直接向內部進行添加新數據。（if語句命中部分）
- 如果當前字元數組已經被塞滿了，首先更新
m_ChunkLength值，因為數組被塞滿了，因此需要下一個數組來繼續放數據，當前的Chunk長度也就是整個字元數組的長度，需要更新。其次，調用了ExpandByABlock(repeatCount)函數，輸入參數為更新後的repeatCount數據，其做的就是構建新的節點，並將其掛載到鏈表上。 - 更新
m_ChunkLength值，記錄當前Chunk的長度，最後將本身返回。
接下來就是ExpandByABlock方法的實現。
private void ExpandByABlock(int minBlockCharCount)
{
...
int newBlockLength = Math.Max(minBlockCharCount, Math.Min(Length, MaxChunkSize));
...
// Allocate the array before updating any state to avoid leaving inconsistent state behind in case of out of memory exception
char[] chunkChars = GC.AllocateUninitializedArray<char>(newBlockLength);
// Move all of the data from this chunk to a new one, via a few O(1) pointer adjustments.
// Then, have this chunk point to the new one as its predecessor.
m_ChunkPrevious = new StringBuilder(this);
m_ChunkOffset += m_ChunkLength;
m_ChunkLength = 0;
m_ChunkChars = chunkChars;
AssertInvariants();
}
和上面一樣，僅列舉出核心功能程式碼。
- 設置新空間的大小，該大小取決於三個值，從當前字元串長度和Chunk最大容量取較小值，然後從較小值和輸入參數長度中取最大值作為新Chunk的大小。值得注意的是，這裡當前字元串長度通常是Chunk已經被塞滿的情況下，可以理解成所有Chunk的長度之和。
- 開闢新空間。
- 通過上述最後一個構造函數，構造向前的節點。當前節點仍然為最後一個節點，更新其他值，即偏移量應該是原先偏移量加上一個Chunk的長度。清空當前Chunk的長度以及將新開闢空間給Chunk引用。
對於Append(string? value)這個函數的實現功能和上述說明是差不多的，基本都是新數據先往當前的字元數組內塞，如果塞滿了就添加新節點並刷新當前字元數組數據再塞。詳細的功能可以從L802開始看。這裡不做過多說明。
驗證
當然，以上只是閱讀程式碼的流程，具體是否正確還可以做點測試來驗證。這裡我做了一個小測試demo。
var sb = new StringBuilder();
sb.Append('1', 10);
sb.Append('2', 6);
sb.Append('3', 24);
sb.Append('4', 15);
sb.Append("hello world");
sb.Append("nice to meet you");
Console.WriteLine($"結果：{sb.ToString()}");
var p = sb;
char[] data;
Type type = sb.GetType();
int count = 0;
while (p != null)
{
count++;
data = (char[])type.GetField("m_ChunkChars", BindingFlags.NonPublic | BindingFlags.Instance).GetValue(p);
Console.WriteLine($"倒數第{count}個StringBuilder內容:{new string(data)}");
p = (StringBuilder)type.GetField("m_ChunkPrevious", BindingFlags.NonPublic | BindingFlags.Instance).GetValue(p);
}
這裡主要做的是利用Append方法添加不同的數據並將最終結果輸出。考慮到內部的細節並沒有對外公開，只能通過反射的操作來獲取，通過遍歷每一個StringBuilder的節點，反射獲取內部的字元數組並將其輸出。最終的結果如下。
這裡分析下具體的過程：
- 第一句
sb = new StringBuilder()。從之前的構造函數程式碼內可以得知，無參構造函數會生成一個16長度的字元數組。 - 第二句
sb.Append('1', 10)。這句話意思是向sb內添加10個1字元，因為添加的長度小於給定的默認值16，因此直接將其添加即可。 - 第三句
sb.Append('2', 6)。在經過上面添加操作後，當前字元數組還剩6個空間，剛好夠塞，因此直接將6個2字元直接塞進去。 - 第四句
sb.Append('3', 24)。在添加字元3之前，StringBuilder內部的字元數組就已經沒有空間了。為此，需要構造新的StringBuilder對象，並將當前對象內的數據傳過去。對於當前對象，需要創建新的字元數組，按照之前給出的規則，當前Chunk之和（16）和Chunk長度（8000）取最小值（16），最小值（16）和輸入字元串長度（24）取最大值（24）。因此，直接創建24個字元空間並存下來。此時，sb對象有一個前置節點。 - 第五句
sb.Append('4', 15)。上一句程式碼只創建了長度為24的字元數組，因此，新數據依然無法再次塞入。此時，依舊需要創建新的StringBuilder節點，按照同樣的規則，取當前所有Chunk之和（16+24=40）。因此，新字元數組長度為40，內部存了15個字元數據4。sb對象有兩個前置節點。 - 第六句
sb.Append("hello world")。這個字元串長度為11，當前字元數組能完全放下，則直接放下。此時字元數組還空餘14個空間。 - 第七句
sb.Append("nice to meet you")。這個字元串長度為16，可以發現超過了剩餘空間，首先先填充14個字元。之後多出的2個，則按照之前的規則再構造新的節點，新節點的長度為所有Chunk之和（16+24+40=80），即有80個存儲空間。當前Chunk只存儲最後兩個字元ou。sb對象有3個前置節點。符合最終的輸出結果。
總結
總的來說，採用定長的字元數組來保存不定長的字元串，不可能完全避免所添加的數據超出剩餘空間這樣的情況，重新開闢新空間並複製原始數據過於耗時。StringBuilder採用鏈表的形式取消了數據的複製操作，提高了字元串連接的效率。對於StringBuilder來說，大部分的操作都在尾部添加，採用逆向鏈表是一個不錯的形式。當然StringBuilder這個類本身有很多複雜的實現，本篇只是介紹了Append方法是如何進行字元串拼接的。
