`String::as_mut_vec` prevents small string optimization

[petrochenkov]

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}

[ranma42]

I do not see String::as_mut_vec as preventing SSO, instead I think it simply makes it natural to apply SSO to the underlying data structure (i.e. Vec). This would make it possible to keep String::as_mut_vec and to get the advantages of SSO (trading an additional comparison to gain more cache locality, to avoid allocating and dereferencing) on all Vec-based data structures.

[petrochenkov]

instead I think it simply makes it natural to apply SSO to the underlying data structure (i.e. Vec)

While this approach is possible, unlike SSO for strings it's not adopted by popular implementations of generic vector - folly::fbvector, boost::vector and not allowed by std::vector. There must be reasons, probably of statistical nature (I can start speculating on them but would prefer not to).

[ranma42]

The main reference I can provide for something like this on vectors is LLVM, but in that case the number of elements is parametrised (the user is free to choose it and the compiler is able to optimise it... AFAICT this would not be possible in rust).
An interesting analysis of the results of using SSO to optimise JavaScript strings is available here. It might provide a starting point for choosing what sizes can be most effective.

I believe you're right about the reason why SSO is more common than similar optimisations on other data structures. Also, the absence of a variable-sized type parameter might contribute in making it easier to find a reasonable default "local cache size" for strings.
It might also make sense to keep this optimisation in mind when implementing ropes #7628

[huonw]

In the worst case, this can still be provided by upgrading an SSO to a Vec although it's a little sad to make as_... possibly expensive.

[thestinger]

@petrochenkov: It wouldn't make sense to provide a small string type without providing a small vector type since it needs to be written anyway. The small string / vector optimization increases the code size and adds extra branches / operations. Rust is always going to provide this string type based on Vec even if the small string optimization is implemented because there's a trade-off.

It's important to note that std::string in C++ is an array of arbitrary bytes - there's no equivalent to Rust's string types. The only real difference between it and std::vector<char> is that it needs to maintain an internal NUL byte at the end for the data and c_str methods. Rust's string types are wrappers around byte slices / vectors enforcing UTF-8 encoding.

[thestinger]

The libc++ std::string is 24 bytes on x86_64 just like the obvious implementation with a length, capacity and data pointer. It only uses the small string optimization for strings up to 23 bytes in length (including the trailing NUL). For small vectors, more flexibility is needed (integer type parameter) because some types are many bytes in length and the usage patterns vary more. Ideally, a small string would also expose that integer type parameter and pass it along to the underlying small vector.

[petrochenkov]

Rust is always going to provide this string type based on Vec even if the small string optimization is implemented

If you are really going to do that, then as_mut_vec is not an issue, it's just the decision to make Vec "small optimized" is much more serious than making as_mut_vec experimental or replacing it with something.

... vectors is LLVM, but in that case the number of elements is parametrised

---

For small vectors, more flexibility is needed (integer type parameter)

This is what I would expect from "small optimized" vector too.
Then as_mut_vec will have to return something like &mut Vec<u8, MAGIC_BUFFER_SIZE> to work correcly, assuming the small buffer size is not kept at runtime. Edit: Interesting, LLVM SmallVector does seem to keep the capacity of small vectors in runtime.

[pepp-cz]

Some hard data: as_mut_vec is not used anywhere in Rust and it is used four times in Rust outside of the String implementation itself.

I suggest to make as_mut_vec private. You know: better safe than sorry.

[thestinger]

If there was a small string there would be an underlying small vector type to go along with it. Either way, there is going to be a string type to go along with Vec<T> so there is no problem here.

[LukasKalbertodt]

I don't understand why the string type needs to have a vector type as underlying buffer. Strings and Vecs are pretty similar in how they work but completely different in what they are used for. Hence we need to treat String as another type with it's own challenges IMO.
We discussed the issue here: http://discuss.rust-lang.org/t/small-string-optimization-remove-as-mut-vec/1320

[thestinger]

The design of strings is that they're a thin wrapper around the corresponding slice/vector type. A small string type would be a wrapper around a small vector type. It's a design trade-off so there would be a choice between the types as there always is. Unless someone can explain why an asymmetric string / vector design makes any sense... ?

[thestinger]

@LukasKalbertodt: Strings in Rust are slice/vector wrappers providing a UTF-8 encoding guarantee. There is always going to be a string type implemented as a wrapper around Vec<u8>. In the future, Rust can have a string type with small string optimization but writing that implies writing a small vector type and it wouldn't make sense to provide one without the other.

The preferred default string type is a separate issue from whether a string wrapper around vectors exists. Note that there is zero language support for either Vec<u8> or String, they are entirely unprivileged library types beyond the fact that a default prelude exists.

[pepp-cz]

I cannot say if it makes any sense but I do not any sense if it is other way round. Firstly Sting is a sequence of "characters" in UTF-8 endcoding so I do see any direct similarity to Vec.

I do not want to argue about implementation of String using Vec or whatsoever. The issue is just about future-proofing the design. At some time it can happen that it is better to have independent String and Vec but this little as_mut_vec methods just makes it harder (e.g. maybe SSO can be done better in strings that on generic vector). And the sad thing about it is that nobody cares about that method.

[thestinger]

It would also make sense to have a string implemented as a rope type, and implementing that is going to result in an underlying general purpose rope-based vector type. It's just the logical way to do things... there's no good reason to make the implementation unusable for other purposes than storing UTF-8.