What's the most efficient way to make a "small" vector?

#1

Hello everyone,
What’s the most efficient way (mostly in terms of access speed, but it can’t take up an excessive amount of memory, either) to store a small vector (less than 16 elements)? I’ve heard of smallvec, but this early in the project, I don’t want to use an external crate. Right now, I’m just representing it like this:

struct<T : Clone> NanoVec<T> {
    data : [T; 16],
    len : usize,
}

But T isn’t always Copy, so to initialize the list, I have to do something like this (it gets very inconvenient):

fn new(default : T) -> Self {
    Self {
        data : [default.clone(), default.clone(), default.clone(), default.clone(), default.clone(), default.clone(), default.clone(), default.clone(), default.clone(), default.clone(), default.clone(), default.clone(), default.clone(), default.clone(), default.clone(), default.clone()],
        len : 16,
    }
}

Is there a more convenient, faster and more memory efficient way to do this?

#2

Using an external crate, even for a “Hello World” project, is the right way in Rust.

SmallVec/ArrayVec already do it, are optimized, and safely handle tricky cases like panics during partial array initialization.

4 Likes
#3

… but it’ll hurt my ego. lmao just kidding.

But seriously, I actually want to try implementing it on my own (get more experienced in Rust and just for fun). Any starter ideas (that’s what I’m asking for - my current approach, using a fixed size array, is really awkward (especially for non copy types), and probably not the most memory of time efficient)? But yeah, Cargo makes using external crates very painless in Rust, so I see why it’s good practice to not reinvent the wheel.

#4

For educational purposes you can study arrayvec. It uses smaller types for small length. Also check how it uses uninitialised memory – it needs special care in case of panics.

You’ll also find lots of hacks in C (that can be adapted to Rust) if you search for Small String Optimization.

#5

Thanks!

#6

I found simply making a regular vector and then doing .reserve(N) directly after the definition outperformed SmallVec by a significant margin. Maybe I was doing something wrong but I benchmarked it extensively.

Like this:

let mut y_segs: Vec<u64> = Vec::new();
y_segs.reserve(100);

2 Likes
#7

If you know your desired size up front, you can also create Vec::with_capacity(100).