{"id":109742,"date":"2024-05-10T07:00:00","date_gmt":"2024-05-10T14:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=109742"},"modified":"2024-05-13T14:23:38","modified_gmt":"2024-05-13T21:23:38","slug":"an-informal-comparison-of-the-three-major-implementations-of-stdstring","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20240510-00\/?p=109742","title":{"rendered":"An informal comparison of the three major implementations of std::string<\/CODE>"},"content":{"rendered":"

[Note: This article has been updated since original publication.]<\/p>\n

We saw some time ago that the three major implementations of std::string<\/code> are all quite different<\/a>. To summarize:<\/p>\n

\/\/ gcc\r\nstruct string\r\n{\r\n    char* ptr;\r\n    size_t size;\r\n    union {\r\n        size_t capacity;\r\n        char buf[16];\r\n    };\r\n\r\n    bool is_large() { return ptr != buf; }\r\n    auto data() { return ptr; }\r\n    auto size() { return size; }\r\n    auto capacity() { return is_large() ? capacity : 15; }\r\n};\r\n\r\n\/\/ msvc\r\nstruct string\r\n{\r\n    union {\r\n        char* ptr;\r\n        char buf[16];\r\n    };\r\n    size_t size;\r\n    size_t capacity;\r\n\r\n    bool is_large() { return capacity > 15; }\r\n    auto data() { return is_large() ? ptr : buf; }\r\n    auto size() { return size; }\r\n    auto capacity() { return capacity; }\r\n};\r\n\r\n\/\/ clang\r\nunion string\r\n{\r\n    struct {\r\n        size_t capacity;\r\n        size_t size;\r\n        char* ptr;\r\n    } large;\r\n\r\n    struct {\r\n        unsigned char is_large:1;\r\n        unsigned char size:7;\r\n        char buf[sizeof(large) - 1];\r\n    } small;\r\n\r\n    bool is_large() { return small.is_large; }\r\n    auto data() { return is_large() ? large.ptr : small.buf; }\r\n    auto size() { return is_large() ? large.size : small.size; }\r\n    auto capacity() { return is_large() ? large.capacity : sizeof(large) - 2; }\r\n};\r\n<\/pre>\n
Note that these implementations above are for expository purposes only. The actual implementations are far more complicated. (For example, the real implementations are uglified, and they have to store the allocator somewhere.)<\/p>\n
Update<\/b>: In the original version of this article, I got the sense of the “small\/large” bit backward in the clang implementation. This in turn led to redoing the code generation and new code golfing results.<\/p>\n
We’ll compare these versions based on the complexity of some commonly-used operations.<\/p>\n
Detecting whether the string is small or large is a single member comparison with msvc and clang, but on gcc, it involves comparing a member against the address of another member, so it will take an extra instruction to calculate that address.<\/p>\n\n\n\n\n
gcc is_large<\/th>\nmsvc is_large<\/th>\nclang is_large<\/th>\n<\/tr>\n
lea rdx, [rcx].buf<\/code>
\ncmp rdx, [rcx].ptr<\/code>
\njnz large<\/code><\/td>\n		cmp [rcx].capacity, 15<\/code>
\nja large<\/code><\/td>\n		test [rcx].is_large, 1<\/code>
\njnz large<\/code><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
Note: gcc could have shaved an instruction by reordering the members so that the buf<\/code> comes first (thereby avoiding the need to calculate its address). On the other hand, it increases the cost of accessing ptr<\/code> on some processors: On the x86 family, it forces a larger encoding because the offset is nonzero. On the Itanium, it requires two instructions because the Itanium cannot perform an offset load in a single instruction. On most other processors, the offset can be folded into the load instruction at no extra cost. My guess is that gcc biased their design to optimize for x86.<\/p>\n
On the other hand, gcc wins the race to access the data()<\/code>, since the ptr<\/code> is always valid, and that’s probably why they chose their design.<\/p>\n\n\n\n\n
gcc data()<\/th>\nmsvc data()<\/th>\nclang data()\u00b9<\/th>\n<\/tr>\n
mov rdx, [rcx].ptr<\/code><\/td>\nlea rdx, [rcx].buf<\/code>
\ncmp [rcx].capacity, 15<\/code>
\ncmova rdx, [rdx]<\/code><\/td>\n		lea rdx, [rcx].small.buf<\/code>
\ntest [rcx].small.is_large, 1<\/code>
\njz @1<\/code>
\nmov rdx, [rcx].large.ptr<\/code>
\n@1:<\/code><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
The clang implementation also has extra work to calculate the size.<\/p>\n\n\n\n\n
gcc size()<\/th>\nmsvc size()<\/th>\nclang size()\u00b2<\/th>\n<\/tr>\n
mov rdx, [rcx].size<\/code><\/td>\nmov rdx, [rcx].size<\/code><\/td>\nmovzx eax, [rcx].small.is_large<\/code>
\ntest al, 1<\/code>
\njz @1<\/code>
\nmov rax, [rcx].large.size<\/code>
\njmp @2<\/code>
\n@1: shr eax, 1<\/code>
\n@2:<\/code><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
A special case of checking the size is checking whether the string is empty.<\/p>\n\n\n\n\n
gcc empty()<\/th>\nmsvc empty()<\/th>\nclang empty()\u00b3<\/th>\n<\/tr>\n
cmp [rcx].size, 0<\/code>
\njz empty<\/code><\/td>\n		cmp [rcx].size, 0<\/code>
\njz empty<\/code><\/td>\n		movzx eax, [rcx].small.is_large<\/code>
\ntest al, 1<\/code>
\njz @1<\/code>
\nmov rax, [rcx].large.size<\/code>
\njmp @2<\/code>
\n@1: shr eax, 1<\/code>
\n@2: test rax, rax<\/code>
\njz empty<\/code><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
The capacity comes into play behind the scenes when extending the string. For example, append(char)<\/code> can do a fast-append if there is excess capacity, and delegate to a function call if the capacity needs to be increased. Here, msvc has an edge.<\/p>\n\n\n\n\n
gcc capacity()<\/th>\nmsvc capacity()<\/th>\nclang capacity()<\/th>\n<\/tr>\n
lea rax, [rcx].buf<\/code>
\ncmp rax, [rcx].ptr<\/code>
\nje @1<\/code>
\nmov rax, [rcx].large.capacity<\/code>
\njmp @2<\/code>
\n@1: mov eax, 15<\/code>
\n@2:<\/code><\/td>\n		mov rax, [rcx].capacity<\/code><\/td>\ntest [rcx].small.is_large, 1<\/code>
\nmov eax, 22<\/code>
\njz @1<\/code>
\nmov rax, [rcx].large.capacity<\/code>
\n@1:<\/code><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
The clang implementation does have an edge in terms of memory usage: Despite an overall smaller size, it has a larger small-string capacity in 64-bit mode.<\/p>\n\n\n\n\n\n
sizeof \/ SSO capacity<\/th>\ngcc<\/th>\nmsvc<\/th>\nclang<\/th>\n<\/tr>\n
32-bit mode<\/td>\n24 \/ 15<\/td>\n24 \/ 15<\/td>\n12 \/ 11<\/td>\n<\/tr>\n
64-bit mode<\/td>\n32 \/ 15<\/td>\n32 \/ 15<\/td>\n24 \/ 22<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
If you reserve()<\/code> a lot of space for a string, but use only a little bit of it, and then call shrink_to_fit()<\/code>, you can potentially get into a mixed state where the string is allocated externally (as if it were a large string), even though the capacity is smaller than the capacity of a small string.<\/p>\n
The msvc implementation uses the capacity to detect whether it is using the small string optimization, so this mixed state is illegal for msvc, and it must convert large strings to small strings if shrink_to_fit()<\/code> shrinks the string below the small-string threshold.<\/p>\n
The gcc and clang implementations allow external allocations to have a small capacity. Nevertheless, both gcc and clang force the conversion of externally-allocated strings to small strings if they shrink below the small-string threshold.<\/p>\n
Update<\/b>: A previous version of this article erroneously said that shrink_to_fit()<\/code> is a nop on gcc.<\/p>\n
One final point of comparison is how the three implementations deal with static initialization.<\/p>\n\n\n\n\n
gcc<\/th>\nmsvc<\/th>\nclang<\/th>\n<\/tr>\n
{ buf, 0, { 0 } }<\/code><\/td>\n{ { 0 }, 0, 15 }<\/code><\/td>\n{ 0, 0, 0, ... }<\/code><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
A statically-initialized empty string in gcc consists of a pointer to the internal buffer, a constant 0 (size), and a bunch of zeroes (buf). The presence of a pointer introduces a relocation into the data segment and  silently messes up string’s constexpr<\/code>-ness<\/a>.<\/p>\n
Statically-initialized empty strings in msvc and clang consist of integer constant data; no pointers. This means no relocations and a better shot at constexpr<\/code>-ness.<\/p>\n
Okay, so let’s summarize all this information into a table.<\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
\u00a0<\/th>\ngcc<\/th>\nmsvc<\/th>\nclang<\/th>\n<\/tr>\n
is_large<\/th>\nslower<\/td>\nfaster<\/td>\nfaster<\/td>\n<\/tr>\n
data()<\/th>\nfast<\/td>\nslower<\/td>\nslower<\/td>\n<\/tr>\n
size()<\/th>\nfast<\/td>\nfast<\/td>\nmuch slower<\/td>\n<\/tr>\n
empty()<\/th>\nfast<\/td>\nfast<\/td>\nmuch slower\u00b3<\/td>\n<\/tr>\n
capacity()<\/th>\nslowest<\/td>\nfast<\/td>\nslower<\/td>\n<\/tr>\n
32-bit size<\/th>\n24<\/td>\n24<\/td>\n12<\/td>\n<\/tr>\n
64-bit size<\/th>\n32<\/td>\n32<\/td>\n24<\/td>\n<\/tr>\n
32-bit SSO capacity<\/th>\n15<\/td>\n15<\/td>\n11<\/td>\n<\/tr>\n
64-bit SSO capacity<\/th>\n15<\/td>\n15<\/td>\n22<\/td>\n<\/tr>\n
ABI supports mixed state?<\/th>\nyes<\/td>\nno<\/td>\nyes<\/td>\n<\/tr>\n
implementation uses mixed state<\/th>\nno<\/td>\nforbidden<\/td>\nno<\/td>\n<\/tr>\n
Static initialization<\/th>\nrelocation<\/td>\nno relocation<\/td>\nno relocation<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
\u00b9 I don’t see clang generating this slightly smaller alternative<\/p>\n
lea rdx, [rcx].small.buf\r\ntest [rcx].small.is_large, 1\r\ncmovnz rdx, [rcx].large.ptr\r\n<\/pre>\n
perhaps because the cmov<\/code> instruction always reads from its second parameter even if the value is not used, and there might be a store-to-load forwarding penalty because in the case of a small string, the read is unlikely to match the size of the previous write.<\/p>\n
\u00b2 I don’t see clang generating this slightly smaller alternative<\/p>\n
movzx eax, [rcx].small.is_large\r\nshr eax, 1\r\njnc @1\r\nmov rax, [rcx].large.size\r\n@1:\r\n<\/pre>\n
probably because “shift right and look at carry” is not something natively expressible in C++. If you really went for it, you could also fold in a cmov<\/code>.<\/p>\n
movzx eax, [rcx].small.is_large\r\nshr eax, 1\r\ncmovc rax, [rcx].large.size\r\n<\/pre>\n
\u00b3 My hand-golfed version of clang empty()<\/code> brings the performance of clang empty()<\/code> to be comparable to gcc and msvc:<\/span><\/p>\n
cmp byte ptr [rcx].small.is_large, 0<\/span>\r\njz empty<\/span>\r\n<\/pre>\n
The trick here is that since clang always uses SSO when possible (no mixed state), the is_large<\/code> is sufficient to tell us whether the string is empty. A large string is never empty, and it will have the is_large<\/code> bit set, so a large string will never have zero as its initial byte. A small string has the is_large<\/code> bit clear and the string size in the remaining bits, so comparing the entire byte against zero tests the size and the is_large<\/code> bit simultaneously.<\/span><\/p>\n
While it’s true that clang always uses SSO when possible, it’s still a valid state for a large string to be empty, because it might have a large capacity but no contents. So we just have to get the size and test it against zero. (Though we can cheat and omit the shift-right since zero shifted left or right by one is still zero.)<\/p>\n
movzx eax, [rcx].small.is_large\r\ntest al, 1\r\ncmovnz rax, [rcx].large.size\r\ntest rax, rax\r\njz empty\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
Pros and cons.<\/p>\n","protected":false},"author":1069,"featured_media":100998,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-109742","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
Pros and cons.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/109742","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=109742"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/109742\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/100998"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=109742"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=109742"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=109742"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}