# Short String optimization

**URL:** <https://internals.rust-lang.org/t/short-string-optimization/8436>\
**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:** 11\
**Page:** 2

<div class="post-metadata">

**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 24, 2018, 8:46pm UTC](https://internals.rust-lang.org/t/short-string-optimization/8436/22 "2018-09-24T20:46:08Z")

</div>

> [@mcy](#):
>
> 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.

---

<div class="post-metadata">

**Author:** ![withoutboats](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/withoutboats/32/4560_2.png) [@withoutboats](https://internals.rust-lang.org/u/withoutboats)\
**Post date:** [September 24, 2018, 9:02pm UTC](https://internals.rust-lang.org/t/short-string-optimization/8436/23 "2018-09-24T21:02:31Z")

</div>

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.

---

<div class="post-metadata">

**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, 9:30pm UTC](https://internals.rust-lang.org/t/short-string-optimization/8436/24 "2018-09-24T21:30:16Z")

</div>

> [@scottmcm](#):
>
> 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:

```rust
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...

> [@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.

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...

---

<div class="post-metadata">

**Author:** ![notriddle](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/notriddle/32/14082_2.png) [@notriddle](https://internals.rust-lang.org/u/notriddle)\
**Post date:** [September 25, 2018, 12:51am UTC](https://internals.rust-lang.org/t/short-string-optimization/8436/25 "2018-09-25T00:51:51Z")

</div>

> [@mcy](#):
>
> 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](https://en.wikipedia.org/wiki/Abstraction_inversion).

---

<div class="post-metadata">

**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 25, 2018, 8:29am UTC](https://internals.rust-lang.org/t/short-string-optimization/8436/26 "2018-09-25T08:29:30Z")

</div>

> [@mcy](#):
>
> 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.

---

<div class="post-metadata">

**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 25, 2018, 8:33am UTC](https://internals.rust-lang.org/t/short-string-optimization/8436/27 "2018-09-25T08:33:03Z")

</div>

> [@mcy](#):
>
> 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.

---

<div class="post-metadata">

**Author:** ![newpavlov](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/newpavlov/32/3290_2.png) [@newpavlov](https://internals.rust-lang.org/u/newpavlov)\
**Post date:** [September 25, 2018, 9:02am UTC](https://internals.rust-lang.org/t/short-string-optimization/8436/28 "2018-09-25T09:02:20Z")

</div>

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++.

---

<div class="post-metadata">

**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 25, 2018, 2:43pm UTC](https://internals.rust-lang.org/t/short-string-optimization/8436/29 "2018-09-25T14:43:18Z")

</div>

> [@notriddle](#):
>
> 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.

> [@pepp](#):
>
> 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!

---

<div class="post-metadata">

**Author:** ![matklad](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/matklad/32/12266_2.png) [@matklad](https://internals.rust-lang.org/u/matklad)\
**Post date:** [September 25, 2018, 4:01pm UTC](https://internals.rust-lang.org/t/short-string-optimization/8436/30 "2018-09-25T16:01:49Z")

</div>

> [@mcy](#):
>
> Does Rust even have a way to do this?

Yep, as an unstable intrinsic: [rust/src/libcore/intrinsics.rs at ae366637fedf6f34185e54fc7b2d725b1a458ff6 · rust-lang/rust · GitHub](https://github.com/rust-lang/rust/blob/ae366637fedf6f34185e54fc7b2d725b1a458ff6/src/libcore/intrinsics.rs#L660)

---

<div class="post-metadata">

**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:** [October 1, 2018, 9:37am UTC](https://internals.rust-lang.org/t/short-string-optimization/8436/31 "2018-10-01T09:37:49Z")

</div>

@newpavlov`String`'s size w/o the SSO can be the same, such that in both cases, when the whole struct is moved via a memcpy, the same amount of work is done, e.g.,

```rust
union String {
    (usize, usize, *mut u8), // (ptr, size, capacity)
    ([u8; size_of::<usize>() * 3), [sso buffer..., sso size, sso bit]
}

```

where one:

- uses 1bit to signal whether the SSO is active (e.g. the highest pointer bit),
- some bits to store the size (either the second highest pointer byte, or one crawls this in the highest pointer byte along with the SSO bit),
- the rest of the bits for the SSO buffer.

On 64-bit targets, if you use 1 byte for the SSO signaling bit, and 1 byte for the size, you get 22byte wide buffer. If you store the size and the sso signaling bit in the same byte, then you get 23 byte wide buffer, but you need to mask the signaling bit every time you want to extract the size.

With move constructors, moving the `String` _could_ be less work when SSO is active (branch to detect SSO, branch on the SSB length, plus only moving the relevant part of the small string buffer) than when the buffer is heap allocated, but without move constructors moving the `String` when SSO is active is never more work than when the string is heap allocated unless one makes it larger than 3 pointers to get a larger small buffer size (AFAIK most C++ string implementations don’t do this).

Whether all the logic for deciding what to move and how to do so is more performant than just memcpying 3 pointers… is unlikely. This only becomes relevant if you use small strings with larger buffers, but the “beauty” of C++ SSO is that one can perform it without increasing the actual size of the `std::string` object.

---

<div class="post-metadata">

**Author:** ![system](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/system/32/14092_2.png) [@system](https://internals.rust-lang.org/u/system)\
**Post date:** [March 25, 2019, 8:30am UTC](https://internals.rust-lang.org/t/short-string-optimization/8436/32 "2019-03-25T08:30:54Z")

</div>

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.

[Previous page](https://internals.rust-lang.org/t/short-string-optimization/8436.md?page=1)