6

我正在努力尝试加快 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;
}
4

12 回答 12

5

malloc 相对于您正在执行的处理可能很昂贵,具体取决于它是什么。与其将自己限制在就地处理,不如使用两个参数,in 和 out,并将分配留给调用者。这使调用者可以选择重用内存,而无需为每次调用分配一个新数组。

于 2010-02-05T18:12:42.093 回答
1

我刚刚运行了您的代码(在修复了一些小错误之后)。然后我拍了几张照片。那些说malloc会是你的罪魁祸首的人是对的。你几乎所有的时间都花在了那里。与此相比,您的其余代码并不是很重要。这是代码:

#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 构建,这将时间降低到 3.7us(cos显然,现在在函数中甚至更多)。因此,如果您真的想加快速度,我建议您使用 stackshots 来找出您主要在做什么,然后看看您是否可以避免这样做。

于 2010-02-06T01:44:12.777 回答
1

如果他们愿意,我会选择让调用者分配内存,但也可以选择让操作就地完成,或者让你进行分配。

对于不能就地完成的操作,可以手动检查调用者是否给了你相同的输入输出位置,自己复制输入。然后使用该副本作为输入进行处理。这使它在函数调用者看来就位。

例如,假设您要创建一个函数,该函数对一组索引进行混洗,这样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 没有异常,因此使用函数的返回值报告错误并通过函数指针将计算值传回是相当标准的。

于 2010-02-05T19:46:51.383 回答
1

如果没有其他指向原始内存分配的指针,第一次调用很容易泄漏内存 - 正如您在询问时可能知道的那样。

是的,如果您可以明智地编写不分配内存的调用函数的第二个版本,它可能会更快,因为内存分配需要时间。如果您只是修改被调用函数,使其具有预先分配的输入和输出数组,它可能只是将内存分配成本转移到调用函数。

但是有规律地使用第一个版本是可以的;该函数分配空间,只要您跟踪传入的原始空间和传回的新空间并且能够释放两者,就没有问题。

您可以通过以下方式遇到“相同”问题:

xyz = realloc(xyz, newsize);

如果 xyz 是指向已分配内存的唯一指针,则在分配失败时会泄漏内存,因为您刚刚使用空指针破坏了 xyz。如果您将使用另一个指针来释放原始空间,则此成语无关紧要-但要谨慎使用。


自从编写此答案的原始版本以来,我还没有完全消化问题中的其他信息。

于 2010-02-05T18:08:00.497 回答
1

如果您可以在适当的位置进行操作,那么这样做可能有助于防止错误(至少与内存相关的错误),并且至少会比执行malloc()操作所花费的时间更快。函数的实际返回类型可能不会以任何方式影响速度。

于 2010-02-05T18:08:34.917 回答
1

double 本身的返回在执行时间方面不会花费你太多。

更重要的是每次进入函数时的内存分配。如果您可以按照您的建议预先分配或存储结果,那将大大提高速度。

要考虑的另一件事是您是否真的需要双精度提供的所有精度(与浮点类型相比)。在许多情况下,浮点数要快得多。

于 2010-02-05T18:11:02.720 回答
0

好吧,你开始你的问题是谈论速度,我不相信这个问题真的得到了回答。首先要说的是,处理参数传递似乎不是加快速度的更好方法......

我同意其他答案:使用 malloc 的第一个建议是内存泄漏的高速公路(无论如何可能更慢),您提出的另一个建议要好得多。按照评论中的 ergosys 建议,您可以轻松增强它并获得良好的 C 代码。

现在有了一些数学,你仍然可以变得更好。

首先,不需要使用 double 和 floor call 来计算整数。你得到相同的 M 没有地板也没有增加 0.5 只是写 M = (nbelts-2) / 10; (提示:整数除法截断为整数)。

如果你还注意到你总是有 M < nbelt - M - 2 < nbelt(嗯,你肯定已经知道了),你可以通过将循环分成三个独立的部分来避免测试循环内的限制。在数组与输出数组相同的情况下,这仍然可以优化。

你的函数可能变成这样:

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 的函数,不同的数量结果是平方定律,但 cos 应该再次减少该数字,因为它是周期性的)。但这一切都取决于您需要什么级别的性能。

于 2010-02-05T23:48:55.803 回答
0

您还可以选择将第二个参数作为输出参数传递。例如

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

或类似的没有回报。

于 2010-02-05T18:16:25.217 回答
0

我建议如果你在子函数中分配内存,你要么创建一个相应的包装器来清理,释放分配的内存,要么让函数正在分配内存非常明显,以防止忘记释放内存.

关于内存占用,第二种方法将使用更少的内存,但它仅在函数不修改初始数组的大小时才有效。根据使用情况,这并不总是正确的。

关于速度,第二种方法理论上应该更快,因为在函数调用结束时将一个指针压入堆栈do_something(考虑内联应该已经是一个考虑因素。因此,除非您实际测量了函数调用的开销作为一个问题(通过分析),否则我不会在没有充分理由(内存占用或分析)的情况下为此类微优化而烦恼。

于 2010-02-05T18:20:27.317 回答
0

如果没有 malloc,您将节省少量时间,但如果您在紧密循环中调用 do_something,这可能会很快加起来并产生明显的差异。您还可以通过不必返回双 * 来节省少量时间,但同样,如果 do_something 被频繁调用,这可以加起来。

至于处理本身,没有区别,因为两种情况都是在双 *

由于您在建议的方法中没有使用动态内存分配,因此不再存在内存泄漏的可能性。

于 2010-02-05T18:13:37.243 回答
0

函数的类型决定了函数与调用它的代码中的位置之间的接口,也就是说在选择时很可能涉及到重要的代码设计问题。通常,这些比速度更值得考虑(前提是速度问题不是内存泄漏大到应用程序通过抖动遭受 DOS 的影响……)

第二种类型几乎表明了改变数组的意图。第一个是模棱两可的:也许你总是会改变数组,也许你总是会提供一个新的分配结果,也许你的代码有时会做一个,有时会做另一个。自由伴随着确保代码正确的困难雷区。如果你走这条路,在assert()你的代码中加入大量的 s 来断言关于指针的新鲜度和共享性的不变量,在调试时可能会以极大的兴趣为自己付出代价。

于 2010-02-05T20:41:40.803 回答
0

在你的功能

无效do_something(双*arr_in,...){
   为了 (...) {
      arr_in = do_that_something;
   }
}

这将是不正确的,因为一旦do_something函数超出范围,您就没有按引用传回数组的参数。它应该看起来像这样

无效do_something(双**arr_in,...){
   为了 (...) {
      *arr_in = do_that_something;
   }
}
/*
** 会这样调用:
** do_something(&array, ...);
*/

坚持第一个例子,因为它更容易阅读。如果调用malloc失败并使用 NULL 指针继续处理,则需要在第一个示例中添加错误检查...

希望这会有所帮助,最好的问候,汤姆。

于 2010-02-05T18:09:52.790 回答