Does initialization of 2D array in c program waste of too much time?

Question

I am writing a C program which has to use a 2D array to store previously processed data for later using.

The size of this 2D array 33x33; matrix[33][33].

I define it as a global parameter, so it will be initialized for only one time. Dose this definition cost a lot of time when program is running? Because I found my program turn to be slower than previous version without using this matrix to store data.

Additional:

I initialize this matrix as a global parameter like this:

int map[33][33];

1. In one of function A, I need to store all of 33x33 data into this matrix.
2. In another function B, I will fetch 3x3 small matrix from map[33][33] for my next step of processing.

Above 2 steps will be repeated for about 8000 times. So, will it affect program running efficiency?

Or, I have another guess that the program truns to be slower because of there are couple of if-else branch statements were lately added into the program.

Answer 1

theoretically using N-th dimensional array shouldn't have performance difference as all of them resolve into contiguous memory reservation by compiler.

int _1D[1089]; int _2D[33][33]; int _3D[3][11][33];

should give similar allocation/deallocation speed.

Answer 2

You need to benchmark your program. If you don't need the initialization, don't make the variable static, or (maybe) allocate it yourself from the heap using malloc():

mystery_type *matrix;

matrix = malloc(33 * 33 * sizeof *matrix);

Answer 3

No, there is no difference in runtime between initializing an array once (with whatever method) and not initializing it.

If you found a difference between your 2 versions, that must be due to differences in the implementation of the algorithm (or a different algorithm).

Answer 4

Well, I wouldn't expect it to (something like that should take much less than a second), but an easy way to find out would be to simply put a print statement at the start of main().

That way you can see if global, static variable initialization is really causing this. Is there anything else in your program that you've changed lately?

EDIT One way to get a clearer idea of whats taking so long would be to use a debugger like GDB or a profiler like GProf

Answer 5

If your program is accessing the matrix a lot during running (even if it's not being updated at all), the calculations of address of an element will involve a multiply by 33. Doing a lot of this could have the effect of slowing down your program.

Answer 6

Simplifying slightly, there are three kinds of variables in C: static, automatic, and dynamic.

Static variables exist throughout the lifetime of the program, and include both global variables, and local variables declared using static. They are either initialized to zeroes (the default), or explicitly initialized data. If they are zeroes, the linker stores them into a fresh memory page that it initializes to zeroes by the operating system (this takes a tiny amount of time). If they are explicitly allocated, the linker puts the data into a memory area in the executable and the operating system loads it from there (this requires reading the data from disk into memory).

Automatic variables are allocated from the stack, and if they are initialized, this happens every time they are allocated. (If not, they have no value, or perhaps they have a random value, and so initialization takes no time.)

Dynamic variables are allocated using malloc, and you have to initialize them yourself, and that again takes a bit of time.

It is highly probably that your slowdown is not caused by the initialization. To make sure of this, you should measure it by profiling your program and seeing where time is spent. Unfortunately, profiling may be difficult for initialization done by the compiler/linker/operating system, especially for the parts that happen before your program starts executing.

If you want to measure how much time it takes to initialize your array, you could write a dummy program that does nothing but includes the array.

However, since 33*33 is a fairly small number, either your matrix items are very large, your computer is very slow, or your 33 is larger than mine.

Answer 7

How ere you doing it before? The only problem I can think of is that extracting a 3x3 sub matrix from a 33x33 integer matrix is going to cause you cacheing issues every time you extract the sub matrix.

On most modern machines the cacheline is 64 bytes in size. Thats enough for 8 elements of the matrix. So for each extra line of the 3x3 sub matrix you will be performing a new cacheline fetch. If the matrix gets hammered very regularly then the matrix will probably sit mostly in the level 2 cache (or maybe even the level 1 if its big enough) but if you are doing lots of other data calculations in between each sub-matrix fetch then you will be getting 3expensive cacheline fetches each time you grab the sub matrix.

However even then its unlikely you'd see a HUGE difference in performance. As stated elsewhere we need to see before and after code to be able to hazard a guess at why performance has got worse ...

Answer 8

How did your previous program version store the data if not in matrix? How were you able to read a sub-matrix if you did not have the big matrix?

Many answers talk about the time spent for initializing. But I don't think that was the question. Anyway, on modern processors, initializing such a small array takes just a few microseconds. And it is only done once, at program start.

If you need to fetch a sub-matrix from any position, there is probably no faster method than using a static 2D array. However, depending on processor architecture, accessing the array could be faster if the array dimensions (or just the last dimension) are power of 2 (e.g. 32, 64 etc.) since this would allow using shift instead of multiply.

If the accessed sub-matrices do not overlap (i.e. you would only access indexes 0, 3, 6 etc.) then using 3-dimensional or 4-dimensional array could speed up the access

  int  map[11][11][3][3];

This makes each sub-matrix a contiguous block of memory, which can be copied with a single block copy command. Further, it may fit in single cache line.