Это хорошая причина для использования alloca?
У меня есть следующая функция:
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? - Есть ли лучший способ избежать выделения кучи здесь?
Решение
Однако я совершенно не согласен с таким подходом:
- Я упускаю какую-то очевидную опасность отвести?
Вы указали одну реальную опасность: поведение переполнения стека не определено для alloca, К тому же, alloca на самом деле не стандартизировано. Например, Visual C ++ имеет _alloca вместо этого и GCC по умолчанию определяет его как макрос. Однако эту проблему можно обойти довольно просто, предоставив тонкую оболочку для нескольких существующих реализаций.
- Есть ли лучший способ избежать выделения кучи здесь?
На самом деле, нет. C ++ 14 будет иметь (потенциально!) Тип массива с переменной длиной стека. Но до тех пор, и когда вы считаете, std::array чтобы не быть в хорошей форме, пойти на alloca в таких случаях, как ваш.
Незначительная мелочь: в вашем коде отсутствует приведение к возвращаемому значению alloca, Это даже не должно компилироваться.
Другие решения
Всегда есть куча заметок, которые можно добавить к любому использованию стековой памяти. Как вы указываете, стеки имеют конечный размер и довольно серьезное неправильное поведение, когда это пространство заканчивается. Мы надеемся, что переполнение стека завершится сбоем, если есть защитные страницы, но на некоторых платформах и в многопоточных средах иногда может быть тихое повреждение (плохо) или проблема безопасности (хуже).
Также помните, что стек распределение очень быстро по сравнению с malloc(это просто вычитание из регистра указателя стека). Но использование этой памяти не может быть. Побочным эффектом большого уменьшения размера стека является то, что строки кэша конечных функций, которые вы собираетесь вызвать, больше не являются резидентными. Поэтому любое использование этой памяти должно выходить в среду SMP, чтобы вернуть строки кэша в исключительное (в смысле MESI) состояние. Шина SMP является гораздо (!) Более ограниченной средой, чем кэш-память L1, и если вы рассылаете спам вокруг своих стековых фреймов, это может стать реальной проблемой масштабируемости.
Кроме того, что касается синтаксиса, обратите внимание, что и gcc, и clang (и, как мне кажется, компилятор Intel) поддерживают синтаксис массива переменной длины C99 как расширение C ++. Возможно, вам не нужно на самом деле позвонить в libc alloca() рутина вообще.
Наконец, обратите внимание, что malloc на самом деле не так медленно. Если вы имеете дело с одиночными буферами размером в десятки килобайт или больше, то пропускная способность памяти, необходимая для обслуживания любой работы, которую вы собираетесь над ними выполнять, может затормозить любые накладные расходы. malloc,
В принципе: alloca() это мило, и имеет свои применения, но если у вас нет эталона, готового доказать, что он вам нужен, вы, вероятно, не будете и должны просто придерживаться традиционного распределения.
Как насчет этого:
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, но я не уверен, какую пользу вы видите в этом.