Geek asks and answers

Is this a good reason to use alloca?

I have the following function:

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

which performs Lagrange interpolation at xxusing points nstored in xand y. The array workhas a size 2 * n. Since this is polynomial interpolation, it nis in an approximate step of ~ 5, very rarely more than 10.

This function is aggressively optimized and should be called in narrow loops. Profiling suggests that the heap allocating the working array in a loop is bad. Unfortunately, I have to pack this into a function class, and clients should not be aware of the working array.

I am currently using the template integer argument for degree and std::arrayto avoid dynamically allocating an 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?
  • ?
+5
3

:

  • alloca?

: undefined alloca. , alloca . , Visual ++ _alloca , GCC . , .

  • ?

. ++ 14 (!) . , , std::array , alloca , .

nitpick: alloca. .

+5

. , , . , , , , () ().

, malloc ( ). . , , , . SMP, - ( MESI) . SMP - , L1-, , .

, , , gcc, clang ( Intel, ) C99 ++. , libc alloca().

, , malloc . , , , , malloc.

: alloca() , , , , , , .

+2

:

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 a std::array, , .

+1

More articles:


All Articles