Implementing ArrayVec Using Const Generics

This is a little blog post I've been working on over the past couple days. If you like low-level data structures, writing correct unsafe code, or embedded programming, you may find this interesting.

The code is all real, and published on crates.io.

5 Likes

Interesting read so far! A few learner questions.

In this block:

impl<T, const N: usize> ArrayVec<T, { N }> {
    ...

    pub const fn len(&self) -> usize { self.length }

    pub const fn is_empty(&self) -> bool { self.len() == 0 }

    pub const fn capacity(&self) -> usize { N }

    pub const fn remaining_capacity(&self) -> usize {
        self.capacity() - self.len()
    }

    pub const fn is_full(&self) -> bool { self.len() == self.capacity() }
}

This line stands out:

impl<T, const N: usize> ArrayVec<T, { N }>

first, what does the brackets wrapped around N mean? (i.e., { N }).

Also, why is this declared a constant function when the len can change throughout runtime? I definitely feel like I'm missing some basic concept/definition here

    pub const fn remaining_capacity(&self) -> usize {
        self.capacity() - self.len()
    }

That is just the syntax for const generics

const means compile time, not constant

Are there limits to what can exist within the ... closure..?

And why is it useful?

closure? If you're talking about const fn, right now there you can't branch, loop, or do anything intrinsically unsafe. You can call unsafe const functions, but they can't do anything intrinsically unsafe (like dereferencing a raw pointer). There are a few other things, but this is the most of it. This is mainly due to prevent stabilizing bugs. Right now the compiler is capable of running most things, but only with a very unstable flag, (I don't remember the name, but it was something along the lines of -Zrelease-the-miri-within, or something like that)

This is useful, because it allows you to compute values at compile time and put them into static. For example, in the future I could have a Mutex<Vec<i32>> without lazy-static or similar.

2 Likes

Making something a const fn is a way to let the compiler run code at compile time (see Compile Time Function Execution). The primary use for CTFE is when initializing const or static variables, for example imagine being able to pre-calculate an expensive lookup table or whatever. Declaring the remaining_capacity() method as a const fn would allow consumers of remaining_capacity() to use it in their own const fn functions.

One use might be to initialize a cache with known "hot" values at compile time, while still leaving enough remaining capacity to avoid cache evictions early on? That's probably a bit contrived but I have no idea what people might want to use ArrayVec for, so I tried to make as many things const fn as possible to not impose any unnecessary limitations.

4 Likes

Happy anniversary @Michael-F-Bryan! =D And thanks for providing a good understanding of the subject