在Rust中，是否可能在运行时确定大小并具有堆栈分配的数组？

Question

在Rust中是否有类似alloca的等效函数可以创建可变长度数组？

我正在寻找以下C99代码的等效函数：

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

- Dogbert

---

你总是可以从 C 语言中导入 alloca 函数。如果你添加一些溢出检查，甚至可以使它更安全。 - oli_obk

@ker: 这不太可能。alloca不是真正的函数，它更像是一个编译器内置函数。至少在LLVM中，它是一条实际的IR指令，所以没有直接的“导入”方式。你需要能够编写内联IR，但目前你还不能这样做。 - DK.

让我想知道那些家伙导入了什么：https://github.com/tomaka/cpal/blob/master/alsa-sys/src/lib.rs#L2135 ... 我很确定它现在是一个C标准函数（http://man7.org/linux/man-pages/man3/alloca.3.html） - oli_obk

一般来说，由于大多数调用约定的工作方式，alloca 不可能是一个常规函数。函数只能更改自己的堆栈帧，不能更改其父堆栈帧。手册页面中的注释部分指出，“函数”取决于编译器和机器。这就是为什么。 - Tyler

Answer 1

这是不可能的直接实现的，因为语言中没有直接支持它的语法。

话虽如此，C99的这个特性是有争议的，它有一定的优点（缓存局部性和绕过malloc），但也有缺点（容易引起栈溢出，阻碍一些优化，可能将静态偏移转换为动态偏移等）。

目前，我建议你使用Vec。如果你有性能问题，那么可以考虑所谓的“小向量优化”。在需要性能的C代码中，我经常看到以下模式：

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); }

现在，Rust很容易支持这个（并且在某种程度上更好）：

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

您可以看到下面的一个简单示例实现。

然而，重要的是，您现在拥有了一种类型，它：

- 在需要少于 N 个元素时使用堆栈 - 否则将移到堆上，以避免堆栈溢出

当然，它始终为 N 个元素在堆栈上预留足够的空间，即使您只使用 2 个元素；但是换取的是没有调用 alloca，因此您避免了对变量的动态偏移的问题。

与 C 不同的是，您仍然从生命周期跟踪中受益，因此您不能意外地将对堆栈分配的数组的引用返回到函数外部。

注意：在 Rust 1.51 之前，您将无法定制 N。

我将展示最“明显”的方法：

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()
    }
}

使用方法：

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

这将按预期输出4：3。

- Matthieu M.

---

@malbarbo：确实，这也涉及到没有聪明地使用类型级整数的问题！我没有考虑过要求用户提供数组类型来指定大小。 - Matthieu M.

smallvec 这个库提供了这个功能。 - wizzwizz4

@wizzwizz4 部分地说，Array 特性仅实现了部分大小的子集，并且使用起来有些繁琐。虽然不是最好的选择，但显然是缺少常量泛型的权宜之计。 - Matthieu M.

Inline 变体的切片实现不应该使用该变体的大小作为边界吗？这里的示例代码创建了一个整个长度为 64 的数组的切片。因此，该切片将具有错误的长度。 - dubiousjim

@dubiousjim：确实如此，已经修复了。另外，如果您想尝试而不必实际构建 64 Ts，则需要使用[MaybeUninit<T>; 64]，但现在我会把它留出来。最后，目前正在进行工作以便能够将内联存储传递给 rustc 的 std 结构，但那还只是原型阶段。 - Matthieu M.

论坛上的每个人都告诉我，动态大小的数组在堆栈上是不可能的，因为堆栈的大小应该在编译时就已知。一直觉得编译器如何确定堆栈大小特别是遇到if-else语句很奇怪。这篇文章让我大开眼界。 - zombiesauce

Answer 2

不行。

在 Rust 中这样做需要能够将类似 [i32] 的动态尺寸类型 (DSTs) 存储在堆栈上，而该语言不支持这种能力。

更深层次的原因是 LLVM，在我看来，它并没有真正支持此功能。我认为你可以这样做，但它会显著干扰优化。因此，我不知道有任何近期允许此操作的计划。

- DK.

---

LLVM 首要是一个 C/C++ 优化器，所以它很可能相对支持得很好。 - huon

每次我看到这个问题被提出来时，总会有人说在块内动态调整堆栈会严重影响LLVM进行优化的能力。我从未找到任何实质性的证据来支持或反驳这一点，所以我更多地是按照我听到的少量信息去做。虽然我很希望自己在这个问题上是错的：堆栈DSTs将会非常棒。 :) - DK.

Rust现在作为Rust 1.0 alpha的一部分支持DST了！http://blog.rust-lang.org/2015/01/09/Rust-1.0-alpha.html - Michael Tang

Rust已经支持DST（夏令时）有一段时间了。除非我漏掉了什么，它不支持将DST存储在变量中，也不支持从函数返回它们。 - DK.

除了效率方面，LLVM 绝对支持堆栈分配的 VLAs。您只需使用 %vla = alloca <type>, <ty> <NumElements> 而不是 %sla = alloca [<NumElements> x <type>]（以及等效的编程 AllocaInst 调用）。 - JAB