C++ Weekly - Ep 430 - How Short String Optimizations Work

[@cppweekly]

There were a couple of bugs in the implementation that GCC let slide - mostly around the use of initializing / assigning C-style arrays. Thanks to a viewer for pointing that out. Here's an updated version that works on GCC/Clang/MSVC compiler-explorer.com/z/3ecYaKK8e

[@nyyakko]

I think this has to be one of the coolest examples on how and why to use constexpr.

[@patrix9999]

Yep, i've been writing my own custom string class implementation and i had to debug such cases at runtime which take me quite some time to make it right, whereas constexpr simply allow us to see the problem at compile time, which is very useful.

[@mCoding]

Top notch! You did a great job showing off the core ideas of SSO/SOO that can be adapted to any dev's situation while not getting bogged down by hyper-optimizations.

[@negidrums915]

constexpr is essentially a compile-time UB sanitizer😮

[@cppweekly]

constexpr all the things!

[@Xilefian]

A good exercise is implementing small object optimised vector

[@sirhenrystalwart8303]

I'm way more sold on the benefit of constexpr/consteval after seeing this.

[@cppweekly]

Yeah, I'm still refining the way I present this stuff. This is a really good argument for it!

[@Raspredval1337]

I've just googled this topic today! PS: one could pack the small string even tighter, there's a way to use single byte for a size, but you'd store the max_small_string_capacity minus size instead. When the small string size equals the max capacity, the capacity minus size becomes zero and acts as a null terminator. 🤯

[@higaski]

That sounds like UB, given that the compiler is free to add padding to its liking.

[@garyp.7501]

@@higaski This trick that @user-cy1m5vb71 uses, could be put into yet another union, and thus you'd know about the packing.

[@Raspredval1337]

struct string { struct s_large { char* data; // assuming it's a 64bit pointer uint64_t size; // maybe even some padding to add extra stack space // like char padding[8]; }; struct s_small { static constexpr max_capacity = sizeof(s_large); char data[sizeof(heap) - 1]; char max_capacity_minus_size; }; uint64_t capacity; union { s_large l; s_small s; } data; }; even if there's some alignment padding added to the members of the s_large, the s_small should still be fine

[@UsernameUsername0000]

@@Raspredval1337 I don’t get this approach. Won’t requesting c_str for a small string not be guaranteed-null-terminated?

[@Raspredval1337]

@@UsernameUsername0000if the whole small string storage is zero initialized, then it will be. Plus, when the small string size would be equal to it's capacity, the last byte (capacity_minus_size) would be equal to zero, thus acting as a null terminator

[@Subdest]

Why Boolean needed to check if it is a small object? Size is present. Max size of small object also is known. I doubt that checking Boolean is much faster then checking if some value is less then a constant…

[@hampus23]

Well, if you shrink the heap allocated string you don't reallocate so that won't work but there are better ways to do this.

[@hampus23]

Raymond Chen has written a great post (Inside STL: The string) about this.

[@garyp.7501]

If the string is shrunk, ie a short string is put into a what was a long string, you'd have to be sure to deallocate the extra space. That might be surprising to some users. Ie, long string, ... allocate short string ... deallocate long string ... allocate again. Vs long string .. allocate short string, .... no deallocation long but not too long string ... also no reallocation

[@Raspredval1337]

size can be zero even if it's a heap-allocated string. But capacity does reflect it's nature tho, you can use that, as long as heap allocated capacity is always larger than the max small string capacity

[@cppweekly]

Because it's possible I grew the string bigger than small object size, allocated, then shrunk the string later and don't want to copy data / deallocate storage.

[@hwstar9416]

honestly I'd rather if small string was a different type, maybe something like: small_string str;

[@ohwow2074]

I don't know why they didn't choose to do that in the first place. Just let the user specify the size of the small buffer based on their needs. Now we're limited to a 16 byte buffer.

[@lkedvenc6898]

I have implemented my own string class and the idea was quite similar. The regular std::string ruins the heap if you use it very frequently. Of course my string was better. ;-)

[@cyrilemeka6987]

Did you implement a copy on write string?

[@mjKlaim]

I would have made `is_small_storage()` a function which returns either `m_size < ` an arbitrary constant or the result of `m_size < sizeof(small_storage)` (so no additional storage needed for the bool). In several functions we would then need to re-evaluate this but I think it's worth it as it takes less space.

[@antonpieper]

Also, a "problem" with this and the video version is that the assignment operator would need to deallocate the memory if you assign a small string to a previously large string, because you would loose the pointer location

[@mjKlaim]

@@antonpieper Yes the check has to be done for any of the modifying operations I guess.

[@Mozartenhimer]

I think the real optimization would be just to make the most significant bit of the size a flag

[@mjKlaim]

@@Mozartenhimer Doesnt that reduce the max size of the container? It's an undefined integer type so all the bits are used.

[@Mozartenhimer]

@@mjKlaim I don't think you'll miss that 9.2 exabytes.

[@FedericoPekin]

awesome one!

[@garyp.7501]

To pack this object into something even smaller in space you could use a bit field for the m_size, and while you can't allocate a string that is unsigned int64, you can allocate a unsigned int63. And use a bit at either end to indicate whether the space was allocated on the heap or using your m_small field of your other union. There of course is a minimal overhead of looking at those bit fields vs a bool or the int, but this is a thing that maps doing red/black do.

[@cyrilemeka6987]

The overhead of bit manipulation should be minimal or non-existent. Computers leave and breathe for those operations, I implemented a u8char class that unfortunately doesn't cache the calculated unicode code-point due to memory concerns, but retrieving the unicode code points from the utf-8 encoded text is a relatively fast operation due to switching over to bit manipulation instead of using std::string and std::bitset which were really costly operations.

[@cyrilemeka6987]

Oh and he won't be able to use the bits on either end, the most significant bit is more apt.

[@PaulMetalhero]

Would love to see a std::variant version

[@cyrilemeka6987]

Maybe to avoid std::visit and lambda pain?

[@anon_y_mousse]

The only thing I dislike here, as usual, is all of the boilerplate code. However, if they incorporate such a string type into the standard then that goes away because you won't have to implement it yourself, and in such a case I would have no complaints.

[@UsernameUsername0000]

Isn’t std::size_t in not ?

[@ohwow2074]

Yeah

[@cppweekly]

I often get that one wrong - sorry!

[@HinaraT]

I think I would have use the capacity has the common field instead of the size because if for example you modify the length of your string a lot between let say 12 and 20 characters your solution force you to allocate deallocate each time you cross the 16 byte boundary. Whereas the capacity can stay at ~20 while your size can move around as it want. To use capacity instead we can say that size() = capacity when capacity < 16 else size and capacity() = max(16,capacity)

[@Raspredval1337]

btw, offtopic question: since you really shouldn't store a function address in a void pointer, it's recommended to use a dummy function pointer type instead. The question is: can you reliably store a method pointer into this dummy function pointer type? Or what can you use instead of a void pointer to store a method pointer? 🤔

[@cppweekly]

I've never heard of this recommendation to use a dummy function pointer type instead. I just double checked and cast to and from void * is allowed as of C++11. The problem is that it's less portable - on something like harvard architecture you might actually have different sized pointers between function pointer and memory pointer types... I would personally still use void * when I need to do that. So, I have no specifically clear guidance here.

[@pierrecolin6376]

Is std::launder necessary for unions? I know the answer is no when the data members are active only once in the lifetime of the union, but this is not the case here.

[@cppweekly]

I believe launder is only necessary in the case of something like placement new(), en.cppreference.com/w/cpp/utility/launder there's no mention of unions there.

[@EgorChebotarev]

cool