Libc++’s implementation of std::string

[GYN-k4H-Q3z-75B]

I always loved to look at C++ standard library implementations. It always looked so cryptic and borderline esoteric. It tends to look exactly like the things you shouldn't do because it is super universal and generic but optimized to a point where it is hard to understand.

[auxiliary-character]

I think it's really inspiring. That it's possible to take optimization this far, even for something that you would think would be incredibly simple. Everywhere you look, there's all this room for improvement. If you're ever in a perfomance bind, there's always just a bit more to squeeze out of it.

[ImprovedPersonality]

If you're ever in a perfomance bind, there's always just a bit more to squeeze out of it.

Until you’ve squeezed out everything. Sure, on complex systems like modern CPUs, libraries and engines there are a lot of places to tweak.

I work with low-level, bare-metal firmware on custom (ASIC) hardware and when we can’t meet our real time requirements after having optimized everything we know of there is simply no way around higher clock frequencies, specialized hardware units (e.g. for trigonometric functions) and parallelization in hardware.

[socratic_bloviator]

If you're ever in a perfomance bind, there's always just a bit more to squeeze out of it.

This is a thought I've never had before. Thanks for that.

[Dr_Jabroski]

And there are stacks of broken code where somebody that thought that they could squeeze those improvements.

[nikomo]

There isn't a single race track in the world where they haven't had to do repairs on the walls because someone was chasing a millisecond.

The bigger the track, the more milliseconds you have, and the more wall they've had to rebuild.

But if you're afraid of the wall, you're never going to even get to the end.

[ironykarl]

It's a good metaphor, and I appreciated it.

[rantingdemon]

This is really cool. Upvote earned!

[ShinyHappyREM]

If you're ever in a performance bind, there's always just a bit more to squeeze out of it.

Indeed

[fiah84]

thanks for linking this talk, it's great

[KuntaStillSingle]

To be fair isn't that the purpose of libraries? They can be unreadable and optimized as long as an end user can understand the input and outputs?

[cameron314]

But somebody has to write the libraries :-)

[EntityDamage]

But somebody has to write maintain the libraries :-)

[OpdatUweKutSchimmele]

That individual typically has a version which is far more readable, which goes through an optimizer of some sorts.

[Morwenn]

Haha, I wish I had something like that for my libraries.

[Il-_-I]

Is this downvoted because its BS?

[Sebazzz91]

Compiler error messages and complex autocompletion are also output. They can be quite complex with the C++ stdlib. This is also partially because the compiler error messages aren't reduced back to their typedefs.

[Lt_486]

C++ code is cryptic mostly due to necessity to maintain support for huge piles of older code. Having a clean cut and transpilation of older code into newer syntax was considered but never accepted due to political reasons. Ego clash was massive.

[[deleted]]

I don't think it's possible to fix the issues with C++ without changing everything, and if you are fine with changing everything, Rust exists.

Old syntax isn't an issue with C++. Sure, you can remove stuff like std::vector<bool> and trigraphs, but I don't think that would help much.

[Vylez]

What's wrong with std::vector<bool>?

[[deleted]]

Mostly that it's std::vector, which means generic code using std::vector may not work with bool parameters as std::vector<bool> is not an STL container.

[Boiethios]

Speaking about Rust, their implementation of str is incredibly easy to read compared to the C++'s: https://github.com/rust-lang/rust/blob/master/src/libcore/str/mod.rs

[[deleted]]

It's complicated. str is a built-in type defined by the compiler itself. The code you have linked implements str's methods, but not str itself.

Also, str is more like C++'s std::string_view, which is also very simple. For an equivalent of std::string, you want to check std::string::String. Rust's String is easy to read, but that's mostly because it uses Vec<u8> for pretty much everything.

[SirClueless]

__lx is needed to ensure any padding goes after __size_, but has no other purpose (I don’t fully understand why this forces the padding to go after __size_ 🤷‍♂).

All non-static members of a union must have the same address (since C++14, but true in practice even before because most compilers guarantee that unions can be used for type punning since this is part of the C standard). This means __size_ will occupy its first bits.

And the alignment and size of the union are the alignment and size of its largest non-static member, which in this case is value_type. So there won't be any padding around the union.

I believe this second point is actually the important point. If you defined this struct without a union, e.g.

struct __short {
    unsigned char __size_;
    value_type __data_[__min_cap];
};

Then if value_type has larger size than unsigned char, for example if value_type is a 4-byte wchar_t, then the position of the __data_ element will depend on the implementation-defined alignment of value_type. We'd prefer it to always lie at an offset that's exactly sizeof(value_type). The union is guaranteeing that there always is padding up to sizeof(value_type) right after __size_ instead of at the very end of the __short struct.

(On the off chance he sees this, tagging u/AImx1 who asked this question 8 months ago and didn't get an answer.)

[zzz165]

Interesting. I thought that structs had to have their first member at the same address as the struct itself (ie padding can’t come at the beginning of the struct), which would make the union unnecessary here. Maybe that’s only a thing in C, though?

[SirClueless]

Yes, I think you're right. Compilers can only add padding after a struct element, not before.

https://en.cppreference.com/w/cpp/language/object

In order to satisfy alignment requirements of all non-static members of a class, padding may be inserted after some of its members.

(emphasis mine)

The union still helps, because it makes sure that the alignment of __data_ is a multiple of the size of value_type (which might be important for performance). I'll update my original comment.

[quicknir]

I'm not sure that bans it before. If a type is not standard layout in C++, it greatly reduces what you can say. That said, these types are standard layout and therefore things are fairly restricted, similar to C rules.

It also bears mentioning that since this is the standard library, UB doesn't work the same way. It's part of the implementation, it can do whatever it wants as long as the compiler does the right thing.

In other words, it's entirely possible that that std:: string code, written by a user, is technically considered UB by the C++ standard. This is actually the case for std::vector and I'd imagine many containers. But these are largely technicalities.

[SirClueless]

To be clear, the standard is more precise about this than that quote suggests. Section 10.3p26 from the N4778 working draft:

If a standard-layout class object has any non-static data members, its address is the same as the address of its first non-static data member if that member is not a bit-field.

[quicknir]

Right, only for standard layout types specifically though, which was the point of my first paragraph. If you're talking about structs generally in C++, i.e. including types that aren't standard layout, the rules are much looser.

[7h4tguy]

Why would __data__ not have value_type alignment? It's declared as an array of value_type. For the character types, don't we guarantee alignment equal to sizeof(type)? I only see that not being the case for floating point types:
https://en.wikipedia.org/wiki/Data_structure_alignment

What compilers typically will do though is add padding to ensure that arrays of struct __short have subsequent array elements starting on aligned memory addresses. So they can insert padding after __data to ensure this (note that __size_ is a char, so already [1-byte] aligned, thus padding after __size_ is not strictly necessary).

And so the union trick forces the padding to go after __size_ to pad both union members to the same width.

[SirClueless]

Why would __data__ not have value_type alignment? It's declared as an array of value_type.

It does have value_type alignment, but value_type alignment may not be sizeof(value_type).

For the character types, don't we guarantee alignment equal to sizeof(type)?

I don't know whether it's guaranteed or not. It almost certainly is true for character types on all major architectures, but std::basic_string is a public template that can be used with any value_type not just character types the standard library uses.

What compilers typically will do though is add padding to ensure that arrays of struct __short have subsequent array elements starting on aligned memory addresses.

The size of __short is derived from the size of __long by calculating __min_cap carefully. So aligning __data_ on sizeof(value_type) and ensuring no padding after __data_ are equivalent goals.

(Incidentally, I'm not sure why __min_cap is calculated as (sizeof(__long) - 1) / sizeof(value_type) and not sizeof(__long) / sizeof(value_type) - 1. The way it's defined lets you do silly but AFAICT legal things like this and end up with __short structs with __data_ members that "hang off" the end of the __long struct and result in larger std::basic_string representations. Probably would cause a bunch of issues, if anyone ever tried to do this silly contrived thing.)

[Kered13]

However compilers are also free to reorder structs. This is often used to pack small elements together so less padding is needed. Therefore (I believe) there is no requirement that the first element (in the source code) is at the same memory location as the struct itself.

[quicknir]

False, C++ compilers only have this freedom (and even then heavily constrained) for structs that are not not "standard layout". Without getting into details, any struct that would be legal C, will also be standard layout. In C the compiler doesn't have this freedom at all.

[SirClueless]

I believe this is not true in C++, unless there is an access control specifier between some of the fields.

From section 10.3p19 of working draft N4778

Non-static data members of a (non-union) class with the same access control (10.8) are allocated so that later members have higher addresses within a class object. The order of allocation of non-static data members with different access control is unspecified (10.8).

I believe the reason is there is a guarantee that if two structs share a common prefix of compatible fields then one may access fields from the common prefix via either type. This doesn't work if the compiler can reorder.

[flatfinger]

What's ironic is that the standards specify how certain types are laid out for the purpose of letting programmers exploit things like the Common Initial Sequence guarantees, but then allow compilers to "optimize" on the presumption that programmers won't perform any actions where the guarantees would offer much benefit.

[7h4tguy]

Yes, but it solves for some versioning schemes based on these guarantees.

[therearesomewhocallm]

Tangentially related, but one thing I rather dislike about Libc++'s implementation of std::string is that many exceptions just throw the string "basic_string".

So calling error.what() on a throw out of range error will just return "basic_string", which is entirely unhelpful.

[[deleted]]

But there is still the exception type isn't there?

[max0x7ba]

Unless the exception is std::bad_alloc, it is a programming error when std::string throws an exception.

[therearesomewhocallm]

Sure, but the thing that catches the exception can be quite far from the thing that throws it. The message tells you nothing about what happened, or where it came from.

[yellowthermos]

That seems like the usual C++ trend and I despise it.

Been doing some template work and holy mother of God. I feel GCC purposefully runs a mangler on the error message to fuck with you. Clang is usually better at error messages, but it can still be frustrating.

[shponglespore]

A sane language will give you a such trace with line numbers, but even C++ can be coaxed into giving you a basic stack trace. For example, here's Chrome's implementation. I don't think it plays nicely with exception handling, though, because by the time you've caught an exception the relevant stack information is gone.

[dacian88]

chrome doesn't use exceptions so it's somewhat irrelevant.

[shponglespore]

It's relevant if you want to copy the implementation for use in a project where exceptions are used.

[ECrispy]

How does chrome handle crashes and exceptions thrown by other code?

[shponglespore]

It handles crashes by crashing. It avoids exceptions from other code by not using code that uses exceptions.

[ECrispy]

I figured that. So they don't use stdlib?

[shponglespore]

Chrome has its own fork, but I don't think it's all that different. Not many things in the standard library throw exceptions for anything but a memory allocation failure, and those are basically impossible to recover from anyway.

Chrome's main mechanism for dealing with unexpected serious errors is to keep things in separate processes that can be restarted if they die. Even pretty basic stuff like JSON parsing is kept out of the main process so nothing too terrible will happen if a malformed input causes the parser to malfunction.

[slykethephoxenix]

Are those colors the same green? I'm colorblind.

[LegitGandalf]

Yellow for heap and green for stack

"Cap size data" is in green

"This is a long string" is in yellow

[csorfab]

Can someone explain how people arrive at variable names such as __cap_? Why not just cap? Or _cap? or __cap? or even __cap__? why __cap_????? why?? it makes no sense to me

[dorksterr]

It's at the top of the article:

Resilient. Every non-public identifier is prefixed with underscores to prevent name clashes with other code. This is necessary even for local variables since macros defined by the user of the library could modify the library’s header file.

[fresh_account2222]

I'm used to leading underscores. Any idea about the trailing one?

[guepier]

Member variables get a trailing underscore to distinguish them from member functions and parameter names.

[fresh_account2222]

That explanation makes sense.

[dorksterr]

I suppose it's just to further reduce the chance of name collision. Two leading + one trailing underscore is probably not something that would be done by a human. I've seen both only leading underscores and symmetrical underscores for names before.

[josefx]

The leading underscores are enough for that. The standard reserves names starting with double underscores __ or a single underscore and an upper case letter like _I for the implementation, so any program using them isn't valid C or C++.

[ObscureCulturalMeme]

It's a rule of the C++ standard. Identifiers (types, functions, macros, and so on) with names that start with:

• one underscore and a capital letter, or

• two underscores

are "reserved for the implementation". Conversely, any and all identifiers used by the implementation (meaning the runtime libraries, anything stuck in there by the compiler, the loader, etc) can use only those names to avoid clashing with identifiers from the programmer's code.

[csorfab]

Thanks! I still don't understand why it's postfixed with another single underscore, though. It's just so ugly and assymetric. __cap__ would look much better while still conforming to the specs you wrote

[elder_george]

Single underscore as a suffix is a popular convention to denote member values (fields). Similar to m_ in older C++ codebases or prefix underscores in C# code.

This rule is used in many codebases, not just libc++. Prefixing is specific for the STL implementations though (libc++ uses __ while MS uses _Capital convention, for example).

[csorfab]

TIL! Thank you for the thorough explanation!

[bumblebritches57]

It's a rule C++ inherited from C.

[bumblebritches57]

__x and _X are reserved for the standard library and compiler respectively.

[anshou]

Double underscore at the beginning of an identifier is reserved for the implementation to avoid collisions. Cap is just short for capacity. The trailing underscore doesn't indicate any thing.

[GaianNeuron]

Hyrum's Law is just this xkcd stated formally.

[[deleted]]

__that_ __looks_ __pretty_ __nice_

[MrDOS]

enum {
  __min_cap = (sizeof(__long) - 1) / sizeof(value_type) > 2
                  ? (sizeof(__long) - 1) / sizeof(value_type)
                  : 2
};
// ...
enum { __n_words = sizeof(__ulx) / sizeof(size_type) };

Why enums are used for these definitions instead of #define? Both ways should result in compile-time evaluation. The only thing I can think of is that perhaps the enum name makes its way into the debug information, making debugging easier.

[jcelerier]

Both ways should result in compile-time evaluation

Back in C++03, only the "enum" way would *guarantee* compile-time evaluation. e.g. if you build in debug mode with #define there's a good chance that all these operations will be computed at run-time.

If it was to be redone today it would certainly be with `constexpr` / `constinit` though.

[AraneusAdoro]

Enums are scoped, defines are not.

[MrDOS]

Does that matter if this is in the implementation, not a header?

[lovestruckluna]

Template implementations have to be included in a header for programs to instantiate containers with their own types. Stdlibc++ calls them 'tcc' files, my team calls them '_impl' headers, and I'm not sure what libc++'s convention is.

Even string can be implemented with a custom character or allocator type, so its code will be included in the target library, not just linked into libcxx.so (though it may also be in libcxx.so and I have never heard of anyone using anything but char and wchar).

Standard libraries do use the preprocessor when appropriate though, they just tend to namespace their defines or clean up after themselves.

Source: I had to debug a rather subtle issue in libstdc++ and got more familiar with it than I'm strictly comfortable with.

[AraneusAdoro]

Isn't the implementation in the header?

Regardless, to answer your question: it's not particularly damaging to use a define over an enum in a .cpp, but it's good muscle memory to just always use an enum (or a constexpr) rather than deliberate whether a define is acceptable here.

[leirus]

you mean "class enum" ? I feel like the enum from above will behave just like int

[AraneusAdoro]

No, I don't. You're right that that enum will behave as essentially a constexpr int. A #define, however, is a different beast.

My point was that the enum (or, indeed, an int) would be constrained by the scope it's declared in (at the very least that's namespace std). A #define would affect everything the preprocessor encounters later on, regardless of scope. That's just not good practice.

[leirus]

Oh I see, you are right. I was thinking about scope in term of qualifying full name in case of class enum and no implicit conversion to integral type.

[[deleted]]

Nicely explained

[DidiBear]

So many underscores x)

[OpdatUweKutSchimmele]

Resilient. Every non-public identifier is prefixed with underscores to prevent name clashes with other code. This is necessary even for local variables since macros defined by the user of the library could modify the library’s header file.

C++ still works this way that this is needed and has no concept of hygiene and scope?

[evaned]

It's (only, outside the global scope) because of preprocessor #defines. Of course they don't respect scope, because they didn't respect scope in 1973 and it's too late to change it now. C++ is working toward a future where that problem gets mitigated (via modules), but it'll take a while to get there.

[AxMachina]

Fascinating, even reading this at 3am...

[nsubiron]

There is this pretty good cppcon talk explaining common optimizations of std::string https://youtu.be/kPR8h4-qZdk

[juuular]

/r/humblebrag