Является ли это хорошей причиной для использования alloca?

Question

У меня есть следующие функции:

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 полиномиальная интерполяция).

Я совершенно unconfortable с подходом, однако:

• Я пропускаю некоторые очевидные опасности alloca?
• Есть ли лучший способ избежать выделения кучи здесь?

Answer 1

Я совершенно unconfortable с подходом, однако:

• Я пропускаю некоторые очевидные опасности ALLOCA?

Вы указали одну реальную опасность из: поведение переполнения стека не определен для alloca. Кроме того, alloca на самом деле не стандартизирован. Например, Visual C++ имеет _alloca и GCC by default defines it as a macro. Однако эту проблему можно легко устранить, предоставив тонкую оболочку вокруг нескольких существующих реализаций.

• Есть ли лучший способ избежать выделения кучи здесь?

Не совсем. C++ 14 будет иметь (потенциально!) Стековый тип массива переменной длины.Но до тех пор, и когда вы считаете, что std::array не подходит, подходите к alloca в таких случаях, как ваш.

Незначительный ничтожный: в вашем коде отсутствует листинг возвращаемого значения alloca. Он даже не компилируется.

Answer 2

Всегда есть куча заметок, которые можно добавить к любому использованию памяти стека. Как вы указываете, стеки имеют конечный размер и довольно серьезное неправильное поведение, когда это пространство заканчивается. Переполнение стека, как мы надеемся, приведет к сбою, если есть защищенные страницы, но на некоторых платформах и средах с потоками иногда может возникать некорректное повреждение (проблема) или проблема с безопасностью (что еще хуже).

помнить также, что стек распределение очень быстро по сравнению с malloc, (это просто вычитание из регистра указателя стека). Но использования этой памяти может и не быть. Побочным эффектом толкания вашего стека на большие суммы является то, что строки кэша функций листа, которые вы собираетесь вызывать, больше не являются резидентными. Поэтому любое использование этой памяти должно выходить в среду SMP, чтобы вернуть кэш-строки в исключительное (в смысле MESI) состояние. Шина SMP - это гораздо более сложная среда, чем L1-кеш, и если вы рассылаете свои фреймы стека, это может быть проблемой масштабируемости.

Кроме того, что касается синтаксиса, обратите внимание, что как gcc, так и clang (и, как мне кажется, компилятор Intel) поддерживают синтаксис массива переменной длины 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 a std::array, но я не уверен, какую выгоду вы видите в этом.