# Short String optimization **URL:** \ **Category:** Uncategorized\ **Created:** [September 20, 2018, 3:55pm UTC](https://internals.rust-lang.org/t/short-string-optimization/8436 "2018-09-20T15:55:36Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![mcy](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/mcy/32/6512_2.png) [@mcy](https://internals.rust-lang.org/u/mcy)\ **Post date:** [September 20, 2018, 3:55pm UTC](https://internals.rust-lang.org/t/short-string-optimization/8436/1 "2018-09-20T15:55:36Z")
Has there been any discussion of having `String` live entirely on the stack for `len < size_of::() * n`? Imagine ```rust enum StringInner { Stack { len: u8, bytes: [u8; N], }, Heap(Vec), } ``` 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. ---
**Author:** ![sfackler](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/sfackler/32/9_2.png) [@sfackler](https://internals.rust-lang.org/u/sfackler)\ **Post date:** [September 20, 2018, 4:12pm UTC](https://internals.rust-lang.org/t/short-string-optimization/8436/3 "2018-09-20T16:12:50Z")
We guarantee that we will never perform this optimization for Vec: [https://doc.rust-lang.org/std/vec/struct.Vec.html#guarantees](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. ---
**Author:** ![cuviper](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/cuviper/32/1897_2.png) [@cuviper](https://internals.rust-lang.org/u/cuviper)\ **Post date:** [September 20, 2018, 4:17pm UTC](https://internals.rust-lang.org/t/short-string-optimization/8436/4 "2018-09-20T16:17:59Z")
And that guarantee of indirection is necessary for [`StableDeref`](https://docs.rs/stable_deref_trait/1.1.1/stable_deref_trait/trait.StableDeref.html) to work. ---
**Author:** ![Centril](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/centril/32/3334_2.png) [@Centril](https://internals.rust-lang.org/u/Centril)\ **Post date:** [September 20, 2018, 4:37pm UTC](https://internals.rust-lang.org/t/short-string-optimization/8436/5 "2018-09-20T16:37:19Z")
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. ---
**Author:** ![leonardo](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/leonardo/32/1344_2.png) [@leonardo](https://internals.rust-lang.org/u/leonardo)\ **Post date:** [September 20, 2018, 4:41pm UTC](https://internals.rust-lang.org/t/short-string-optimization/8436/6 "2018-09-20T16:41:48Z")
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? 🙂 ---
**Author:** ![Centril](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/centril/32/3334_2.png) [@Centril](https://internals.rust-lang.org/u/Centril)\ **Post date:** [September 20, 2018, 4:48pm UTC](https://internals.rust-lang.org/t/short-string-optimization/8436/7 "2018-09-20T16:48:35Z")
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 =) ---
**Author:** ![mbrubeck](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/mbrubeck/32/174_2.png) [@mbrubeck](https://internals.rust-lang.org/u/mbrubeck)\ **Post date:** [September 20, 2018, 5:09pm UTC](https://internals.rust-lang.org/t/short-string-optimization/8436/8 "2018-09-20T17:09:43Z")
`String` docs do make a number of other promises that are hard to keep if it does not share its representation with `Vec`. For example, [`String::into_bytes`](https://doc.rust-lang.org/std/string/struct.String.html#method.into_bytes) says that it does not copy the contents. ---
**Author:** ![pepp](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/pepp/32/1847_2.png) [@pepp](https://internals.rust-lang.org/u/pepp)\ **Post date:** [September 20, 2018, 5:10pm UTC](https://internals.rust-lang.org/t/short-string-optimization/8436/9 "2018-09-20T17:10:27Z")
> [@mcy](#): > > Has there been any discussion of having `String` live entirely on the stack for `len < size_of::() * n` ? There have been some conversations in the past: > > > SSO is a popular optimization technique and is currently implemented in all the …major C++ standard libraries\*. > If Rust decides to adopt it too then it will come into contradiction with the \`String::as\_mut\_vec\` method, which exposes details of the current \`String\` implementation incompatible with SSO. > I suppose, the choice between these two has to be made before marking \`as\_mut\_vec\` as stable. > > \\*Although it's not used by default in libstdc++ due to ABI compatibility\ and > [@Small string optimization: remove as\_mut\_vec](https://internals.rust-lang.org/t/small-string-optimization-remove-as-mut-vec/1320): > > I needed to create this thread, since I haven’t found too much dicussions on that topic. SSO is an important optimization in modern languages. To give an example: More than half of all allocations in the chromium browser are std::string allocations [1]. I don’t have a study or article around to prove the statement, but: You can easily imagine that many strings in applications won’t exceed a certain length. Storing those strings without allocating in the stack-object itself would be a huge gain … ---
**Author:** ![scottmcm](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/scottmcm/32/2355_2.png) [@scottmcm](https://internals.rust-lang.org/u/scottmcm)\ **Post date:** [September 21, 2018, 12:20am UTC](https://internals.rust-lang.org/t/short-string-optimization/8436/10 "2018-09-21T00:20:13Z")
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](https://crates.io/crates/smallvec). ---
**Author:** ![rpjohnst](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/rpjohnst/32/9524_2.png) [@rpjohnst](https://internals.rust-lang.org/u/rpjohnst)\ **Post date:** [September 21, 2018, 1:56am UTC](https://internals.rust-lang.org/t/short-string-optimization/8436/11 "2018-09-21T01:56:26Z")
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. ---
**Author:** ![TechnoMancer](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/technomancer/32/4455_2.png) [@TechnoMancer](https://internals.rust-lang.org/u/TechnoMancer)\ **Post date:** [September 21, 2018, 5:44am UTC](https://internals.rust-lang.org/t/short-string-optimization/8436/12 "2018-09-21T05:44:28Z")
The `String` docs also talk about its representation and says the buffer is always allocated on the heap. ---
**Author:** ![gnzlbg](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/gnzlbg/32/3858_2.png) [@gnzlbg](https://internals.rust-lang.org/u/gnzlbg)\ **Post date:** [September 21, 2018, 8:22am UTC](https://internals.rust-lang.org/t/short-string-optimization/8436/13 "2018-09-21T08:22:05Z")
Note that since we do not technically guarantee it for `String`, `StableDeref` is playing a risky business here. ---
**Author:** ![cuviper](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/cuviper/32/1897_2.png) [@cuviper](https://internals.rust-lang.org/u/cuviper)\ **Post date:** [September 21, 2018, 5:22pm UTC](https://internals.rust-lang.org/t/short-string-optimization/8436/14 "2018-09-21T17:22:51Z")
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`. ---
**Author:** ![mcy](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/mcy/32/6512_2.png) [@mcy](https://internals.rust-lang.org/u/mcy)\ **Post date:** [September 21, 2018, 6:03pm UTC](https://internals.rust-lang.org/t/short-string-optimization/8436/15 "2018-09-21T18:03:05Z")
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` 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`… ---
**Author:** ![mbrubeck](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/mbrubeck/32/174_2.png) [@mbrubeck](https://internals.rust-lang.org/u/mbrubeck)\ **Post date:** [September 21, 2018, 6:49pm UTC](https://internals.rust-lang.org/t/short-string-optimization/8436/16 "2018-09-21T18:49:49Z")
> [@mcy](#): > > 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. ---
**Author:** ![mcy](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/mcy/32/6512_2.png) [@mcy](https://internals.rust-lang.org/u/mcy)\ **Post date:** [September 21, 2018, 6:54pm UTC](https://internals.rust-lang.org/t/short-string-optimization/8436/17 "2018-09-21T18:54:52Z")
I did say it was a bad hack. ---
**Author:** ![FenrirWolf](https://avatars.discourse-cdn.com/v4/letter/f/35a633/32.png) [@FenrirWolf](https://internals.rust-lang.org/u/FenrirWolf)\ **Post date:** [September 21, 2018, 10:18pm UTC](https://internals.rust-lang.org/t/short-string-optimization/8436/18 "2018-09-21T22:18:43Z")
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](https://doc.rust-lang.org/std/string/struct.String.html#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. ---
**Author:** ![madmalik](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/madmalik/32/4213_2.png) [@madmalik](https://internals.rust-lang.org/u/madmalik)\ **Post date:** [September 23, 2018, 6:26pm UTC](https://internals.rust-lang.org/t/short-string-optimization/8436/19 "2018-09-23T18:26:29Z")
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. ---
**Author:** ![pepp](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/pepp/32/1847_2.png) [@pepp](https://internals.rust-lang.org/u/pepp)\ **Post date:** [September 24, 2018, 11:20am UTC](https://internals.rust-lang.org/t/short-string-optimization/8436/20 "2018-09-24T11:20:25Z")
> [@madmalik](#): > > 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. ---
**Author:** ![mcy](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/mcy/32/6512_2.png) [@mcy](https://internals.rust-lang.org/u/mcy)\ **Post date:** [September 24, 2018, 4:08pm UTC](https://internals.rust-lang.org/t/short-string-optimization/8436/21 "2018-09-24T16:08:39Z")
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. [Next page](https://internals.rust-lang.org/t/short-string-optimization/8436.md?page=2)