Hacker News Reader

Comment by yongjik | Hacker News Reader

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.

View on HN

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.

> 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 )`

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.

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..

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...

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).

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.

It is relevant to the memory usage.

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.

Reply on news.ycombinator.com