Is there a plan to have a small string and small vector optimisations, similar to fbvector and fbstring which offer significant performance improvements.
I've noted in my own production code in c++ projects that a lot of times the use case is a growable vector but the number of items ends up being within some reasonable bounds. In those cases having the flexibility to declare a vector to be stack allocated up to N : u32 elements but switch to heap when the logic demands transparently would be a performance win.
The std::string has small string optimisation but it's too small at 16bytes fixed; the optimum size depends on the benchmarking for your use case, so a level of user control is needed. And std::vector missed a trick on this front so fbvector is used more.
I've seen one or two crates with this functionality but somewhat restricted due to other constraints. It would be great to see it in the std library behind the scenes, though perhaps with const fn it will be more doable.
1 Like
On this topic recently I've seen:
1 Like
Yes, that's a little better, still nothing in the vector area though 
1 Like
We aren't going to use the small vector optimization in Vec - @Gankra would know the most about the background there.
1 Like
@sfackler: Do you by any chance have a link to a discussion or article on this? It would be good to get a view on it, and what alternatives there are
Thanks
I remember this question being asked in the past and the resolution was that types in the standard library (i.e. Vec and String) wouldn't get small size optimisation, instead people are encouraged to use a specialised crate. I think the reasoning was that it adds a lot of implicit magical behaviour and people should have to knowingly opt into something like SSO.
You may want to check out the smallvec crate which was originally created by the servo team. It allows you to specify the type of the backing array, meaning you can tweak the size according to your use case. Unfortunately smallvec::Array is only implemented on a finite number of sizes due to current limitations in the type system, but const generics are in the pipeline so that shouldn't be an issue for long.
It won't happen in the stdlib, but you can use external packages which do these kinds of things.
For background: Small string optimization: remove as_mut_vec - libs - Rust Internals
as for the "small vector" optimisation, using stack-memory. I had a similar requirement, avoiding expensive heap-allocation for dynamic small-list; in my case the length of the lists shall be related to depth of function calls.
Finally I implemented the crate Seq realizing a linked list, located in stack memory.
Sequences can grow within stack-frames of function calls dynamically; sequences can be rolled-out in stack memory.
Just, the performance is bad compared to containers using consecutive memory (see benchmarks at https://github.com/frehberg/seq-rs) such as Vec or array. The frequent allocation of stack-memory for each Seq element has high costs.
Servo recently added another crate with a "small vector" optimization, specifically for bit vectors: smallbitvec.
This crate not only avoids heap allocations for small collections; it also minimizes stack size. The SmallBitVec struct has only one field, a single usize. Depending on the number of items in the collection, this field is treated either as an inline bit vector (with two bits reserved as flags), or a pointer to a heap-allocated bit vector.
4 Likes