C++ Weekly - Ep 430 - How Short String Optimizations Work
ฝัง
- เผยแพร่เมื่อ 7 ก.พ. 2025
- ☟☟ Awesome T-Shirts! Sponsors! Books! ☟☟
Upcoming Workshops:
► C++ Best Practices Workshop, ACCU, Bristol UK, Mar 31, 2025: accuconference...
CLion is a cross-platform JetBrains IDE for C and C++ with:
A smart C and C++ editor to navigate and maintain your code base productively.
Code analysis with quick-fixes to identify and fix bugs and style inconsistencies.
An integrated debugger - along with other essential tools from the ecosystem - available
straight out of the box.
And much more!
jb.gg/clion_ide code: CppWeeklyCLion
Episode details: github.com/lef...
T-SHIRTS AVAILABLE!
► The best C++ T-Shirts anywhere! my-store-d16a2...
WANT MORE JASON?
► My Training Classes: emptycrate.com/...
► Follow me on twitter: / lefticus
SUPPORT THE CHANNEL
► Patreon: / lefticus
► Github Sponsors: github.com/spo...
► Paypal Donation: www.paypal.com...
GET INVOLVED
► Video Idea List: github.com/lef...
JASON'S BOOKS
► C++23 Best Practices
Amazon Paperback: amzn.to/47MEAhj
Leanpub Ebook: leanpub.com/cp...
► C++ Best Practices
Amazon Paperback: amzn.to/3wpAU3Z
Leanpub Ebook: leanpub.com/cp...
JASON'S PUZZLE BOOKS
► Object Lifetime Puzzlers Book 1
Amazon Paperback: amzn.to/3g6Ervj
Leanpub Ebook: leanpub.com/ob...
► Object Lifetime Puzzlers Book 2
Amazon Paperback: amzn.to/3whdUDU
Leanpub Ebook: leanpub.com/ob...
► Object Lifetime Puzzlers Book 3
Leanpub Ebook: leanpub.com/ob...
► Copy and Reference Puzzlers Book 1
Amazon Paperback: amzn.to/3g7ZVb9
Leanpub Ebook: leanpub.com/co...
► Copy and Reference Puzzlers Book 2
Amazon Paperback: amzn.to/3X1LOIx
Leanpub Ebook: leanpub.com/co...
► Copy and Reference Puzzlers Book 3
Leanpub Ebook: leanpub.com/co...
► OpCode Puzzlers Book 1
Amazon Paperback: amzn.to/3KCNJg6
Leanpub Ebook: leanpub.com/op...
RECOMMENDED BOOKS
► Bjarne Stroustrup's A Tour of C++ (now with C++20/23!): amzn.to/3X4Wypr
AWESOME PROJECTS
► The C++ Starter Project - Gets you started with Best Practices Quickly - github.com/cpp...
► C++ Best Practices Forkable Coding Standards - github.com/cpp...
O'Reilly VIDEOS
► Inheritance and Polymorphism in C++ - www.oreilly.co...
► Learning C++ Best Practices - www.oreilly.co...
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
I think this has to be one of the coolest examples on how and why to use constexpr.
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.
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.
I'm way more sold on the benefit of constexpr/consteval after seeing this.
Yeah, I'm still refining the way I present this stuff. This is a really good argument for it!
A good exercise is implementing small object optimised vector
constexpr is essentially a compile-time UB sanitizer😮
constexpr all the things!
awesome one!
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…
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.
Raymond Chen has written a great post (Inside STL: The string) about this.
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
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
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.
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. ;-)
Did you implement a copy on write string?
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. 🤯
That sounds like UB, given that the compiler is free to add padding to its liking.
@@higaski This trick that @user-cy1m5vb71 uses, could be put into yet another union, and thus you'd know about the packing.
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
@@Raspredval1337 I don’t get this approach. Won’t requesting c_str for a small string not be guaranteed-null-terminated?
@@RevolutionaryUsernameif 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
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.
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.
Oh and he won't be able to use the bits on either end, the most significant bit is more apt.
honestly I'd rather if small string was a different type, maybe something like:
small_string str;
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.
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)
Isn’t std::size_t in not ?
Yeah
I often get that one wrong - sorry!
Would love to see a std::variant version
Maybe to avoid std::visit and lambda pain?
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.
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? 🤔
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.
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.
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.
@@cppweekly The issue is that for some types, explicit destructor calls and placement new expressions are the way to change a union’s active member (cf. C++20, §11.5, p 7). This seems to make launder necessary, but I’ve never seen anyone address this.
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.
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
@@antonpieper Yes the check has to be done for any of the modifying operations I guess.
I think the real optimization would be just to make the most significant bit of the size a flag
@@Mozartenhimer Doesnt that reduce the max size of the container? It's an undefined integer type so all the bits are used.
@@mjKlaim I don't think you'll miss that 9.2 exabytes.
cool