5
$\begingroup$

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<class T, class Allocator, ::std::enable_if_t<(sizeof (T) <= _SSO_SIZE_LIMIT), bool> = true>
class _vec_storage {
  // ...version with SSO...
};

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

template<class T, class Allocator = ::std::allocator<T> >
class vector {
private:
  _vec_storage<T, Allocator> m_storage;
// ...
};

Why is this only done for strings and not general-purpose arrays?

$\endgroup$

2 Answers 2

7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Good point, and welcome to the site! $\endgroup$
    – kaya3
    Jul 4, 2023 at 15:49
7
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ "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 github.com/rust-lang/rfcs/pull/3446 ;) $\endgroup$ Jul 3, 2023 at 13:42
  • $\begingroup$ 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). $\endgroup$ Jul 3, 2023 at 22:16
  • $\begingroup$ @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. $\endgroup$
    – kaya3
    Jul 3, 2023 at 22:20

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .