<p><em>Short string optimization</em> is the optimization that sufficiently short strings have their data stored inline rather than an external buffer, so the string type ends up being a union. <a href="https://langdev.stackexchange.com/a/1506/15">Swift does this</a>, since its string type is a union anyways, and I've heard that most implementations of C++ <code>std::basic_string</code> do this as well.</p>
<p>However, I haven't seen this optimization applied to a dynamic array type, such as Swift <code>Array</code> or C++ <code>std::vector</code>. In C++, it would be fairly straightforward to only implement this for small types, IIUC:</p>
<pre class="lang-cpp prettyprint-override"><code>/// Maximum element size to consider for SSO.
constexpr size_t _SSO_SIZE_LIMIT = 4;

template&lt;class T, class Allocator, ::std::enable_if_t&lt;(sizeof (T) &lt;= _SSO_SIZE_LIMIT), bool&gt; = true&gt;
class _vec_storage {
  // ...version with SSO...
};

template&lt;class T, class Allocator, ::std::enable_if_t&lt;(sizeof (T) &gt; _SSO_SIZE_LIMIT), bool&gt; = false&gt;
class _vec_storage {
  // ...version without SSO...
};

template&lt;class T, class Allocator = ::std::allocator&lt;T&gt; &gt;
class vector {
private:
  _vec_storage&lt;T, Allocator&gt; m_storage;
// ...
};
</code></pre>
<p>Why is this only done for strings and not general-purpose arrays?</p>

<implementation><standard-library><strings><arrays>
Why would Short String Optimization not apply to dynamic arrays?
<p>I suspect the difference is that strings are typically immutable, whereas dynamic arrays are mutable. Even if a list is short enough to apply this optimisation, it might soon get long enough that it needs an allocation anyway; in that case the &quot;optimisation&quot; would really be a small performance cost of changing the representation, and also for branching on the discriminant whenever the list is accessed.</p>
<p>In contrast, if an immutable string is shorter than the threshold then it will stay that short and never need an allocation; and if the language already has multiple representations for different string data structures, then you're already branching on some discriminant, so adding one more variant doesn't necessarily increase that cost.</p>
<p>That said, there are many programs for which most of the mutable lists will be short and will stay short, but for the vast proportion of those programs, the relevant length is zero. So you can get most of the value of the optimisation by just not allocating for empty lists; Rust's <code>Vec</code> is like this, where a newly-created empty vector has a capacity of 0, and no allocated buffer.</p>
<p>This means that it's only a relatively small minority of programs which would get a significant benefit from &quot;SSO&quot; optimisation for dynamic arrays beyond the easier optimisation for length 0; and other programs would pay a performance penalty due to the branching. Therefore this optimisation isn't universally applicable, and it's better to leave it to third-party libraries to provide a data structure that is optimised for some use-cases but not others.</p>

CC BY-SA 4.0
2023-07-03T13:32:16.190Z
2023-07-03T13:46:40.347Z
2023-07-03T13:46:40.347Z
kaya3
CC BY-SA 4.0
2023-07-03T13:42:14.043Z
_"it's better to leave it to third-party libraries to provide a data structure that is optimised for some use-cases but not others"_ => Or to work to provide more abstract stores for containers to use, so that users can pick when to apply the optimization, see https://github.com/rust-lang/rfcs/pull/3446 ;)
Matthieu M.
CC BY-SA 4.0
2023-07-03T22:16:31.063Z
FYI, Scala has 4 special-case implementations for sets of 1–4 elements and the same for maps. But all of those are immutable. The standard tree-based implementation of an immutable persistent dynamic array is similar in that shorter arrays have a smaller tree depth (down to 0 for arrays smaller than the branching factor).
Jörg W Mittag
CC BY-SA 4.0
2023-07-03T22:20:20.860Z
@JörgWMittag Indeed, Java likewise has some implementations of `List<T>`, `Set<T>` and so on that are optimised for small immutable collections. But this doesn't "cost extra" when those are interfaces whose methods are always dynamically dispatched anyway.
kaya3
<p>Because the number of elements that could be stored in a small vector optimisation is rarely worth it, and the small vector optimisation is not free.</p>
<p>Strings are allocated from single bytes which makes it the best case situation for the optimisation - a reasonably long string can be stored easily within the space needed for the management of longer strings. In contrast, a vector usually stores larger objects - at minimum about 4 bytes on most systems, and often significantly more than that. After necessary overhead and alignment requirements, that means you're looking at most a length 5 vector being optimisable. In many cases, you'll not even manage that.</p>
<p>But, in order to access these extremely modest benefits, the library needs to check on almost every function affecting the vector whether the vector is in small vector optimisation mode or not.</p>

CC BY-SA 4.0
2023-07-04T14:57:38.433Z
2023-07-04T14:57:38.433Z
Jack Aidley
CC BY-SA 4.0
2023-07-04T15:49:53.113Z
Good point, and welcome to the site!
kaya3
# Why would Short String Optimization not apply to dynamic arrays?
Posted by: username_0 on 2023-07-03
Short string optimization is the optimization that sufficiently short strings have their data stored inline rather than an external buffer, so the string type ends up being a union. Swift does this, since its string type is a union anyways, and I've heard that most implementations of C++ std::basic_string do this as well.
However, I haven't seen this optimization applied to a dynamic array type, such as Swift Array or C++ std::vector. In C++, it would be fairly straightforward to only implement this for small types, IIUC:
/// Maximum element size to consider for SSO.
constexpr size_t _SSO_SIZE_LIMIT = 4;

template = true>
class _vec_storage {
  // ...version with SSO...
};

template _SSO_SIZE_LIMIT), bool> = false>
class _vec_storage {
  // ...version without SSO...
};

template >
class vector {
private:
  _vec_storage m_storage;
// ...
};

Why is this only done for strings and not general-purpose arrays?
**Tags:** implementation standard-library strings arrays
---
## 2 answers
### Answer by username_4 on 2023-07-04. Score: 7 | Accepted answer
Because the number of elements that could be stored in a small vector optimisation is rarely worth it, and the small vector optimisation is not free.

Strings are allocated from single bytes which makes it the best case situation for the optimisation - a reasonably long string can be stored easily within the space needed for the management of longer strings. In contrast, a vector usually stores larger objects - at minimum about 4 bytes on most systems, and often significantly more than that. After necessary overhead and alignment requirements, that means you're looking at most a length 5 vector being optimisable. In many cases, you'll not even manage that.

But, in order to access these extremely modest benefits, the library needs to check on almost every function affecting the vector whether the vector is in small vector optimisation mode or not.
> **Comments:**
> **username_1** (2023-07-04): Good point, and welcome to the site!  
---
### Answer by username_1 on 2023-07-03. Score: 7
I suspect the difference is that strings are typically immutable, whereas dynamic arrays are mutable. Even if a list is short enough to apply this optimisation, it might soon get long enough that it needs an allocation anyway; in that case the "optimisation" would really be a small performance cost of changing the representation, and also for branching on the discriminant whenever the list is accessed.

In contrast, if an immutable string is shorter than the threshold then it will stay that short and never need an allocation; and if the language already has multiple representations for different string data structures, then you're already branching on some discriminant, so adding one more variant doesn't necessarily increase that cost.

That said, there are many programs for which most of the mutable lists will be short and will stay short, but for the vast proportion of those programs, the relevant length is zero. So you can get most of the value of the optimisation by just not allocating for empty lists; Rust's `Vec` is like this, where a newly-created empty vector has a capacity of 0, and no allocated buffer.

This means that it's only a relatively small minority of programs which would get a significant benefit from "SSO" optimisation for dynamic arrays beyond the easier optimisation for length 0; and other programs would pay a performance penalty due to the branching. Therefore this optimisation isn't universally applicable, and it's better to leave it to third-party libraries to provide a data structure that is optimised for some use-cases but not others.
> **Comments:**
> **username_2** (2023-07-03): _"it's better to leave it to third-party libraries to provide a data structure that is optimised for some use-cases but not others"_ => Or to work to provide more abstract stores for containers to use, so that users can pick when to apply the optimization, see https://github.com/rust-lang/rfcs/pull/3446 ;)  
> **username_3** (2023-07-03): FYI, Scala has 4 special-case implementations for sets of 1–4 elements and the same for maps. But all of those are immutable. The standard tree-based implementation of an immutable persistent dynamic array is similar in that shorter arrays have a smaller tree depth (down to 0 for arrays smaller than the branching factor).  
> **username_1** (2023-07-03): @JörgWMittag Indeed, Java likewise has some implementations of `List<T>`, `Set<T>` and so on that are optimised for small immutable collections. But this doesn't "cost extra" when those are interfaces whose methods are always dynamically dispatched anyway.  
---
