C: Возвращение пустоты против возврата двойного * из подфункции

Question

Я пытаюсь ускорить некоторую общую обработку данных в C. Я написал несколько подпрограмм в виде:

double *do_something(double *arr_in, ...) {
   double *arr_out; 
   arr_out = malloc(...)

   for (...) {
     do the something on arr_in and put into arr_out
   }

   return arr_out; 
}

Мне нравится этот стиль, потому что его легко читать и использовать, но часто я называю его так:

 array = do_something(array,...);

Будет ли это быстрее кода (и, возможно, предотвратить утечки памяти), если бы вместо этого я использовал вместо void подфункции:

void do_something(double *arr_in, ...) {
   for (...) {
      arr_in = do that something;
   }
   return;
}

обновление 1: Я запустил valgrind --leak-check = full в исполняемом файле, и похоже, что при использовании первого метода не было утечек памяти. Тем не менее, исполняемый файл ссылается на библиотеку, которая содержит все подпрограммы, которые я сделал с помощью этой формы, поэтому он может не улавливать утечки из библиотеки.

Мне интересно, как бы я написал обертки для освобождения памяти и что на самом деле делает **, или что такое указатель на указатель, поэтому я избегаю использования маршрута ** (это и, возможно, Я сделал это неправильно, потому что он не компилируется на моем Mac).

Вот одна текущая подпрограмма:

double *cos_taper(double *arr_in, int npts)
{
int i;
double *arr_out;
double cos_taper[npts];
int M; 
M = floor( ((npts - 2) / 10) + .5);

arr_out = malloc(npts*sizeof(arr_out));

for (i=0; i<npts; i++) {
    if (i<M) {
        cos_taper[i] = .5 * (1-cos(i * PI / (M + 1)));
    }
    else if (i<npts - M - 2) {
        cos_taper[i] = 1;
    }
    else if (i<npts) {
        cos_taper[i] = .5 * (1-cos((npts - i - 1) * PI / (M + 1)));
    }
    arr_out[i] = arr_in[i] * cos_taper[i];
}
return arr_out;
}

Исходя из совета, который я получил здесь, звучит так, что лучшим методом будет:

void *cos_taper(double *arr_in, double *arr_out, int npts)
{
int i;
double cos_taper[npts];
int M; 
M = floor( ((npts - 2) / 10) + .5);

for (i=0; i<npts; i++) {
    if (i<M) {
        cos_taper[i] = .5 * (1-cos(i * PI / (M + 1)));
    }
    else if (i<npts - M - 2) {
        cos_taper[i] = 1;
    }
    else if (i<npts) {
        cos_taper[i] = .5 * (1-cos((npts - i - 1) * PI / (M + 1)));
    }
    arr_out[i] = arr_in[i] * cos_taper[i];
}
return
}

звоните:

int main() {
  int npts;
  double *data, *cos_tapered;

  data = malloc(sizeof(data) * npts);
  cos_tapered = malloc(sizeof(cos_tapered) * npts);

//fill data

  cos_taper(data, cos_tapered, npts);
  free(data);
  ...
  free(cos_tapered);
  ...
  return 0;
}

Answer 1

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

Answer 2

Я только что запустил ваш код (после исправления ряда мелких ошибок). Затем я сделал несколько стеков . Люди, которые сказали, что «1003» будет вашим виновником, были правы. Почти все вашего времени проведено там. По сравнению с этим, остальная часть вашего кода не очень важна. Вот код:

#include <math.h>
#include <stdlib.h>
const double PI = 3.1415926535897932384626433832795;

void cos_taper(double *arr_in, double *arr_out, int npts){ 
    int i; 
//  double taper[npts];
    double* taper = (double*)malloc(sizeof(double) * npts); 
    int M;  
    M = (int)floor( ((npts - 2) / 10) + .5); 

    for (i=0; i<npts; i++){ 
        if (i<M) { 
            taper[i] = .5 * (1-cos(i * PI / (M + 1))); 
        } 
        else if (i<npts - M - 2) { 
            taper[i] = 1; 
        } 
        else if (i<npts) { 
            taper[i] = .5 * (1-cos((npts - i - 1) * PI / (M + 1))); 
        } 
        arr_out[i] = arr_in[i] * taper[i]; 
    }
    free(taper);
    return;
}

void doit(){
    int i;
    int npts = 100; 
    double *data, *cos_tapered; 

    data = (double*)malloc(sizeof(double) * npts); 
    cos_tapered = (double*)malloc(sizeof(double) * npts); 

    //fill data 
    for (i = 0; i < npts; i++) data[i] = 1;

    cos_taper(data, cos_tapered, npts); 
    free(data); 
    free(cos_tapered); 
}

int main(int argc, char* argv[]){
    int i;
    for (i = 0; i < 1000000; i++){
        doit();
    }
    return 0;
}

РЕДАКТИРОВАТЬ: я рассчитал вышеуказанный код, который занял 22us на моей машине (в основном в malloc). Затем я изменил его, чтобы сделать mallocs только один раз снаружи. Это сократило время до 5.0us, что было в основном в функции cos. Затем я переключился с Debug на Release build, который сократил время до 3.7us (теперь даже больше в функции cos, очевидно). Так что, если вы действительно хотите сделать это быстро, я рекомендую делать стеки, чтобы выяснить, что вы в основном делаете, а затем посмотреть, сможете ли вы избежать этого.

Answer 3

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

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

Например, предположим, что вы хотите создать функцию, которая перетасовывает массив индексов так, что output[i] == input[ input[i] ] (глупая функция, правда, но нетривиальная на месте).

#include <stdlib.h> 
#include <string.h>
int shuffle(size_t const * input, size_t const size, size_t ** p_output)
{
    int retval = 0;
    size_t i;
    char in_place = 0;
    char cleanup_output = 0;

    if (size == 0)
    {
        return 0; // nothing to do
    }
    // make sure we can read our input and write our output
    else if (input == NULL || p_output == NULL)
    {
        return -2; // illegal input
    }
    // allocate memory for the output
    else if (*p_output == NULL)
    {
        *p_output = malloc(size * sizeof(size_t));
        if (*p_output == NULL) return -1; // memory allocation problem
        cleanup_output = 1; // free this memory if we run into errors
    }
    // use a copy of our input, since the algorithm doesn't operate in place.
    // and the input and output overlap at least partially
    else if (*p_output - size < input && input < *p_output + size)
    {
        size_t * const input_copy = malloc(size * sizeof(size_t));
        if (input_copy == NULL) return -1; // memory allocation problem
        memcpy( input_copy, input, size * sizeof(size_t));
        input = input_copy;
        in_place = 1;
    }

    // shuffle
    for (i = 0; i < size; i++)
    {
        if (input[i] >= size)
        {
            retval = -2; // illegal input
            break;
        }
        (*p_output)[i] = input[ input[i] ];
    }

    // cleanup
    if (in_place)
    {
         free((size_t *) input);
    }
    if (retval != 0 && cleanup_output)
    {
         free(*p_output);
         *p_output = NULL;
    }

    return retval;
}

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

// caller allocated memory
my_allocated_mem = malloc( my_array_size * sizeof(size_t) );
if(my_allocated_mem == NULL) { /*... */ }
shuffle( my_array, my_array_size, &my_allocated_mem );

// function allocated memory
my_allocated_mem = NULL;
shuffle( my_array, my_array_size, &my_allocated_mem );

// in place calculation
shuffle( my_array, my_array_size, &my_array);

// (naughty user isn't checking the function for error values, but you get the idea...)

Вы можете увидеть полный пример использования здесь .

Поскольку в C нет исключений, достаточно стандартно использовать возвращаемое значение функции для сообщения об ошибках и передавать вычисленные значения обратно через указатель функции.

Answer 4

Возврат самого двойника не требует больших затрат с точки зрения времени исполнения.

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

Еще одна вещь, которую следует учитывать, - нужна ли вам вся точность, которую обеспечивает double (по сравнению с типом float). Во многих случаях плавает намного быстрее.

Answer 5

Если вы можете выполнить свою операцию на месте, это, вероятно, поможет предотвратить ошибки (по крайней мере, связанные с памятью) и будет быстрее, по крайней мере, за время, необходимое для выполнения операции malloc(). Фактический тип возврата вашей функции, вероятно, никак не влияет на скорость.

Answer 6

Первый вызов может легко привести к утечке памяти, если нет другого указателя на исходное распределение памяти - как вы, вероятно, знаете, так как вы спрашиваете.

Да, если вы можете разумно написать вторую версиюВызванная функция без выделения памяти, скорее всего, будет быстрее, поскольку выделение памяти занимает много времени.Если вы просто измените вызываемую функцию так, чтобы у нее были предварительно выделенные входные и выходные массивы, она могла бы просто перенести стоимость выделения памяти на вызывающую функцию.

Но дисциплинированное использование первой версии хорошо;функция выделяет пространство, и пока вы отслеживаете как исходное пространство, переданное внутрь, так и новое пространство, переданное обратно, и можете освободить оба, проблем нет.

Вы можете запустить себя в 'та же самая проблема с:

xyz = realloc(xyz, newsize);

Если xyz является единственным указателем на выделенную память, это приводит к утечке памяти при ошибке выделения, потому что вы только что закрыли xyz нулевым указателем.Если есть другой указатель, который вы будете использовать для освобождения исходного пространства, эта идиома не имеет значения - но будьте осторожны с ней.

---

Я не полностью усвоил дополнительную информацию в вопросе с момента написанияоригинальная версия этого ответа.

Answer 7

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

Я согласен с другими ответами: первое предложение с использованием malloc - это путь к утечкам памяти (и, вероятно, в любом случае медленнее), другое предложение, к которому вы пришли, гораздо лучше. Следуя предложениям ergosys в комментариях, вы можете легко улучшить его и получить хороший C-код.

Теперь с небольшим количеством математики вы все еще можете поправиться.

Во-первых, нет необходимости использовать двойной и минимальный вызов для вычисления целых чисел. Вы получаете тот же M без пола и без добавления 0,5, просто написав M = (nbelts-2) / 10; (Подсказка: целочисленное деление усекается до целого).

Если вы также заметили, что у вас всегда есть M

Ваша функция может выглядеть примерно так:

void cos_taper(double *arr_in, double *arr_out, int npts)
{
int i;
int M; 
M = (npts - 2) / 10;

if (arr_out == arr_in) {
    for (i=0; i<M; i++) {
        arr_out[i] *= .5 * (1-cos(i * PI / (M + 1)));
    }
    for (i = npts - M - 2; i<npts; i++) {
        arr_out[i] *= .5 * (1-cos((npts - i - 1) * PI / (M + 1)));
    }
}
else {
    for (i=0; i<M; i++) {
        arr_out[i] = arr_in[i] * (.5 * (1-cos(i * PI / (M + 1))));
    }
    for (; i<npts - M - 2; i++) {
        arr_out[i] = arr_in[i];
    }
    for (; i<npts; i++) {
        arr_out[i] = arr_in[i] * (.5 * (1-cos((npts - i - 1) * PI / (M + 1))));
    }
}
}

Это положительно, но это еще не конец, и, если подумать, возможна дополнительная оптимизация, например, выражения типа (.5 * (1-cos(i * PI / (M + 1)))); выглядят так, как будто они могут получить относительно небольшое количество значений (зависит от размера nbelt, поскольку это функция i и nbelt, число различных результатов является квадратичным законом, но потому что оно должно уменьшить это число снова, поскольку оно периодическое). Но все зависит от того, какой уровень производительности вам нужен.

Answer 8

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

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

Answer 9

Я бы посоветовал, чтобы, если вы выделяете память внутри подфункции, вы либо создали соответствующую оболочку для очистки, освободили выделенную память или сделали ослепительно очевидным, что функция выделяет память, чтобы не забыть освободить память.

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

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

Answer 10

У вас также есть возможность передать второй параметр в качестве вашего параметра out. Например

int do_something (double * in , double * out) {
   /*
    * Do stuff here
    */
   if (out is modified)
      return 1;
   return 0;
}

или аналогичный без возврата.