C++ string 的兩種實做

Share on:

本文內容採用創用 CC 姓名標示-非商業性-相同方式分享 3.0 台灣 授權條款授權.

最近在玩一些比較老舊的程式碼的時候,發現 g++ 5 前後的 sizeof(std::string) 的大小有相當大的差異,在 64-bit 平台下,有 g++ 5 之前是 8 bytes,之後是 32 bytes。這其中的差異蠻有趣的,尤其是舊版的 string 只要一個 pointer 的大小,於是就找了一下資料並記錄下來。

從 API 來從推論 std::string 的實做,最低限度要有這三個元素:

  • 字串資料的指標 (char* string::data())
  • 字串大小 (size_t string::size())
  • 字串指向的指標容量 (size_t string::capacity())

寫成程式就是這樣:

1struct string {
2	char *data;
3	size_t size;
4	size_t capacity;
5};

在 64-bit 系統中,這應該是用掉 24 bytes,到底怎麼會跑出 24 或是 8 bytes?這是因為 g++ stl 實做中的效能都經過了大量的優化,兩種大小對應到不同的優化實做,本文接著討論兩種(簡化過的)實做的不同。

g++ 5 之後的 std::string

長這樣:

1struct string {
2	char *data;
3	size_t size;
4	union {
5		size_t capacity;
6		char small_buffer[16];
7	};
8};

可以看到 capacity 跟 16 bytes 的 buffer 共用一個空間,這個空間可以給小於 16 bytes 的字串使用,也就是說對於長度是 15 以下的字串,data 直接指向這個位置:

1string::string(const size_t n) {
2	data = n < 16 ? this->small_buffer : new char[n+1];
3}

而要知道 capacity() 就必須先判斷 data 到底是指向 small_buffer 還是其他地方:

1size_t string::capacity() {
2	return data == this->small_buffer ? 16 : this->capacity;
3}

因為一般程式裡面很多 string 都很短,用這個小小的 buffer 可以避免大量的 new/delete。至於為什麼 buffer size 是選 16 呢,我猜可能是因為 32 bytes 在很多 CPU 裡面都有單一指令(x86 lea 或是 ARM barrel shifter)可以快速計算。

g++ 5 之前的 std::string

8 bytes 的結構長這樣:

1struct string {
2	struct SizeAndCapacity {
3		size_t size;
4		size_t capacity;
5	}
6	char *data;
7};

等等,為什麼一個 string 只需要存 data 呢?這樣要怎麼知道字串大小?答案就是把他藏在 data 指向的空間的前面

1string::string(const size_t n) {
2	data = new char[sizeof(SizeAndCapacity)+n] + sizeof(SizeAndCapacity);
3}

這樣當我們需要 size 或是 capacity 的時候,只要去前面挖就好,在 stl 裡面的寫法也蠻簡潔的:

1size_t string::size() {
2	return reinterpret_cast<SizeAndCapacity*>(data)[-1].size;
3}

但是這樣每次要拿 size 的時候,都需要 dereference,而且也沒辦法消除小字串造成的 new/delete,所以這個作法就慢慢消失了。

補充

g++ 5 之前的 string 其實有實做 copy-on-write 機制,但是因為我發現在文章中不討論這個好像也不太會怎樣,而且 C++11 之後明文禁止 copy-on-write 實做了,所以就沒有在本文提到。