12 ms·
Libc++'s Implementation of std::string
- dylanmclark 7y agoReminds me of a talk a few years ago about Facebook's internal implementation of std::string. They do the same short string optimization, but Facebook manages to outperform this implementation by storing 24 bytes (vs 23) in "short string mode". IIRC, Facebook achieves this by using the last byte as the flag byte. To signify short string mode, this flag is set 0. This allows it to also serve as the null terminator. Tricky!
- rwbt 7y agoThat is clever. Using last byte as the flag byte also lets one cast the std::string memory address to a null terminated c-string without intermediate buffers (not that one should).
- braindeath 7y agoUmm.. in any implementation you can already "cast" a std::string to a null-terminated string without a buffer (cf std::string::data() and std::string::c_str()) -- C++11 essentially mandates that. c_str must return "a pointer p such that p + i == &operator[](i) for each i in [0,size()]." The history of those demonstrate some of the bat-shit insanity of the evolution of C++. Originally data didn't have to null-terminated, but then they finally realized that making c_str actually work without this invariant in general was nearly impossible. So since C++11 data and c_str are equivalent. Edit: by impossible I really mean something usable with sane complexity requirements -- that wouldn't make people just immediately discard std::string for something better. This is the same C++ that brought you auto_ptr, and other garbage. C++11 corrected many things, this included.
- murderfs 7y agoIt was possible with copy on write strings (e.g. libstdc++'s strings until C++11), but C++11 added complexity requirements that outlawed COW strings, because they're only really useful in very specific circumstances, at the cost of making the common case slow.
- ncmncm 7y agoThere was no need to plug in the NUL until somebody called c_str(). That possibility was lost in C++11. Now, if somebody plugs something else there (which is done, UB notwithstanding), c_str() produces the wrong answer. NUL-terminated strings were one of the dumber things C++ inherited from C, and code that depends on NUL termination is not a thing to be proud of.
- braindeath 7y agoHow do you "plugin" the NUL. If there's no space for it, then everytime you want a C string, you need to do an allocation. And why would you put something in it's place - as you said if you modify the c_str that was always UB -- so you pretty much lost all guarantees at that point -- that was just dumb. Basically the NUL-terminator amounts to a 1-byte of wasted space -- which is almost always completely in the noise -- if you're using std::string for tiny strings you're paying at least 24 bytes anyway. There are just very few cases where that one extra byte matters. I think the overwhelming opinion is that this 1-byte trade-off is better than the overhead of allocation and copying when you want to pass that string around. NUL-terminated strings aren't important in C++ because of C (well, not directly), but because they are essentially the ABI of countless existing libraries and the major operating systems. > code that depends on NUL termination is not a thing to be proud of. Whatever. Code that depends on NUL termination is ubiquitous.
- ncmncm 7y ago>How do you "plugin" the NUL. If there's no space for it, then everytime you want a C string, you need to do an allocation. You have not thought it through. There was always space for a NUL, but nobody needs it to have a NUL in it until somebody calls c_str(). Anyway, that was true until somebody jiggered the Standard, just before 1998, to require a NUL visible to s[s.size()]. >C Code that depends on NUL termination is ubiquitous. Fixed that for you.
- BubRoss 7y agoAre you saying that there should not be an extra 0 byte at the end until the string fills up and c_str() is called? Inconsistent allocations seem like a recipe for difficult to debug performance problems.
- zelly 7y agoC++11 was really a new language. It even had a whole new ABI. I'm surprised the transition went smoothly and not like Python 2 to 3.
- foota 7y agoImo this is probably in part because you can mix the two more easily? I imagine you could link again C++ 2003 code compiled with a compiler understanding the new ABI?
- fyp 7y agoIt's a tradeoff. In libc++'s version you still have string size stored in the top 7 bits so you just need a bitshift to get size. It sounds like fb's implementation would require looping until null terminator to get the size.
- edflsafoiewq 7y agoIIRC you store (23 - size) in the last byte in "small string" mode, so when the size gets to 23, the last byte is 0, doubling as the null terminator.
- lilyball 7y agoSurely it must be (23 - size) << 1, otherwise you won't guarantee a 0 in the LSB.
- edflsafoiewq 7y agoIf you use the LSB of the last byte for a flag, you're using the 56th bit of one of the {data,size,cap} words. I'd use the MSB in this case, since you can shift that off easier.
- SamReidHughes 7y agoOn little endian systems it uses two MSb's, on big endian systems it uses two LSb's. There are actually two flag bits.
- deleted 7y ago[deleted]
- roel_v 7y agoTo save those who, like me, were going to comment 'that would violate the standard because std::string::size is required to be O(1) complexity' a Google - the standard recommends but doesn't require that.
- coolplants 7y ago
- pjscott 7y agoI think this is the talk you're referring to. If not, it's still definitely worth a watch: https://www.youtube.com/watch?v=kPR8h4-qZdk https://www.youtube.com/watch?v=kPR8h4-qZdk
- stuffypages 7y agoPart of the motivation for writing this blog post was that I enjoyed this talk so much.
- thedance 7y agoIt’s funny that every company gets to the point where they have to have their own std::string. I wonder if Facebook also traces their need back to the time when GNU std::string was copy-on-write and therefore completely useless. Google, I think, can trace their std::string to those dark days. Luckily c++11 effectively outlawed COW string implementations, so nobody need be subject to that horror show again.
- api 7y agoSo your own std::string means you have "arrived?"
- faitswulff 7y agoI'm not very good at systems programming, what makes a CoW std::string a bad thing? Memory overhead for a common data structure?
- yongjik 7y agoFrom what I've heard - COW means each string data may be pointed to by multiple objects, potentially being used by different threads. So every string operation requires thread synchronization, which can be quite expensive.
- kccqzy 7y agoThe language is fundamentally too weak to express the kind of reference and borrowing relationships demanded by CoW. Suppose I have a string and I take a reference to a character: std::string a = f(); // shared char& c = a.front(); Should the string be copied or not? One might argue, no taking a reference is different from "writing" so no copying, but one might also argue that reference can be used to change the string later, and the string doesn't know when this would happen so it has to pessimistically make a copy. You get bugs if you go with the former, and bad performance if you go with the latter.
- zelly 7y agoconst char& c = a.front(); Unfortunately the STL has an overload for the non-const version, which would cause this problem. It's hard to imagine the cases where you'd need a mutable reference to a single character. It can fit into the same register that the reference would live, so even as an immutable reference it doesn't make much sense.
- lbrandy 7y agohey i've worked on this stuff for awhile at fb. One important update is that the primary rationale for us, at the time, to change std::string's implementation to `fbstring` was to get SSO. We got huge perf wins for having SSO on std::string. (small string optimization for those unfamiliar with the initialism). This, at the time, was a violation of the standard. By wording, SSO was not standard compliant. Once the standard was changed (as of C++11) so that std::strings could have SSO, we removed our patches on the standard library and now use "vanilla" std::string (from libstdc++). We still have `folly::fbstring` for people who want that implementation (which is smaller, and has more in-situ capacity, because of various cleverness detailed in that talk), but it's no longer our `std::string`. For reference: https://github.com/facebook/folly/blob/master/folly/FBString.h https://github.com/facebook/folly/blob/master/folly/FBString...
- tybit 7y agoDo you happen to know why the standard doesn’t use that trick? It always impressed me how clever it was, but once you know it it seems fairly clean and maintainable with no obvious downsides.
- deleted 7y ago[deleted]
- scottlamb 7y agoJust a guess: the null byte is necessarily at the end of the 24 bytes rather than at the beginning. It might be in a different (typically 64-byte) cache line. Maybe one you don't need to read in from main RAM otherwise if you're handling a shorter string. That might make more of a performance difference than whether 23-byte strings (plus NUL byte) are short or long, depending on your application.
- choeger 7y agoAfaik it costs you some performance for long string operations.
- OskarS 7y agoI think it's to avoid a branch in `size()`. If you use this trick, you have to check the flag if it's a small in-situ string or a "regular" heap-allocated string, because they they calculate size differently. In the standard library strings, the size is always just stored in the same position in memory, so `size()` has essentially no overhead when inlined, it's just a memory load. Branches on their own aren't particularly expensive (especially not an easily predictable one like this), but they do screw with several compiler optimizations (auto-vectorization, for one). Given that, it seems like a reasonable decision, and the only way you'd know which one is faster is just testing it. I'd personally think it would be interesting to test artificially increasing the sizeof() of strings from 24 bytes (the minimum needed to store a pointer, size and capacity) to something like 64 bytes, just to get longer strings using the SSO. The trade-off in the stack-space of the string seems like it would totally be worth it, and with 56 character long "small strings", a huge number of strings could fit in there (virtually all names, for instance). You probably couldn't do it for std::string (would wreck havoc with ABIs), but my hunch is that performance and memory usage might both benefit from the reduced memory allocations.
- deleted 7y ago[deleted]
- continuational 7y agoIf you use one of the bytes for a null terminator, then you can't use it for a character in the string, so isn't that 23 characters?
- garmaine 7y agoYes, but by that accounting the other mechanism has only 22 characters.
- spac 7y agoBloomberg has also developed a drop in replacement for std::string with SSO, and has a very well documented header file. https://github.com/bloomberg/bde/blob/master/groups/bsl/bslstl/bslstl_string.h https://github.com/bloomberg/bde/blob/master/groups/bsl/bsls...
- deleted 7y ago[deleted]
- lallysingh 7y agoTypo in title. That's std::string.
- stuffypages 7y agoThanks! I don't think I can edit it now though :( Does the edit button disappear after a certain amount of time?
- thenewnewguy 7y agoI don't believe you can ever edit the title of a submission, but the mods can (and typically will).
- dang 7y agoYes.
- tlb 7y agoEdited, thanks.
- kccqzy 7y agoHere's something that once bit me. The libc++ implementation uses short string optimization. Which means no heap allocation for short strings. Unfortunately I didn't know this and naively thought when you std::move a string, the data() buffer would remain unchanged. This is then incorrect. You can manifest this by storing strings into any container that moves their elements around like std::vector or absl::flat_hash_map.
- zvrba 7y ago> when you std::move a string, the data() buffer would remain unchanged You cannot assume anything about the state of a moved-from object. AFAIK, the only valid operations are destruction and assigning something else to it.
- leni536 7y agoNot entirely true. Moving from std::vector is required to not invalidate iterators and references when moved from. This is why strings can be small buffer optimized and vectors can't be.
- zvrba 7y agoThis does not conflict with what I or the OP wrote; you're mixing up the vector and its contents. Moving from a vector can invalidate `data()`, yet references and iterators to its previous contents remain valid.
- steerablesafe 7y agoWell, kccqzy probably meant the pointer returned by data remaining valid, not calling data() again on a moved-from object.
- quietbritishjim 7y ago> You cannot assume anything about the state of a moved-from object. This is the right default assuption, but classes are allowed to have (and document) more specific behaviour. For example, it is guaranteed that std::unique_ptr and std::shared_ptr are empty (nullptr) after they have been moved from, and std::vector is guaranteed to be empty after it is moved from so long as the destination allocator is the same. > AFAIK, the only valid operations are destruction and assigning something else to it. Even for classes whose move constructors have no guarantees, there are often other methods that don't have any preconditions, such as calling clear() or resize(0). In fact is it allowed to call other operations and they should behave consistently, it's just not guaranteed what exact value the object should have (e.g. if size() > 0 then .at(0) should not throw and a second call to it should return the same value as the first call to it).
- userbinator 7y agoThe short string mode uses the same 24 bytes to mean something completely different. ...and the reason short strings are that length is precisely because a long string needs that amount of space to store the pointer, capacity, and used variables anyway. On a 32-bit system, the short string limit is lower by half. Also, as optimised as this implementation is, I have yet to see a compiler that's smart enough to do things like replace "dumb" uses of std::string with essentially the equivalent of what a smart C programmer using pointers would write (as the saying goes, "the fastest way to do something is to not do it at all.") Ditto for the other data structures in the library. In other words, optimising individual classes approaches a local minima.
- zelly 7y agoAnd the smart assembly programmer laughs at the C programmer. There are a couple dozen string-oriented x86 instructions that I've never seen a C or C++ compiler produce. You could easily get a 2x speedup on strings by hand writing clever x86 with SSE. In fact I'm surprised no one has made an STL with lots of inline assembly.
- erik_seaberg 7y agoMost of what I know predates SSE; does that have a long track record of being fast? I know REP MOVSB was originally fast, and then CPU vendors decided it was rarely used and did it in (slower) microcode, and then architectural changes made it fast again sometimes depending on alignment.
- userbinator 7y agoREP MOVS is still a microcode loop, but it will copy entire cachelines (usually 64 bytes) at once if it can. The fact that it is a tiny instruction (2 bytes) and runs in microcode means that it doesn't consume instruction fetch bandwidth while it's running, and occupies only a tiny amount of the instruction cache.
- Hello71 7y agoyou'd get worse results, because 1) most of those instructions are slower on modern hardware anyways, and 2) assembly is an optimization barrier on modern compilers, so even if you make one function 0.1% faster, it's not worth it if you've slowed down the rest of the program by 1%.
- yongjik 7y agoI always wondered why these string implementations have full 8 bytes for length. Many programs use millions of strings (or more), while very few would ever use a >2GB string. It would make sense to use, say, "not-too-long string optimization" where you only store 4-byte lengths for any string <2GB, and use the remaining one bit to mean "the length is in the data block". But I guess these people have run the benchmarks. ...Or maybe not. I have to wonder.
- dc443 7y agoI'm not sure that is optimization is relevant now that your CPU's native architecture will be just as efficient with the 8 byte length as the 4 byte one.
- lifthrasiir 7y agoIt is relevant to the memory usage.
- vnorilo 7y agoYou would be trading 4 bytes for an extra branch on getting the size. Since the instance needs 8-byte alignment, those 4 bytes would be lost in padding or allocation overhead anyway.
- Const-me 7y ago> for an extra branch on getting the size Modern CPUs have branch prediction. The predictors work by caching which branches were taken, and assuming the same outcome is likely to happen next time the branch at that address is checked. That particular branch is checked all the time, and unless you actually have >2GB strings the result is always the same. Only branches which dynamic runtime behavior are bad for performance, like binary search when the same branch is taken/not taken randomly, depending on the data and the key being searched. Branches with stable runtime behavior are OK thanks to branch prediction. Examples of good branches: `while( i < 10000 )`, `if( string_length < INT_MAX )`
- Thorrez 7y ago> I will assume that ... the char type is signed and 1 byte wide. You don't really need to make an assumption about being 1 byte wide. That's guaranteed by the standard. https://en.cppreference.com/w/cpp/language/sizeof https://en.cppreference.com/w/cpp/language/sizeof
- stuffypages 7y agoThanks! Fixed.
- stuffypages 7y agoInteresting, the page you linked also says this. >Depending on the computer architecture, a byte may consist of 8 or more bits, the exact number being recorded in CHAR_BIT. I'll add that as an assumption.
- thedance 7y agoDoes it make a difference? It doesn't seem like your article relies on CHAR_BIT being 8.
- gpderetta 7y agoThat's true, by definition one char is one byte. What's not guaranteed is that 1 byte is one octet.
- RcouF1uZ4gsC 7y agoNote that this implementation has undefined behavior according to the standard because union members are accessed that haven't been written to. The code that tests whether it the string is long or short, accesses members of the union unconditionally. This is fine because std::string is provided by the standard library and the standard library is allowed to do stuff normal libraries are not allowed to do. This technique does work in practice, but it is technically undefined behavior.
- cryptonector 7y agoWhy is this worth noting?
- Inityx 7y ago> standard library is allowed to do stuff normal libraries are not allowed to do. How does this work, given that it's still written in C++? Is there special casing in the compiler to define the behavior?
- chacham15 7y agoIts about maintenance. Things which are "undefined behavior" can actually have a defined behavior if the compiler provides it. By doing something undefined in the stl, the compiler authors are saying that the compiler will support it and if the compiler changes, they authors will also change the library. If you rely on this behavior, theres no guarantee that the compiler wont change this behavior in a future update thereby breaking your code.
- aidenn0 7y agoIt will only ever be compiled with clang, so as long as clang doesn't implement this behavior in a way that will cause it to be incorrect, that's fine. If it were to be special-cased, it would probably require an attribute or a pragma or something. While it's not unheard of for compilers to automatically detect they are compiling the standard library, it's fairly rare.
- deleted 7y ago
- jnordwick 7y agoDoes anybody know why vector isn't allowed short buffer optimization or if it will be changed in the future?
- SamReidHughes 7y agoThe swap method requires that pointers or iterators don't get invalidated.
- gpderetta 7y agoYou could say that while most string are small, vectors are all kind of sizes and the T size itself can be large, so the optimization is less of a win in for a general purpose container. But it is mostly for historical reasons. I believe the original STL used the SSO optimiziation [1], so there was never any assumption about the stability of references to string elements, while there is a lot of code that assumes that references to vector elements do not change. [1] The SGI STL, direclty derived from the original HP STL had extensive rationale on why it didn't implement COW; libstdc++, which I believe also traces its roots from it, decided to instead do COW. The rest is history.
- huhtenberg 7y agoIn situations when there might be a lot of _empty_ strings, the 'capacity' and 'size' can be taken out of the fixed part and bundled with the data instead. This will bring sizeof(string) to a size of a single pointer and will still allow for short strings of 7 chars (in 64-bit builds). Memory allocations are usually aligned by default, so the pointers will have at least one lower bit cleared and available to be used as a mode flag. If in doubt, allocating through aligned_alloc(2,...) will guarantee an unused bit in a pointer.
- gpderetta 7y agoYes, sometimes it is worth to optimize for size, especially if the string is actually not used in any fast path and just need to be there. I'll mention though that std::string (well, basic_string) takes an allocator parameter, so it could only enable this optimization for 'well known' allocators that provide aligned buffers.
- amelius 7y agoIsn't the __cap__ field available also inside the malloc block header, so couldn't this field be optimized out of the std::string implementation?
- thedance 7y agoNo. You can’t make assumptions about how global operator new works. Allocators like tcmalloc are allowed to override it. And string can be instantiated with any stl allocator, so it might never call ::new anyway.