When is it "morally" correct to use smallvec?

Everyone seems to love smallvec, but I haven't yet had the chance to use it in a project. Keeping things off the heap generally seems like a good idea, so I'd like to try it.

Here's the thing: when is it "morally" right to use smallvec? I don't mean "technically". I know what it's for and how to use it. But when would its use be considered a premature optimization? If a datatype I only use once, saying during program initialization, contains a Vec, would there really be a point in making that a SmallVec? etc.

Please and thanks.

1 Like

If you add too much to any stack frame, you risk getting a StackOverflowError. I'd stay away from that potential with a mile-long pole. If you need to store a small, countable and well-bounded set wherein each item T also holds a reasonably small memory size, then go with a smallvec. The magic number depends on the std::mem::size_of::<T>(). If I have to store a nondeterministic 20-25 u64's on the stack because I only need the items alive while in the same (or inner) closure, SmallVec is a good choice. If I need to return a set of items from the closure, I'd go with a heap-allocated Vec.

Generally: If you know the range of the number of items you need to store, but not necessarily the exact length, then so long as the upper bound on that range is rather small, go with SmallVec

Alternatively, if you have an upper and lower bound, and the difference between the two is small, you can just create a slice on the stack and keep a seperate length variable.

2 Likes

If smallvec is a performance optimization then the "morally" right time to use it is when you've done real-world benchmarking on your application which identifies a bottleneck that smallvec alleviates.

It's good benchmarking that's the key.

10 Likes

Use of smallvec will be "morally" justified when you have measured/profiled the performance of whatever you are trying to do and discovered that your use of normal vectors is some kind of bottleneck.

Last year I took part in a challenge to calculate the first Fibonacci number with a million digits in the language of you choice. The limitation not being allowed to use any libraries that were not a standard part the the language system. My C++ solution ended up using a handmade big number engine that was optimized the same way as smallvec. A definite win in performance as my recursive divide and conquer big number multiplications always bottomed out dealing with thousands of small numbers.

1 Like

First, some reasons not to use SmallVec:

  • When it spills onto the heap, it’s just a worse Vec.
  • It wastes more space when empty.
  • It takes up inline space in structs/containers, which can decrease cache locality of the fields outside of the vector.
  • Moving a SmallVec by value may be much more expensive than moving a Vec, and LLVM does not always ellide moves perfectly. This means you occasionaly need to re-architect some code in order to use SmallVec efficiently.
  • It uses unsafe code. While we do a lot to audit and test it, soundness bugs have slipped through a few times.

Reasons that SmallVec might be a big win:

  • You know that your vector will hold a very small number of items most of the time, and only rarely need to hold more. (SmallVec may speed up the common case a lot, while slightly slowing down the uncommon case.)
  • Your vector is local to the stack of a function that is called frequently. (SmallVec will usually be allocated on the stack, saving the need for frequent heap allocations and deallocations.)
  • You want cache locality between the items in your vector and other data stored alongside it. (SmallVec eliminates a pointer indirection between the vector and its container.)

I'd probably want at least two of these reasons to be true, or some other strong evidence of a performance win, before I would reach for SmallVec. (Disclosure: I’m one of the maintainers of the smallvec crate.)

19 Likes

It's worth noting that if you're 100% confident on the upper bound, the arrayvec crate has a hard upper limit and would avoid most of the drawbacks of smallvec.

5 Likes

Thanks everyone, this clears up the issue substantially. For now I'll avoid using smallvec, as I don't see how current Vec usage could possibly be a bottleneck at the moment.

1 Like

For the sake of completeness: There is also tinyvec, which avoids using unsafe with the small caveat of the vec's item type T to implement Default.

And if you are worried that your stack might be too small, there is a way to make it bigger (taken from this reddit thread):
cargo rustc -- -C link-args=-Wl,-zstack-size=4194304

or directly in code by spawning a thread with explicit stack size:

use std::thread;

const STACK_SIZE: usize = 4 * 1024 * 1024;

fn run() {
    // Usual main code goes here
} 

fn main() {
    // Spawn thread with explicit stack size
    let child = thread::Builder::new()
        .stack_size(STACK_SIZE)
        .spawn(run)
        .unwrap();

    // Wait for thread to join
    child.join().unwrap();
}
3 Likes

One elegant use of smallvec I've encountered is in a terminal application. It has a grid of character cells in which every cell holds a grapheme. With unicode combiners and modifiers and such, this can become quite large (it's hard to put a strict upper bound). However, in practice, by far most cells will contain 'simple' characters like ASCII or at least single codepoints. Using smallvec avoids (in the expected use case) the overhead of a zillion heap allocations and deallocations, as well as a level of indirection when accessing the contents.

4 Likes

One thing that hasn't been mentioned (maybe because it's too obvious :joy:): Generally I would bias towards using built-in Rust data structures unless you have a pretty good reason not to. I'll offer two reasons for this heuristic:

  1. The use of any third-party crate can tend to increase build times and executable sizes.
  2. Depending on how production-ready you want your software to be, you may also want to consider maintenance, security surface area, licenses, and crate stability. That said, I actually think smallvec would do really well on these criteria because it's post-1.0 and maintained by the servo org.
2 Likes