5 ms·

I 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

I 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 ago
I'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 ago
  It is relevant to the memory usage.
vnorilo 7y ago
You 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 )`
  - vnorilo 7y ago
    In isolation, yes. Predictor resources are not infinite. Predictable is better than dynamic, but no branch is optimal. Consider the implications to inlining: the size getter is a prime candidate, but suddenly it gets less predictor-friendly. Edit: this is naturally a good case for manual hinting.
usefulcat 7y ago
It could be done as you say, in 16 bytes (assuming 64 bit pointers): struct not_too_long_string { char* data; uint32_t size; uint32_t capacity; }; Of course, if you do it that way then the longest string you can store with the small string optimization is probably ~15 bytes instead of ~23. So although you do save 1/3 on the size of each string, on average you're probably still going to end up doing a greater number of dynamic allocations because of the reduced small string capacity. Unless of course you know a priori that a sufficiently large portion of your strings will be > 15 bytes anyway, which of course the implementors of std::string almost certainly don't know. Edit: I failed to notice the part about the length being in the data block (doh). I guess the disadvantage to putting the length there would be that an extra indirection is required to get the length, a rather common operation. And as others have pointed out, that only saves 4 bytes, which will be used anyway for alignment..
- yongjik 7y ago
  Eh, I was thinking about pretty much exactly what you said. "Length in the data block" would be when length doesn't fit in 32 bits. (I.e. >2GB or maybe >4GB.) It would require an additional branch to test for huge strings, but it will be almost never executed, and I think modern CPUs are pretty good at optimizing out such branches...
- jcranmer 7y ago
  If you want to get really fancy, you can do it in 8 bytes. Pointers are only 48-bits on 64-bits, so you can squeeze a 16-bit size field. If size overflows that, then you can use a cookie before the data string to find the size. Capacity could be stored in such a cookie, or junked entirely and you rely on your memory allocator to get the size of the allocation (small-string optimization obviously not even being considered in this model).
gpderetta 7y ago
They do run bechmarks, but of course it is anyone guess how significant and representative they are. At the end of the day it is a long list of tradeoff. You pick one point in the option space and hope to have gotten it right, because it will enshrined in the ABI for a very long time.

dc443 7y ago

I'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 ago
It is relevant to the memory usage.

vnorilo 7y ago

You 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 )`
- vnorilo 7y ago
  In isolation, yes. Predictor resources are not infinite. Predictable is better than dynamic, but no branch is optimal. Consider the implications to inlining: the size getter is a prime candidate, but suddenly it gets less predictor-friendly. Edit: this is naturally a good case for manual hinting.

usefulcat 7y ago

It could be done as you say, in 16 bytes (assuming 64 bit pointers): struct not_too_long_string { char* data; uint32_t size; uint32_t capacity; }; Of course, if you do it that way then the longest string you can store with the small string optimization is probably ~15 bytes instead of ~23. So although you do save 1/3 on the size of each string, on average you're probably still going to end up doing a greater number of dynamic allocations because of the reduced small string capacity. Unless of course you know a priori that a sufficiently large portion of your strings will be > 15 bytes anyway, which of course the implementors of std::string almost certainly don't know. Edit: I failed to notice the part about the length being in the data block (doh). I guess the disadvantage to putting the length there would be that an extra indirection is required to get the length, a rather common operation. And as others have pointed out, that only saves 4 bytes, which will be used anyway for alignment..

yongjik 7y ago
Eh, I was thinking about pretty much exactly what you said. "Length in the data block" would be when length doesn't fit in 32 bits. (I.e. >2GB or maybe >4GB.) It would require an additional branch to test for huge strings, but it will be almost never executed, and I think modern CPUs are pretty good at optimizing out such branches...
jcranmer 7y ago
If you want to get really fancy, you can do it in 8 bytes. Pointers are only 48-bits on 64-bits, so you can squeeze a 16-bit size field. If size overflows that, then you can use a cookie before the data string to find the size. Capacity could be stored in such a cookie, or junked entirely and you rely on your memory allocator to get the size of the allocation (small-string optimization obviously not even being considered in this model).

gpderetta 7y ago

They do run bechmarks, but of course it is anyone guess how significant and representative they are. At the end of the day it is a long list of tradeoff. You pick one point in the option space and hope to have gotten it right, because it will enshrined in the ABI for a very long time.