The cost of memory allocation in a loop in C

Question

Is there a significant difference between allocating an array inside or outside a loop in terms of cost of time?

I use many arrays in functions inside a loop in my program, should I pass all the arrays as function parameters to increase the performance although it decreases the readability? For example:

#include <stdlib.h>
#define N 1000000
void foo()
{
    int* array = (int*)malloc(N*sizeof(int));
    /*
    Do something with the array
    */
    free(array);
}
int main()
{
    int i;
    for(i=0; i<1000000; i++)
        foo();
    return 0;
}

or

#include <stdlib.h>
#define N 1000000
void foo(int* array)
{
    /*
    Do something with the array
    */
}
int main()
{
    int i;
    int* array = (int*)malloc(N*sizeof(int));
    for(i=0; i<1000000; i++)
        foo(array);
    free(array);
    return 0;
}

Answer 1

The cost of a memory allocation is not very dependent on the size of the allocation. Roughly speaking, a memory allocation of any size is O(1), and obviously standard libraries are optimized to make allocations as fast as possible.

So if you need a very big allocation, as in the example program, the cost of allocation will be trivial compared with the cost of initializing the allocated memory (to say nothing of the cost of actually doing the computation which is required).

For small allocations in very tight loops, where the allocation overhead might be noticeable, alternative mechanisms might be useful; one of these is the one suggested in the question, passing a preallocated array as an additional parameter to the function. (Other possibilities include using C's variable length arrays (VLAs), if they are available on all target platforms, or alloca/_alloca/_malloca.)

But I would suggest not implementing microoptimizations of this form until there is solid evidence that the time savings are justified; otherwise, the cost in maintainability and readability will outweigh any small time savings you might achieve.