Short String optimization

[rpjohnst]

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.

[TechnoMancer]

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

[gnzlbg]

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

[cuviper]

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.

[drXor]

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…

[mbrubeck]

anything that semantically gives out addresses into a String would trigger an allocation

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.

[drXor]

I did say it was a bad hack.

[FenrirWolf]

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.

[madmalik]

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 Just because C++ does it it does not mean its a win for us too.

[pepp]

Just because C++ does it it does not mean its a win for us too.

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.

[drXor]

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.

[scottmcm]

which really shouldn’t have been made in the first place.

I’m not sure that’s true. I also wouldn’t want to be in a situation where people are writing their own strings around Vec<u8> because they can’t trust that the standard one is no-fail in the places they care about.

[withoutboats]

My recollection was that we decided would never do this because we wanted String and Vec to avoid complex optimizations that make their semantics more difficult to understand (preferring to keep them “canonical implementations”). Apparently this decision never translated into documentation guarantees.

[drXor]

because they can’t trust that the standard one is no-fail in the places they care about.

Can you elaborate? I imagine an SSO String would have an explicit way to turn a &str or whatever into something on the heap. If they really, really care, a user could do this:

struct HeapString(String);
impl HeapString {
  fn new(str: &str) -> Self {
    let string = String::in_heap(str);
    Self(string)
  }
  fn into_inner(self) -> String { .. }
  unsafe fn new_unchecked(str: String) -> Self { .. }
}
impl Deref for HeapString {
  type Target = String; // or str or whatever
  // ..
}

I imagine that in most branches involving is_heap would predict true anyway…

My recollection was that we decided would never do this because we wanted String and Vec to avoid complex optimizations that make their semantics more difficult to understand (preferring to keep them “canonical implementations”). Apparently this decision never translated into documentation guarantees.

Sure, I can imagine wanting that. I think Rust tends to treat String a lot more like e.g. Java StringBuffer than std::string anyways. I wonder if it’s possible to measure whether this would even be a notable improvement…

[notriddle]

HeapString

Then all of the String functions would have to check whether the String is heap-allocated or inlined, despite the HeapString guaranteeing that the branch only goes one way. It’s an anti-pattern called an abstraction inversion.

[pepp]

I think it might actually be valuable to be able to turn on SSO as an optimization.

You can turn this optimization on a case-by-case basis by using SmallString which is based on SmallVec. I would argue that it is better than turning SSO for everything. In many cases SSO is pessimisation. It is in many ways similar to choosing between HashMap and BTreeMap.

The only argument that has any solid ground here is that someone measures that SSO will improve performance of majority of existing rust code.

[pepp]

we’d need to explicitly remove any guarantees about the layout of String , which really shouldn’t have been made in the first place.

Probably three years too late. I joined the discussion then myself arguing that it is safer and more future-proof to not define String as a wrapper around Vec and leave it as an implementation detail.

[newpavlov]

I think that without custom move constructors it will be a performance regression, not only because of the additional branching, but also because String moves will copy the whole struct, including often unused [u8; N]. Plus I don’t think that SSO will result in a cache friendlier code for most of Rust codebases, because thanks to borrow checker it’s idiomatic in Rust to pass around &str instead of pervasively cloning substrings as you’ll do in C++.

[drXor]

Then all of the String functions would have to check whether the String is heap-allocated or inlined, despite the HeapString guaranteeing that the branch only goes one way.

Yeah, there’s no particularly good way to optimize those calls in today’s compiler. I mumbled something about how is_heap should be annotated to predict true (Does Rust even have a way to do this? Clang has some kind of non-standard attr I think.) or whatever, but I have nothing concrete to say as to the performance hit.

The only argument that has any solid ground here is that someone measures that SSO will improve performance of majority of existing rust code.

Yeah, that’s what I’ve been saying. Absent that, I don’t think making std::string::String an SSO string is worth it.

I’m glad to see the discussion this has generated. I think the issue is cleared up for me!

[matklad]

Does Rust even have a way to do this?

Yep, as an unstable intrinsic: https://github.com/rust-lang/rust/blob/ae366637fedf6f34185e54fc7b2d725b1a458ff6/src/libcore/intrinsics.rs#L660