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

21–30 of 30 posts

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

#21

Post by mianos »

blt wrote: post #5

This is great. It would be a good C/C++ interview question to compare these. Of course you can't expect a Raymond Chen level performance, but it should give some insight into experience with low level programming.

Interesting expectations. So you expect the new guy to be famously better than anyone already at the firm. Highly experienced in something 0.0001% of developers ever actually do. Top marks for bike-shedding as well. I guess being on the ISO committee and being responsible for adding some rando feature would be a ring in.

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

#22

Post by camel-cdr »

nanoxide wrote: post #20
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

He wrote a very lovely book called "The C standard library". It contains a full implementation of the c standard library with lots of explenations and excerpts from the C standard.

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

#23

Post by dmazzoni »

mianos wrote: post #21
blt wrote: post #5

This is great. It would be a good C/C++ interview question to compare these. Of course you can't expect a Raymond Chen level performance, but it should give some insight into experience with low level programming.

Interesting expectations. So you expect the new guy to be famously better than anyone already at the firm. Highly experienced in something 0.0001% of developers ever actually do. Top marks for bike-shedding as well. I guess being on the ISO committee and being responsible for adding some rando feature would be a ring in.

I was imagining you’d show someone the simplified struct representations from the top of the article and ask them to compare/contrast them. Not to know this stuff of the top of their head.

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

#24

Post by blt »

dmazzoni wrote: post #23
mianos wrote: post #21

Earlier quoted context omitted.

Interesting expectations. So you expect the new guy to be famously better than anyone already at the firm. Highly experienced in something 0.0001% of developers ever actually do. Top marks for bike-shedding as well. I guess being on the ISO committee and being responsible for adding some rando feature would be a ring in.

I was imagining you’d show someone the simplified struct representations from the top of the article and ask them to compare/contrast them. Not to know this stuff of the top of their head.

yes, that is what I meant.

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

#25

Post by dmazzoni »

This is so interesting!

I wonder if anyone has ever tried an implementation that prioritizes even more minimal memory usage for small strings?

Of the three implementations discussed, the smallest (on a 64-bit system) is 24 bytes.

How about 8 bytes: the union of a single pointer and a char[8]?

For strings of 6 or fewer characters, it uses the first 6 bytes to store the string, one for the null terminator, and the last byte to store the length, but with a trick (see below).

For strings of 7 or more characters, it uses all 8 to store the address of a larger block of memory storing the capacity, size, and string bytes.

The trick is to use the last byte as a way to know whether the bytes are encoding a short string or a pointer. Since pointers will never be odd, we just store an odd number in that last byte. For example, you could store (size So if the last bit is 1, it's a short string. The size is bytes[7] >> 1, and the data() pointer is just equal to the string itself.

If the last bit is 0, treat the whole data as a pointer to a structure that encodes the capacity and size and then string bytes as usual.

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

#26

Post by variadix »

dmazzoni wrote: post #25

This is so interesting! I wonder if anyone has ever tried an implementation that prioritizes even more minimal memory usage for small strings? Of the three implementations discussed, the smallest (on a 64-bit system) is 24 bytes. How about 8 bytes: the union of a single pointer and a char[8]? For strings of 6 or fewer characters, it uses the first 6 bytes to store the string, one for the null terminator, and the last…

Having to do a load to get the metadata is probably why. Say you have a big array of strings and you care about the compactness of that array for cache reasons, so making the string structs small matters. You probably want to do some operation on all of them, e.g. accumulate the length of all of them so you can determine how much space is required to write them out. Now this either requires a byte scan for the null to determine length, or it requires a load from the heap (that’s probably cold) for the metadata, and a second load from the heap (that is also probably cold).

Generally when you do memory compactification of non-serialized structures it’s for cache related performance improvements, so unless the common case is overwhelmingly small strings there’s probably not a benefit. It’s worth testing to see where this is an improvement, but my guess is that it’s in extremely limited regimes, but maybe some bit manipulations instead of traditional byte scan could yield improvements, likewise it may be worth going to larger SSO sizes for SIMD and a larger scope of SSO cases.

If you’re interested in data structure optimizations like this there’s a cppcon talk about Facebook’s string implementation that has some clever tricks.

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

#28

Post by tialaramex »

tialaramex wrote: post #14

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…

[Raymond has now corrected the charts in the article, and also made other fixes]

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

#29

Post by Iwan-Zotow »

twoodfin wrote: post #15
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.

> it’s both smaller

not sure about "smaller" - cacheline is 32bytes or larger on all modern 64bit cpus

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

#30

Post by Iwan-Zotow »

BeeOnRope wrote: post #13
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.

> libc++ string is smaller

modern 64bit cpus has no less than 32bytes cacheline

Post reply on HN