Short String optimization

1

Has there been any discussion of having String live entirely on the stack for len < size_of::<usize>() * n? Imagine

enum StringInner {
    Stack {
        len: u8,
        bytes: [u8; N],
    },
    Heap(Vec<u8>),
}

Of course, off the top of my head I don’t know how well this plays with existing APIs, but I wanted to put down the idea for discussion before I mull it over more.

Note that this is the same size of the current String, if we use StringInner::Heap.0's RawVec's Unique as a niche. I have no idea if @eddyb’s work on niches can handle something like this, though.

3

We guarantee that we will never perform this optimization for Vec: https://doc.rust-lang.org/std/vec/struct.Vec.html#guarantees. I don’t think the same is explicitly documented for String, but String is simply a wrapper around Vec so it still holds there at least in practice.

3 Likes
4

And that guarantee of indirection is necessary for StableDeref to work.

1 Like
5

I think the assumption here that unsafe impl StableDeref for String {} was made in error and thus it would be entirely legitimate for T-libs to break it if they want to because no such guarantee was ever given.

3 Likes
6

Short string optimization is often regarded as a quite important optimization. But do we have benchmarks that compare the performance of the current String to the performance of a Short-string-optimized type in a some reasonable real programs/libraries? :slight_smile:

7

I’m not aware of this myself, but I believe the Tendril crate is relevant here. We could always do benchmarks in the future to see if such a change would be worth it =)

8

String docs do make a number of other promises that are hard to keep if it does not share its representation with Vec<u8>. For example, String::into_bytes says that it does not copy the contents.

7 Likes
9

There have been some conversations in the past:

and

2 Likes
10

I don’t think there’s any choice of N here that’s obviously-correct, so I prefer having both String as today with some sort of SmallString, like we have Vec and the smallvec crate.

5 Likes
11

The importance of this optimization is perhaps less in Rust, which has safe string slices permeating its APIs, lessening the amount of string allocation and copying that goes on.

7 Likes
12

The String docs also talk about its representation and says the buffer is always allocated on the heap.

3 Likes
13

Note that since we do not technically guarantee it for String, StableDeref is playing a risky business here.

1 Like
14

I agree that StableDeref took a risk, but since we know that code exists, we should think carefully whether it’s worth breaking them. Or we can just codify that guarantee for String and leave SSO to something like SmallString.

1 Like
15

Well, there is technically a rather nasty way out of this. I’ll note that I think this is a bad hack, and that guaranteeing that String is a newtype over Vec<u8> is a mistake.

Since things only break down when we give out references to things inside of String, we could treat SSO as a “deferred” allocation; anything that semantically gives out addresses into a String would trigger an allocation. Unfortunately, this means introducing interior mutability, since we’d need to mutate inside of Deref::deref…

16

This includes calling any &str methods on the String, and it would mean that almost any actual usage of the string's contents would prevent it from remaining on the stack.

1 Like
17

I did say it was a bad hack.

2 Likes
18

Yup. The guarantees aren't as iron-clad as those of Vec, but they do seem to suggest that a non-empty String is always heap-allocated. From the docs for String:

Representation

A String is made up of three components: a pointer to some bytes, a length, and a capacity. The pointer points to an internal buffer String uses to store its data. The length is the number of bytes currently stored in the buffer, and the capacity is the size of the buffer in bytes. As such, the length will always be less than or equal to the capacity.

This buffer is always stored on the heap.

1 Like
19

Is there actually reason to believe that the majority of use cases for std strings would benefit from SSO?

Most of the time we can use slices instead of owned strings (at least when it comes to typical situations where one uses a huge amount of very small strings, where SSO strings shine), curtesy of the borrow checker and all that :wink: Just because C++ does it it does not mean its a win for us too.

7 Likes
20

I remember that in those old dicussions it was said that C++ benefits from SSO because empty std::string has to contain terminating \0 and empty strings are actually very frequent. Rust does not allocate for empty strings. On the other hand SSO adds to program size by adding branches into every use of string. I am not going to search for it and my memory may be failing me but there were some posts that stated that it was measured and tested programs ran faster without SSO.

3 Likes
21

It definitely sounds like SSO isn’t quite as useful for Rust; std::string is pretty pervasive in C++, and things like e.g. absl::string_view are not nearly as pleasant to use as &str.

I might argue, though, that while branching will increase binary size, I think it might actually be valuable to be able to turn on SSO as an optimization. However, to do this we’d need to explicitly remove any guarantees about the layout of String, which really shouldn’t have been made in the first place.