c++ - 这是使用 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 的一些明显危险？
• 是否有更好的方法来避免此处的堆分配？

Answer 1

I'm quite unconfortable with the approach however:

• Am I missing some obvious danger of alloca ?

您指出了一个真正的危险:alloca 的堆栈溢出行为未定义。此外，alloca 实际上并未标准化。例如，Visual C++ 有 _alloca 而不是 GCC by default defines it as a macro .然而，通过围绕少数现有实现提供一个薄包装器，可以很容易地规避这个问题。

• Is there a better way to avoid heap allocation here ?

不是真的。 C++14 将有一个(可能!)堆栈分配的可变长度数组类型。但在那之前，当您认为 std::array 不适合时，请在像您这样的情况下使用 alloca。

虽然有点挑剔:您的代码缺少 alloca 返回值的转换。它甚至不应该编译。