8 ms·
Reminds 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 t
by dylanmclark 7y ago
Reminds 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...