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];
    // ...
}

you could always import the alloca function from c. if you add some kind of overflow checking you might even get it to be safe. — oli_obk
@ker: That's unlikely. alloca isn't really a function, it's more a compiler intrinsic. At least with LLVM, it's an actual IR instructions, so there's no direct way of "importing" it. You'd need to be able to write inline IR, which you currently can't. — DK.
that makes me wonder what those guys imported: github.com/tomaka/cpal/blob/master/alsa-sys/src/lib.rs#L2135 ... i was pretty sure it's a c standard function nowadays (man7.org/linux/man-pages/man3/alloca.3.html) — oli_obk
In general, due to how most calling conventions work, it would be impossible for alloca to be a regular function. A function can only change it's own stack frame and cannot change its parent's stack frame. The Notes section in the man page states that the "function" is compiler and machine dependent. This is why. — Tyler

Matthieu M. Matthieu M. · Accepted Answer · 2015-01-11T19:25:01

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.

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

2 Answers