News for hackers. Stuff that matters.
Re:Small Strings in Rust: smolstr vs. smartstring by dataflow on Saturday August 24, 2024 @12:30PM (#41339357)
Note for C++ developers: Their trick is only possible because the strings are UTF-8 and not null-terminated. It wouldn't work as a drop-in for standard strings in C++.
Re:Small Strings in Rust: smolstr vs. smartstring by kloop on Saturday August 24, 2024 @01:03PM (#41339599)
std::string isn't null terminated (or at least it isn't guaranteed to be, I don't think it's forbidden for an implementation to do that).

That's why the c_str method exists, so you can get a pointer to a null terminated character array

Re:Small Strings in Rust: smolstr vs. smartstring by dataflow on Saturday August 24, 2024 @01:17PM (#41339702)
> std::string isn't null terminated

It is as of C++11. The constness of c_str() threw a wrench into that as soon as C++ got a threading model.

Re:Small Strings in Rust: smolstr vs. smartstring by unclad5968 on Saturday August 24, 2024 @01:16PM (#41339688)
std::string is guaranteed to be null terminated since c++11.

std::string::c_str returns the same address as &string[0]

Re:Small Strings in Rust: smolstr vs. smartstring by dataflow on Saturday August 24, 2024 @01:20PM (#41339728)
> std::string::c_str returns the same address as &string[0]

Note that this by itself doesn't imply null-termination, though as you say strings are indeed null-terminated now.

Edit: This is not particularly obvious, but the reason this has nothing to do with allocation or the return value is that the implementation could still leave space for the null terminator, but avoid actually setting it to zero until c_str() is invoked. That would neither affect the returned pointer nor the constant-time guarantee.

Re:Small Strings in Rust: smolstr vs. smartstring by masspro on Saturday August 24, 2024 @02:00PM (#41340037)
Why downvotes? Ignoring C++11 changes for a minute, c_str is absolutely able to cause a reallocation if it needs to, such that after it returns, its return value and the value of data() are the same. Ergo no, the GP statement alone doesn’t imply anything.
Re:Small Strings in Rust: smolstr vs. smartstring by dpassens on Saturday August 24, 2024 @02:29PM (#41340289)
But the return value guarantee is, as far as I can see, a C++11 change, so you can't ignore those. And as of C++11, c_str is noexcept, so it cannot allocate anything.
Re:Small Strings in Rust: smolstr vs. smartstring by dataflow on Saturday August 24, 2024 @03:08PM (#41340616)
Please see my edit.
Re:Small Strings in Rust: smolstr vs. smartstring by dietr1ch on Saturday August 24, 2024 @09:42PM (#41343606)
Shouldn't c_str() be null terminated? Then if it must point to the actual backing store, then that must also be a valid null terminated C string as there's no other way to use them.
Re:Small Strings in Rust: smolstr vs. smartstring by dataflow on Saturday August 24, 2024 @11:48PM (#41344210)
> Shouldn't c_str() be null terminated?

Yes, by definition.

> Then if it must point to the actual backing store, then that must also be a valid null terminated C string as there's no other way to use them.

No, this doesn't follow. The buffer could leave room for the terminator but not actually write the terminator until c_str() is called. That's why the C++11 standard had to explicitly require that the string always be null-terminated regardless of whether c_str() is called.

Re:Small Strings in Rust: smolstr vs. smartstring by dietr1ch on Sunday August 25, 2024 @04:39AM (#41345614)
Wow, I didn't expect `c_str()` to write at all. I knew that C++ was wild before C++57, but before C++ is insane.

Thanks for the explanation!

Re:Small Strings in Rust: smolstr vs. smartstring by jcelerier on Sunday August 25, 2024 @08:32AM (#41346845)
I don't think any implementation ever did this. But it was "technically possible" as the spec didn't prevent it so you have to account for it.
Re:Small Strings in Rust: smolstr vs. smartstring by searealist on Saturday August 24, 2024 @01:07PM (#41339622)
I think std::string is actually required to be null terminated now in the latest standards. But even before it was basically required as that was the only way to make c_str() constant time.
Re:Small Strings in Rust: smolstr vs. smartstring by dataflow on Saturday August 24, 2024 @01:24PM (#41339760)
> But even before it was basically required as that was the only way to make c_str() constant time.

Note that c_str() could've inserted the terminator in constant time, as long as the string kept space reserved for that. So this wouldn't have violated constant-time-ness, and it's not an insane thing to do considering it would save some instructions elsewhere. But yeah, the flexibility wasn't all that useful even in the beginning, and became even more useless as soon as C++ incorporated threading, due to the constness of the function.

Re:Small Strings in Rust: smolstr vs. smartstring by mananaysiempre on Saturday August 24, 2024 @02:24PM (#41340251)
More of a knock against C than C++, seeing as today’s C++ tends to prefer `string_view`s or at worst iterator pairs, neither of which use null-termination. (Saying that as someone who prefers C to C++ and avoids Rust exactly because of “better C++” vibes—I don’t want a better version of C++, if anything I want a much much simpler one that’s worse at some things.)

That said, I don’t see why it wouldn’t be possible to cram in 24 bytes of null-terminated payload (so 23 useful ones, the best you could hope for with null termination) into the same structure the same way by storing the compact version with null termination and ensuring the last byte is also always zero. For extra style points, define the last byte to be 24 minus payload length instead so you don’t need to recompute the length in the inline case.

To be clear: none of this makes null termination not dumb.

Re:Small Strings in Rust: smolstr vs. smartstring by aw1621107 on Saturday August 24, 2024 @02:51PM (#41340484)
> That said, I don’t see why it wouldn’t be possible to cram in 24 bytes of null-terminated payload (so 23 useful ones, the best you could hope for with null termination) into the same structure the same way by storing the compact version with null termination and ensuring the last byte is also always zero.

I want to say libc++ and maybe MSVC do something along those lines in their std::string implementations.

> For extra style points, define the last byte to be 24 minus payload length instead so you don’t need to recompute the length in the inline case.

IIRC Facebook's FBString from Folly does (did?) that?

Re:Small Strings in Rust: smolstr vs. smartstring by tialaramex on Saturday August 24, 2024 @04:27PM (#41341231)
> I want to say libc++ and maybe MSVC do something along those lines in their std::string implementations.

Here's Raymond Chen on this topic earlier this same year. As a bonus since you're looking at this in August it's more or less correct now, whereas when it was published it had numerous serious errors. Whether the standard library implementation of such an important type should be so complicated that an expert makes numerous errors is another question...

https://devblogs.microsoft.com/oldnewthing/20240510-00/?p=10...

So, libc++ gets closest, 1 flag byte + 22 bytes of text + 1 byte of ASCII NUL = 24 bytes

The others are much worse, larger (32 bytes on modern computers) yet with lower SSO capacity (15 bytes of text).

Re:Small Strings in Rust: smolstr vs. smartstring by aw1621107 on Saturday August 24, 2024 @07:53PM (#41342962)
Huh, I thought MSVC had a libc++-style SSO implementation. Now I have to wonder where I got that mistaken impression :(
Re:Small Strings in Rust: smolstr vs. smartstring by dataflow on Saturday August 24, 2024 @02:43PM (#41340417)
> That said, I don’t see why it wouldn’t be possible to cram in 24 bytes of null-terminated payload

Note that I didn't say this is impossible, just that the given trick wouldn't work.

However, this is impossible for general strings. The only way could possibly make this work is if you constrain the inline string somehow (e.g., to UTF-8), so that some shorter strings failing that constraint are forced to go on the heap too. Otherwise you have 1 fixed zero byte at the end, and 23 fully flexible bytes, leaving you no way to represent an out-of-line string.

(Well, you could do it if you use the address as a key into some static map or such where you shove the real data, but that's cheating and beside the point here.)

Re:Small Strings in Rust: smolstr vs. smartstring by Dylan16807 on Sunday August 25, 2024 @09:36AM (#41347212)
Think that through again. An inline string needs a fixed 0 byte at the end. A heap string does not. Therefore if the last byte is anything other than 0 you have a heap string.

Inline strings only use 0.4% of your possible values.

Re:Small Strings in Rust: smolstr vs. smartstring by dataflow on Sunday August 25, 2024 @09:44AM (#41347264)
Oof, you're right, thank you. In my mind the last byte was obviously zero for a heap string too, since the pointer or sizes would've had a zero upper byte. Somehow I never accounted for the fact that on 64-bit there's no need to represent it that way. Fantastic point!
Re:Small Strings in Rust: smolstr vs. smartstring by neonsunset on Saturday August 24, 2024 @01:18PM (#41339706)
Null-terminated strings really are a mistake. Make vectorized algorithms problematic by forcing them to account for page size and paged memory in general as well as always scan for NUL, cannot be easily sliced without re-allocation, are opposite to how languages with better string primitives define them and in general don't save much by passing a single pointer over ptr + length.
Re:Small Strings in Rust: smolstr vs. smartstring by andersa on Saturday August 24, 2024 @10:02PM (#41343702)
It's not really possible to get rid of them in C++ however, given a staggering amount of legacy APIs that require them. Constantly converting every time you have to call a system API with your string is even worse.
Re:Small Strings in Rust: smolstr vs. smartstring by anp on Saturday August 24, 2024 @11:03PM (#41344009)
FWIW Rust also has null-terminated strings available under its std::ffi module. I’m not sure it would be feasible to migrate C++ to the approach of multiple string types now, and I’m not sure it would have been the right approach for C++11 given C++’s approach to interop, but it’s definitely possible to support interoperability with those legacy APIs without constraining a default string type to null-termination.