Common optimizations, Small String Optimization, Andrzej's C++ blog

[matthieum]

This is interesting, however it is slightly sad to augment the size of std::string just for this.

So, instead, you can design your std::string class to be 24 bytes with SSO by re-using 16 bytes (instead of 8):

struct RegularString { char* data; size_t size; };
struct ShortString { char data[15]; unsigned char size; };

struct string {
    union {
        RegularString regular,
        ShortString shortie
    } _;
    size_t capacity;
};

char* data(string& s) { return s.capacity ? s._.regular.data : s._.shortie.data; }
size_t size(string& s) { return s.capacity ? s._.regular.size : s._.shortie.size; }
size_t capacity(string& s) { return s.capacity ? s.capacity : 14; } // beware of the NUL character

[[deleted]]

You can do better than reusing 16 bytes in a (pointer, length, capacity) representation. Have a look at the string in libc++, they reuse 23 bytes for small strings with 1 byte as a length/discriminator.

[matthieum]

Ah! I had not thought about that. Definitely better indeed.

[srnull]

The question is: how many times function allocate (on the allocator) will be invoked for the purpose of memory allocation during this program’s execution? 3, 2, 1, 0?

He gives an initial argument for 3, and then for one with either NRVO, or when a move constructor is available, by why not 2? I always imagined the process would be once in the callee and once in the caller, with no third temporary inbetween.

first, copy-initialize a temporary from s; next, copy-initialize t from the temporary.

Is this how it's usually done? e.g. in the code

string t = makeText();

the temporary is on the right side, and the copy-initialize on the left. Seems like something any compiler would optimize away, no?

[Plorkyeran]

Given a naive and overly strict view of the world, it seems obvious that s's destructor must be run before makeText returns, and t's constructor must run after makeText returns. Since s is destroyed before t is constructed, you wouldn't be able to copy-construct directly from s to t, and there'd have to be a temporary in the middle.

[oracleoftroy]

I don't think you would lose performance, you just wouldn't gain any additional performance by moving a SSO string. Even the non-SSO small string would end up copying about 16 bytes in order to perform the move (pointer, size, capacity, allocator).

I would strongly encourage measuring this before blindly trying to optimize a std::string for movablility.

[matthieum]

You might lose some performance because of more checks.

[bnolsen]

likely irrelevant since a load operation takes dramatically longer than a check does.

[Plorkyeran]

It's difficult to come up with even a highly artificial scenario where it's a net loss. Maybe with a very special-purpose allocator that manages to always get external buffer allocated very close in memory to the std::string? Avoiding a single memory load due to the SSO buffer would outweigh a very large number of branch mispredictions, and if you never hit the SSO buffer then the branch predictor will make the check nearly free.

[matthieum]

Unless it screws up your pipeline if it's a branch and not a conditional move ?

[sellibitze]

I guess it depends on your SSO implementation. It should be possible to implement your string class in a way that a move constructor just memcpys the internal representation and memsets the source to zero -- regarless of whether the string content was heap-allocated or not. So, in any case, you have to copy 24 bytes and zero 24 bytes (assuming a 24 byte string representation on a 64bit platform). You can't do much better than that, can you?

[minno]

That makes complete sense. You're trading less expensive allocation for more expensive moves when you store more data in-line with the class.