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

by

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.

More Related Contents:

  1. Why can’t I store a value and a reference to that value in the same struct?
  2. The compiler suggests I add a ‘static lifetime because the parameter type may not live long enough, but I don’t think that’s what I want
  3. Is it possible to control the size of an array using the type parameter of a generic?
  4. Does println! borrow or own the variable?
  5. How do I pass disjoint slices from a vector to different threads?
  6. Why does Iterator::take_while take ownership of the iterator?
  7. When should I implement std::convert::From vs std::convert::Into?
  8. Why is it possible to implement Read on an immutable reference to File?
  9. Compare enums only by variant, not value
  10. How can I call a mutating method while holding a reference to self?
  11. How do you actually use dynamically sized types in Rust?
  12. Why do I need rebinding/shadowing when I can have mutable variable binding?
  13. “parameter `’a` is never used” error when ‘a is used in type parameter bound
  14. Borrowing references to attributes in a struct
  15. How do I ‘pass down’ feature flags to subdependencies in Cargo?
  16. Using generic trait methods like .into() when type inference is impossible
  17. Why does an enum require extra memory size?
  18. What is a crate attribute and where do I add it?
  19. Parameter type may not live long enough?
  20. How to model complex recursive data structures (graphs)?
  21. Why can’t I reuse a &mut reference after passing it to a function that accepts a generic type?
  22. How can I define an async method in a trait?
  23. How do I specify the linker path in Rust?
  24. How can I override a constant via a compiler option?
  25. Creating a vector of zeros for a specific size
  26. What is the difference between immutable and const variables in Rust?
  27. Why does the Rust compiler request I constrain a generic type parameter’s lifetime (error E0309)?
  28. Cannot pass self as callback parameter due to double borrowing
  29. How do I create a HashMap with type erased keys?
  30. Can Rust optimise away the bit-wise copy during move of an object someday?

Leave a Comment