0

I am working with large arrays in C for numerical calculations.

Within one of the functions I make use of some temporary local (disposable) arrays. Normally I would just declare these as double v[N] and then not worry about having to free the memory manually.

The problem that I have noticed is that when my N gets very large (greater than 4 million) my program fails to declare the variable. Hence I resorted to malloc() and free() which allows me to run the program successfully. The problem is that my execution time almost doubles from 24s to 40s when I use the dynamic allocation (for a smaller N).

It is possible for me to modify the code to avoid creating these temporary arrays in the first place, however it would impact on the readability of the code and coding effort. I am currently using a preprocessor macro to access the vector like a 2D matrix. Is there another solution that will avoid the CPU cost whilst allowing me to save the data like a matrix?

Community
  • 1
  • 1
xyz
  • 397
  • 2
  • 8
  • 1
    You could just call `malloc()` once to allocate a very large temporary array, or a handful of times to allocate a handful of temporary arrays. After that, it should be as fast as statically allocated arrays. No need to `free()` them as long as you keep reusing them. Only pay the allocation penalty once. – Joe Z Dec 06 '13 at 03:55
  • @JoeZ: I have found that regardless of whether I only call `malloc()` once, (e.g. passing a pointer to the malloc'd memory to the function or initialising it only once as a static pointer) the execution time is still increased, leading me to believe that the cost is for read access to the heap rather than an allocation penalty. – xyz Dec 07 '13 at 07:34
  • Then there is probably something else at play. The heap isn't magically slower than the stack all by itself. Either you're getting better cache locality in your algorithm, or the compiler is able to apply some optimizations because it did a better job of alias analysis in the non-heap version. – Joe Z Dec 07 '13 at 16:35
  • Hmmm... I'm out of ideas of how to get the C compiler to optimize it. Tried the `restrict` keyword which didn't make a difference. – xyz Dec 07 '13 at 18:18
  • Hmmm... I'm personally out of ideas. Without seeing the code (and the compiler-generated output), it's hard to say what's pessimizing the code. – Joe Z Dec 07 '13 at 18:21

1 Answers1

1

When you declare a variable local to the method you are working with automatic allocated variables which go on the stack and unfortunately the stack size is limited. Using malloc means that the variable will be allocated on heap and the time difference is what you pay for that dynamic allocation.

I see two possible solutions:

  • use a static global array (and reuse it when necessary) so that the compiler will be able to optimize accesses to it
  • change the stack size so that you won't have problems with larger arrays local to your functions, this can be done even dynamically, take a look here.
Community
  • 1
  • 1
Jack
  • 131,802
  • 30
  • 241
  • 343
  • Thanks @Jack, the `static` solution seems very straightforward and should work, however for some reason I am getting the same execution time increase when I replace `double v[N]` with `static double* v; static int b=1; if(b==1){b=0; v=malloc(sizeof(double[N]));}`. Any idea what is going wrong? – xyz Dec 06 '13 at 04:41
  • (as for option 2: `setrlimit` is not able to provide the stack sizes that I am requesting (the function returns an error code `-1`)) – xyz Dec 06 '13 at 05:00
  • 1
    You can directly allocate a `static double v[N]` block. No need for `malloc` at all, otherwise you'll end up in the same problem. – Jack Dec 06 '13 at 05:39
  • 1
    Note that the use of a static array in such a way makes your functions thread-unsafe. May not matter, but needs mentioning. – Martin James Dec 06 '13 at 10:42
  • @MartinJames: Is there any way to have a thread safe implementation, with `N` as a function argument (unknown at compile time), that can be executed for the same cost as @Jack's `static` method above? – xyz Dec 07 '13 at 07:46