Is it possible to have stack allocated arrays with the size determined at runtime in Rust?

Question

Is there an equivalent of alloca to create variable length arrays in Rust?

I'm looking for the equivalent of the following C99 code:

void go(int n) {
    int array[n];
    // ...
}

Answer 1

It is not possible directly, as in there is not direct syntax in the language supporting it.

That being said, this particular feature of C99 is debatable, it has certain advantages (cache locality & bypassing malloc) but it also has disadvantages (easy to blow-up the stack, stumps a number of optimizations, may turn static offsets into dynamic offsets, ...).

For now, I would advise you to use Vec instead. If you have performance issues, then you may look into the so-called "Small Vector Optimization". I have regularly seen the following pattern in C code where performance is required:

SomeType array[64] = {};
SomeType* pointer, *dynamic_pointer;
if (n <= 64) {
    pointer = array;
} else {
    pointer = dynamic_pointer = malloc(sizeof(SomeType) * n);
}

// ...

if (dynamic_pointer) { free(dynamic_pointer); }

Now, this is something that Rust supports easily (and better, in a way):

enum InlineVector<T, const N: usize> {
    Inline(usize, [T; N]),
    Dynamic(Vec<T>),
}

You can see an example simplistic implementation below.

What matters, however, is that you now have a type which:

• uses the stack when less than N elements are required
• moves off to the heap otherwise, to avoid blowing up the stack

Of course, it also always reserves enough space for N elements on the stack even if you only use 2; however in exchange there is no call to alloca so you avoid the issue of having dynamic offsets to your variants.

And contrary to C, you still benefit from lifetime tracking so that you cannot accidentally return a reference to your stack-allocated array outside the function.

Note: prior to Rust 1.51, you wouldn't be able to customize by N.

---

I will show off the most "obvious" methods:

enum SmallVector<T, const N: usize> {
    Inline(usize, [T; N]),
    Dynamic(Vec<T>),
}

impl<T: Copy + Clone, const N: usize> SmallVector<T, N> {
    fn new(v: T, n: usize) -> Self {
        if n <= N {
            Self::Inline(n, [v; N])
        } else {
            Self::Dynamic(vec![v; n])
        }
    }
}

impl<T, const N: usize> SmallVector<T, N> {
    fn as_slice(&self) -> &[T] {
        match self {
            Self::Inline(n, array) => &array[0..*n],
            Self::Dynamic(vec) => vec,
        }
    }

    fn as_mut_slice(&mut self) -> &mut [T] {
        match self {
            Self::Inline(n, array) => &mut array[0..*n],
            Self::Dynamic(vec) => vec,
        }
    }
}

use std::ops::{Deref, DerefMut};

impl<T, const N: usize> Deref for SmallVector<T, N> {
    type Target = [T];

    fn deref(&self) -> &Self::Target {
        self.as_slice()
    }
}

impl<T, const N: usize> DerefMut for SmallVector<T, N> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        self.as_mut_slice()
    }
}

Usage:

fn main() {
    let mut v = SmallVector::new(1u32, 4);
    v[2] = 3;
    println!("{}: {}", v.len(), v[2])
}

Which prints 4: 3 as expected.

Answer 2

No.

Doing that in Rust would entail the ability to store Dynamically Sized Types (DSTs) like [i32] on the stack, which the language doesn't support.

A deeper reason is that LLVM, to my knowledge, doesn't really support this. I'm given to believe that you can do it, but it significantly interferes with optimisations. As such, I'm not aware of any near-terms plans to allow this.