5 ms·

hey 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

hey 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 ago
Do 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 ago
  Just 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 ago
  Afaik it costs you some performance for long string operations.
- OskarS 7y ago
  I 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.
  - acqq 7y ago
    > 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 The "optimal" implementation would actually have different allocation sizes when used mostly for processing and when used mostly for storage: for processing one would prefer bigger defaults, for storage, one needs as little as possible initial overhead. That could be achieved by raising the knowledge of that distinction and introducing actually (at least) two kind of strings. And even more than that can be gained by recognizing that whenever the strings are involved in some more complex structures, some additional restrictions for totality of all associated strings could also be exploited: allocating the strings separately is an overhead by itself. If I remember correctly, Turbo Pascal strings had the default size of 256 bytes and that's how much was on the stack for each, and that was fast even decades ago. That was not efficient for having a lot of them in the structures, if a lot of them could be smaller, but that was what a programmer had to care separately - still the typical processing of strings and working with the limited number of them was nicely covered by that default.
- bregma 7y ago
  > Do you happen to know why the standard doesn’t use that trick? Many of the early implementations of `std::string` were COW (copy-on-write), which is not entirely compatible with SSO strings. In practice, COW strings proved to be troublesome and slow, and the SSO strings won out. The standard was changed to effectively mandate SSO strings and forbid COW strings.
  - bodyfour 7y ago
    In the early days of std::string multi-threading was much rarer, so reference counting was cheaper. As CPU count grows the relative cost of needing an atomic refcount on every string also grew. The COW strings also were a constant source of surprising behavior. As with any COW object you have to make sure that the copy happens before and write. Simple enough, but the STL-style interface does not support this well. All you had to do is call operator[] or begin() on a non-const std::string and it would force a copy. This meant that something that to the programmer clearly looked like a read-only operation like: if (str[2] == 'x') { ...} ...could end up copying the string. Worse, it also meant that any previously taken references are now invalidated. This lead to horrible bugs where you would hold a pointer at the previous copy of the string (which you no longer own a refcount on) and it would almost always work... but every so often another thread would come by and reuse the memory behind your back. So COW std::string was a long festering mess in C++. Their removal in C++11 was completely warranted.

tybit 7y ago

Do 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 ago
Just 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 ago
Afaik it costs you some performance for long string operations.
OskarS 7y ago
I 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.
- acqq 7y ago
  > 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 The "optimal" implementation would actually have different allocation sizes when used mostly for processing and when used mostly for storage: for processing one would prefer bigger defaults, for storage, one needs as little as possible initial overhead. That could be achieved by raising the knowledge of that distinction and introducing actually (at least) two kind of strings. And even more than that can be gained by recognizing that whenever the strings are involved in some more complex structures, some additional restrictions for totality of all associated strings could also be exploited: allocating the strings separately is an overhead by itself. If I remember correctly, Turbo Pascal strings had the default size of 256 bytes and that's how much was on the stack for each, and that was fast even decades ago. That was not efficient for having a lot of them in the structures, if a lot of them could be smaller, but that was what a programmer had to care separately - still the typical processing of strings and working with the limited number of them was nicely covered by that default.
bregma 7y ago
> Do you happen to know why the standard doesn’t use that trick? Many of the early implementations of `std::string` were COW (copy-on-write), which is not entirely compatible with SSO strings. In practice, COW strings proved to be troublesome and slow, and the SSO strings won out. The standard was changed to effectively mandate SSO strings and forbid COW strings.
- bodyfour 7y ago
  In the early days of std::string multi-threading was much rarer, so reference counting was cheaper. As CPU count grows the relative cost of needing an atomic refcount on every string also grew. The COW strings also were a constant source of surprising behavior. As with any COW object you have to make sure that the copy happens before and write. Simple enough, but the STL-style interface does not support this well. All you had to do is call operator[] or begin() on a non-const std::string and it would force a copy. This meant that something that to the programmer clearly looked like a read-only operation like: if (str[2] == 'x') { ...} ...could end up copying the string. Worse, it also meant that any previously taken references are now invalidated. This lead to horrible bugs where you would hold a pointer at the previous copy of the string (which you no longer own a refcount on) and it would almost always work... but every so often another thread would come by and reuse the memory behind your back. So COW std::string was a long festering mess in C++. Their removal in C++11 was completely warranted.