5

我有以下功能：

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

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

3 回答 3

5

但是，我对这种方法很不满意：

  • 我是否错过了一些明显的 alloca 危险？

您指出了一个真正的危险：堆栈溢出行为未定义alloca。此外，alloca实际上并没有标准化。例如，Visual C++ 有_alloca，而GCC 默认将其定义为宏. 然而，通过围绕少数现有实现提供一个薄包装器，可以相当容易地规避这个问题。

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

并不真地。C++14 将有一个（可能！）堆栈分配的可变长度数组类型。但在那之前，当您认为std::array不合适时，请选择alloca像您这样的情况。

次要的挑剔：您的代码缺少alloca. 它甚至不应该编译。

于 2013-04-30T19:01:28.540 回答
2

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

还要记住，与 , 相比，堆栈分配非常快malloc（它只是堆栈指针寄存器的减法）。但是使用那个内存可能不行。大量下推堆栈帧的副作用是您将要调用的叶函数的缓存行不再驻留。因此，对该内存的任何使用都需要进入 SMP 环境，以将高速缓存线带回独占（在 MESI 意义上）状态。SMP 总线是一个比 L1 缓存更受限制的环境（！），如果您围绕这个问题向堆栈帧发送垃圾邮件，这可能是一个真正的可扩展性问题。

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

最后，请注意，这malloc真的不是那么慢。如果您正在处理几十 KB 或更大范围的单个缓冲区，那么为您要对它们执行的任何工作提供服务所需的内存带宽将淹没malloc.

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

于 2013-04-30T19:23:16.493 回答
1

这个怎么样：

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

于 2013-04-30T19:53:23.600 回答