这是否是使用alloca的好理由？

Question

我有以下函数：

double 
neville (double xx, size_t n, const double *x, const double *y, double *work);

此函数在 x 和 y 中存储的 n 个点上，以 xx 进行拉格朗日插值。 work 数组的大小为 2 * n。由于这是多项式插值，所以 n 大概在 ~5 左右，很少会超过 10。

此函数经过了积极优化，应在紧密循环中调用。分析表明，在循环中堆分配工作数组是不好的。不幸的是，我必须将其打包成类似函数的类，并且客户端必须不知道工作数组。

目前，我使用模板整数参数来表示该函数的次数，并使用 std::array 来避免动态分配 work 数组：

template <size_t n>
struct interpolator
{
    double operator() (double xx) const
    {
        std::array<double, 2 * n> work;
        size_t i = locate (xx); // not shown here, no performance impact
                                // due to clever tricks + nice calling patterns

        return neville (xx, n, x + i, y + i, work.data ());
    }        

    const double *x, *y;
};

可以将工作数组作为类的可变成员进行存储，但是operator()应该被多个线程并发使用。只要在编译时知道n，这个版本就可以使用。

现在，我需要在运行时指定n参数。我在思考像这样的解决方案：

double operator() (double xx) const
{
    auto work = static_cast<double*> (alloca (n * sizeof (double)));
    ...

使用 alloca 时会有一些警告：当然，我必须对 n 设定上限以避免 alloca 调用溢出（不管怎么说，使用100次多项式插值是相当愚蠢的）。

但是，我对这种方法感到非常不舒服：

• 我是否忽略了一些明显的 alloca 危险？
• 有没有更好的方式来避免堆分配？

- Alexandre C.

---

你不能只是用C语言编写这个函数并使用C99 VLAs吗？ - user529758

@KonradRudolph double neville (double xx, size_t n, const double *x, const double *y, double *work); - 你需要运算符重载来编写这个函数吗？哇，我从来不知道！ - user529758

@H2CO3 哈哈，你抓住我了。我的最后一个论点是，我非常不喜欢将C和C++代码链接在一起。当然，如果做得正确，就没有真正的问题！但是，我遇到过许多链接错误的C库，给我带来了很多痛苦。但是，我看不出使用可变长度数组（VLA）比使用alloca有什么好处，也许我错过了什么……？ - Konrad Rudolph

@KonradRudolph 为了受益：alloca()在失败时可能会调用UB，VLAs在C99标准中，alloca()甚至不是POSIX等。 - user529758

@H2CO3 请阅读 https://dev59.com/rnNA5IYBdhLWcg3wUL1Y#1018865 上的评论。本质上，可变长度数组（VLA）与 alloca 具有完全相同的缺点，除了缺乏标准化。但是 GCC 确实 支持它，如果您想编写可移植代码，可以自己提供 alloca.h（尽管缺乏标准化是一个好观点，并值得修改我的答案）。 - Konrad Rudolph

Answer 1

我对这种方法感到相当不舒服：

• 我是否忽略了一些明显的alloca危险？

你指出了唯一的真正危险：alloca的堆栈溢出行为未定义。此外，alloca实际上并没有标准化。例如，Visual C++使用_alloca而非alloca，GCC默认将其定义为宏。然而，可以通过提供围绕少数现有实现的薄包装来轻松解决该问题。

• 是否有更好的方法避免在此处进行堆分配？

实际上没有。C++14将具有（可能！）堆栈分配的变长数组类型。但在那之前，并且当您认为std :: array不适合时，请在您这种情况下选择alloca。

小小的挑剔一下：您的代码缺少对alloca返回值的强制转换。它甚至不应该编译。

- Konrad Rudolph

---

我受到匿名投票的伤害。有人愿意来安慰我吗？ - Konrad Rudolph

只是猜测关于负投票：建议使用非标准特性，尤其是在没有说明的情况下（在您的原始版本中），以及可能建议在C++中使用基本上是C库函数的内容，这些都有可能吸引纯粹主义者的负投票，而您两者都做到了。 - hyde

Answer 2

使用堆栈内存时，总是有一堆注意事项需要添加。正如您所指出的，堆栈具有有限的大小，在空间用尽时会出现严重的错误行为。如果存在保护页面，希望发生堆栈溢出崩溃，但某些平台和线程环境可能会导致静默破坏（不好）或安全问题（更糟）。

还要记住，与malloc相比，堆栈分配非常快（只需从堆栈指针寄存器中减去）。但是，该内存的使用可能并不快。将堆栈帧向下移动大量的副作用是要调用的叶函数的缓存行不再驻留。因此，对该内存的任何使用都需要离开SMP环境，以将缓存行置回排他（在MESI意义上）状态。SMP总线是一个比L1缓存约束得多的环境，如果您正在频繁地传递堆栈帧，则可能会导致实际的可扩展性问题。

此外，就语法而言，请注意gcc和clang（以及Intel的编译器，我相信）支持C99变长数组语法作为C++扩展。您可能根本不需要调用libc alloca（）例程。

最后，请注意malloc真的不那么慢。如果您正在处理几十千字节或更大的单个缓冲区，则为执行任何工作所需的内存带宽将淹没来自malloc的任何开销。

基本上：alloca（）很可爱，而且有其用途，但除非您已准备好进行基准测试并证明需要它，否则您可能不需要它，并且应该坚持传统分配。

- Andy Ross

---

你是否对缓存关联性做出了特定的假设？因为我不明白为什么动态内存应该会将更少的页面带入缓存——事实上，它应该会触及更多页面，因为它必须访问堆内部数据结构。因此，它更有可能而不是更少地导致叶函数使用的页面被驱逐。如果您担心这些页面一开始就没有在缓存中，我不明白为什么。在大量使用大型堆栈分配的程序中，这些堆栈页面将在缓存中保持热度。 - Ben Voigt

@andy：我明白你关于第一个调用的意思。（当然，这涉及到守卫页、异常处理、更新TLB - 并将新页面带入独占状态是你最不用担心的）但是，之后是什么导致这些页面离开E状态呢？栈对于每个线程都是本地的，没有其他线程会声明所有权。唯一会导致缓存行失去排他性的事情就是它被驱逐了。而本地堆栈缓冲区会导致更少的驱逐。抱歉，虽然我喜欢你的思路，但这个答案是错误的。 - Ben Voigt

栈增长非常昂贵——仅一次。提交新页面需要与全系统VMM数据结构同步访问。可能需要将页面刷新到磁盘、清零等操作。 - Ben Voigt

但它并没有使用不同的行。要么（a）此线程正在增加其堆栈，要么（b）此线程是最后一个以任何方式使用这些缓存行的核心，这意味着它们仍处于E状态，除非它们被驱逐。 - Ben Voigt

我只知道三个缓存行失去排他性的原因：（1）另一个线程的实际访问——对于本地使用的工作缓冲区不会发生这种情况（2）由于缓存太小而导致的驱逐——动态分配更有可能导致这种情况（3）调度程序将线程移动到另一个核心——这将对仅由一个线程使用的动态分配缓冲区产生相同的性能影响。 - Ben Voigt

Answer 3

这个怎么样：

double operator() (double xx) const
{
    double work_static[STATIC_N_MAX];
    double* work = work_static;
    std::vector<double> work_dynamic;

    if ( n > STATIC_N_MAX ) {
        work_dynamic.resize(n);
        work = &work_dynamic[0];
    }

    ///...

没有不可移植的特性，异常安全，并且当 n 太大时会逐渐降级。当然，你可以将 work_static 设为 std::array，但我不确定你在其中看到了什么好处。

- Ben Voigt

---

有时候我会错过显而易见的事情... 我正在考虑禁止大于20的n值（或某个预处理器常量，我的真实函数是基于y参数模板化的，因此完整的源代码是可用的）。如果每次在堆栈上分配320字节不会降低性能，那么这是值得一试的。 - Alexandre C.

@AlexandreC.：人们可以想象一种实现了“小字符串优化”的std::vector，它将包装这个丑陋的东西。 - Ben Voigt

如果您认为堆分配可能成为瓶颈，那么在堆栈中使用过大的数组也可能会对CPU缓存产生影响，这并不理想。但是，请在真正的多线程负载下进行基准测试。 - hyde

@hyde：当然。我不是“认为”，而是已经“测量”过堆分配是否成为瓶颈。在这里，性能基准测试也非常重要。 - Alexandre C.