Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

An informal comparison of the three major implementations of std:string

devblogs.microsoft.com

Post reply on HN
Print view View original

11–20 of 30 posts

Re: An informal comparison of the three major implementations of std:string

#11

Post by asveikau »

whoopdedo wrote: post #8

GCC putting a pointer at the top of the structure seems reminiscent of the way Pascal stored strings. A PString is the address of a character buffer like C, but the length of the string is stored at a negative offset. I may be remembering wrong but I think there was an older C++ STL that also used negative offsets. As much as these snippets make clang look heavier, I wonder what it compiles to in practice when the co…

> A PString is the address of a character buffer like C, but the length of the string is stored at a negative offset. I may be remembering wrong but I think there was an older C++ STL that also used negative offsets.

In the Microsoft world, BSTR from COM/OLE does this. Though I think the length prefix is 4 bytes, and the payload is 16 bit wchars.

Re: An informal comparison of the three major implementations of std:string

#12

Post by techjamie »

dataflow wrote: post #9

The most interesting thing imo is what they all do similarly: they all store the size, instead of the end pointer -- unlike, say, std::vector. Exercise for the reader as to why this is the right tradeoff.

Maybe the sheer amount that strings are getting iterated through makes storing length computationally cheaper? Unless you're using very optimized methods to work with the string, the majority of string operations involve a lot of iteration and comparison. Vectors, on the other hand, have much more varied use and possibly may never be iterated at all (though they likely will somewhere).

Re: An informal comparison of the three major implementations of std:string

#13

Post by BeeOnRope »

ajross wrote: post #6

tl;dr: libc++ is just bad, libstdc++ and MSVC trade punches for first place, with the eyeball win going to the FSF. Though really the performance gates on string-heavy code tend to be in the heap and not the string library itself.

libc++ string is smaller with a higher SSO capacity which in many scenarios can overwhelm the code generation. So it's hard to draw an absolute conclusions.

Re: An informal comparison of the three major implementations of std:string

#14

Post by tialaramex »

The SSO capacity tables seem obviously wrong to me. For clang/libc++ we see 11 or 22 bytes, in each case it's the size of the whole data structure, minus one byte for the bit flag and length value, and another byte for the zero (ASCII NUL) that's obligatory in C++

But for MSVC and GCC we're told 16 bytes as each has a 16-byte buffer. However they still need that obligatory zero byte, for ASCII NUL so surely the table should show 15.

The most popular string in C++, the one which makes SSO almost obligatory as a design feature for the language's string object, is the empty string. On a modern (64-bit) machine Clang can store that inline in a local 24-byte object, MSVC and GCC need 32-bytes. Without SSO it would mean probably 24 bytes and a heap allocation. That's hard to swallow.

Re: An informal comparison of the three major implementations of std:string

#15

Post by twoodfin »

whoopdedo wrote: post #8

GCC putting a pointer at the top of the structure seems reminiscent of the way Pascal stored strings. A PString is the address of a character buffer like C, but the length of the string is stored at a negative offset. I may be remembering wrong but I think there was an older C++ STL that also used negative offsets. As much as these snippets make clang look heavier, I wonder what it compiles to in practice when the co…

Agree, re: clang. In dominant 64-bit platforms it’s both smaller and eliminates more allocations.

When placing a bet on real workload performance, I’d take those attributes every day of the week and twice on Sundays.

Re: An informal comparison of the three major implementations of std:string

#16

Post by GuB-42 »

ajross wrote: post #6

tl;dr: libc++ is just bad, libstdc++ and MSVC trade punches for first place, with the eyeball win going to the FSF. Though really the performance gates on string-heavy code tend to be in the heap and not the string library itself.

Size is very important, and in may experience less memory usage tend to beat using less instructions. So I understand Clang decision to trade size for complexity.

Clang developers are not stupid, if they did that instead of copying what GCC or MSVC did (they both predate clang), there is a good reason, and my guess is that it is better aligned with how modern architectures and optimizers work. Anyways, that's a tradeoff, but on a modern high performance computer, intuitively, I would side with clang.

Re: An informal comparison of the three major implementations of std:string

#17

Post by cpeterso »

asveikau wrote: post #11
whoopdedo wrote: post #8

GCC putting a pointer at the top of the structure seems reminiscent of the way Pascal stored strings. A PString is the address of a character buffer like C, but the length of the string is stored at a negative offset. I may be remembering wrong but I think there was an older C++ STL that also used negative offsets. As much as these snippets make clang look heavier, I wonder what it compiles to in practice when the co…

> A PString is the address of a character buffer like C, but the length of the string is stored at a negative offset. I may be remembering wrong but I think there was an older C++ STL that also used negative offsets. In the Microsoft world, BSTR from COM/OLE does this. Though I think the length prefix is 4 bytes, and the payload is 16 bit wchars.

An interesting difference between BSTR and Pascal strings is that BSTR strings, in addition to the length prefix, are NUL terminated (for compatibility with C string APIs). And since Pascal strings track their length in the prefix, they can support strings with embedded NUL bytes.

Re: An informal comparison of the three major implementations of std:string

#18

Post by cpeterso »

techjamie wrote: post #12
dataflow wrote: post #9

The most interesting thing imo is what they all do similarly: they all store the size, instead of the end pointer -- unlike, say, std::vector. Exercise for the reader as to why this is the right tradeoff.

Maybe the sheer amount that strings are getting iterated through makes storing length computationally cheaper? Unless you're using very optimized methods to work with the string, the majority of string operations involve a lot of iteration and comparison. Vectors, on the other hand, have much more varied use and possibly may never be iterated at all (though they likely will somewhere).

> getting iterated through

So for loop conditions like

  for (size_t i = 0; i
are cheaper to calculate?

Re: An informal comparison of the three major implementations of std:string

#19

Post by cozzyd »

GuB-42 wrote: post #16
ajross wrote: post #6

tl;dr: libc++ is just bad, libstdc++ and MSVC trade punches for first place, with the eyeball win going to the FSF. Though really the performance gates on string-heavy code tend to be in the heap and not the string library itself.

Size is very important, and in may experience less memory usage tend to beat using less instructions. So I understand Clang decision to trade size for complexity. Clang developers are not stupid, if they did that instead of copying what GCC or MSVC did (they both predate clang), there is a good reason, and my guess is that it is better aligned with how modern architectures and optimizers work. Anyways, that's a trade…

On the other hand, ABI incompatibility has a cost (not that GCC has stayed ABI-compatible with itself...)

Re: An informal comparison of the three major implementations of std:string

#20

Post by nanoxide »

gte525u wrote: post #3

Somewhat related - but there are a ridiculous number of platform/systems that ship with derivative of Dinkum C++ standard library - MSVC (included). When you lookup the company behind it - it's basically small shop that seems to be primarily one guy up in MA.

That one guy even has it's own Wikipedia article https://en.m.wikipedia.org/wiki/P._J._Plauger
Post reply on HN