这是使用alloca的好理由吗？

Question

我的职能如下：

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

它使用存储在xx和y中的n点在x上执行拉格朗日插值。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危险？
• 是否有更好的方法来避免这里的堆分配？

Answer 1

然而，我很难接受这种方法：

• 我是不是错过了阿洛卡的明显危险？

您指出了一个真正的危险:对于alloca，堆栈溢出行为是未定义的。此外，alloca实际上并不是标准化的。例如，VisualC++有_alloca和GCC默认将其定义为宏。。但是，通过为现有的少数实现提供一个薄包装，可以很容易地解决这个问题。

• 是否有更好的方法来避免这里的堆分配？

不怎么有意思。C++14将有一个(潜在的！)堆栈分配可变长度数组类型。但在此之前，当您认为std::array不是很适合的时候，在像您这样的情况下选择alloca。

不过，稍微有点麻烦的是:您的代码缺少alloca返回值的强制转换。它甚至不应该编译。

Answer 2

对于堆栈内存的任何使用，总是有一堆注释要添加。正如您所指出的，当空间耗尽时，堆栈具有有限的大小和相当严重的不当行为。如果有保护页面，堆栈溢出可能会崩溃，但在某些平台和线程环境中，有时会出现无声的损坏(坏)或安全问题(更糟)。

还请记住，堆栈分配与malloc相比非常快(它只是堆栈指针寄存器中的一个减法)。但是使用那个内存的可能不是。大量将堆栈帧向下推的副作用是，您将要调用的叶函数的缓存行不再驻留。因此，该内存的任何使用都需要到SMP环境中，以便将缓存线恢复到独占状态(在MESI意义上)。SMP总线是一个非常(!)比L1缓存更受约束的环境，如果您正在垃圾处理您的堆栈帧，这可能是一个真正的可伸缩性问题。

另外，就语法而言，请注意gcc和clang (以及英特尔的编译器，我相信)都支持C99可变长度数组语法作为C++扩展。您可能根本不需要实际调用libc alloca()例程。

最后，请注意，malloc确实没有那么慢。如果您处理的是几十千字节或更大范围内的单个缓冲区，那么无论您在其上做什么工作，所需的内存带宽都将淹没来自malloc的任何开销。

基本上：alloca()很可爱，也有它的用途，但是除非你有一个基准测试来证明你需要它，否则你可能不会，也应该坚持传统的分配。

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，但我不知道您从中看到了什么好处。