Функция нуждается в своем собственном массиве для рабочего пространства - лучшие практики?

Question

Предположим, что функция

void foo(int n, double x[])

сортирует n-вектор x, выполняет некоторые операции с x, а затем восстанавливает исходный порядок до x перед возвратом.Таким образом, для внутреннего использования foo требуется некоторое временное хранилище, например, по крайней мере, n-вектор целых чисел, чтобы оно сохраняло исходный порядок.

Каков наилучший способ обработки этого временного хранилища?Я могу вспомнить два очевидных подхода:

1. foo объявляет свое собственное рабочее пространство, объявляя внутренний массив, т. Е. В верхней части foo мы имеем

   int temp[n];
   

2. в основной вызывающей подпрограмме динамически распределяет n-вектор целых чисел один раз и передает в хранилище при каждом вызове версию foo, которая принимает временное хранилище в качестве 3-го аргумента, то есть

   double *temp = malloc(n*sizeof(double));
   foo(n, x, temp);
   

Я беспокоюсь, что вариант 1 неэффективен (функция foo будет вызываться много раз с тем же n), и опция2 просто безобразно, так как мне приходится носить с собой это временное хранилище, чтобы оно всегда было доступно везде, где мне понадобится вызов foo(n,x).

Есть ли другие более элегантные варианты?

Answer 1

Если в конечном итоге вы используете вариант 2 - то есть функция использует память, выделенную в другом месте - используйте правильную инкапсуляцию.

Короче говоря, не передавайте необработанный массив, передавайте объект context, который имеет соответствующие функции init и release.

Тогда пользователь все равно должен передать контекст и правильно его настроить и разорвать, но подробности скрыты от него, и ему наплевать на детали распределения. Это общий шаблон в C.

typedef struct {
    double* storage;
} foo_context;

void foo_context_init(foo_context*, int n);

void foo_context_free(foo_context*);

void foo(foo_context* context, int n, double x[]);

Теперь для очень простого случая это явно огромные накладные расходы, и я согласен с Оли в том, что потребовался вариант 1.

Answer 2

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

Обновление

@ Комментарий ниже, правильный;это может взорвать ваш стек, если n большой.«Инкапсулированный» метод до C99 заключался бы в том, чтобы распределять локальный массив, а не помещать его в стек.

Answer 3

На большинстве архитектур вариант 1 очень эффективен, поскольку он выделяет память в стеке и обычно является добавлением к стеку и / или указателю кадра. Просто будьте осторожны, чтобы не сделать n слишком большим.

Answer 4

Как сказал Оли в своем ответе, лучше всего иметь автономную функцию для этого временного массива.Одно выделение не будет стоить дорого, если эта функция не вызывается в очень быстром цикле ... так что сначала сделайте все правильно, затем профилируйте, а затем решите, стоит ли проводить оптимизацию.

Это сказано вчерез несколько случаев после профилирования и когда необходимая временная структура данных была немного сложнее, чем один массив int, я принял следующий подход:

void foo(int n, ... other parameters ...)
{
    static int *temp_array, temp_array_size;
    if (n > temp_array_size)
    {
        /* The temp array we have is not big enough, increase it */
        temp_array = realloc(temp_array, n*sizeof(int));
        if (!temp_array) abort("Out of memory");
        temp_array_size = n;
    }
    ... use temp_array ...
}

обратите внимание, что использование статического массива исключает, например, многопоточность или рекурсиюи это должно быть четко указано в документации.