2D Dynamic Array in C: Which of those 3 snippets gets executed faster?

gprof is not working properly on my system (MinGW) so I'd like to know which one of the following snippets is more efficient, on average.

I'm aware that internally C compilers convert everything into pointers arithmetic, but nevertheless I'd like to know if any of the following snippets has any significant advantage over the others.

The array has been allocated dynamically in contiguous memory as 1d array and may be re-allocated at run time (its for a simple board game, in which the player is allowed to re-define the board's size, as often as he wants to).

Please note that i & j must get calculated and passed into the function set_cell() in every loop iteration (gridType is a simple struct with a few ints and a pointer to another cell struct).

Thanks in advance!

Allocate memory

grid = calloc( (nrows * ncols), sizeof(gridType) );

Snippet #1 (parse sequentially as 1D)

gridType *gp = grid;
register int i=0 ,j=0;      // we need to pass those in set_cell()

if ( !grid )
return;

for (gp=grid; gp < grid+(nrows*ncols); gp++)
{
    set_cell( gp, i,开发者_StackOverflow社区 j, !G_OPENED, !G_FOUND, value, NULL );

    if (j == ncols-1) {     // last col of current row has been reached
        j=0;
        i++;
    }
    else                    // last col of current row has NOT been reached
        j++;
}

Snippet #2 (parse as 2D array, using pointers only)

gridType *gp1, *gp2;

if ( !grid )
    return;

for (gp1=grid; gp1 < grid+nrows; gp1+=ncols)
    for (gp2=gp1; gp2 < gp1+ncols; gp2++)
        set_cell( gp2, (gp1-grid), (gp2-gp1), !G_OPENED, !G_FOUND, value, NULL );

Snippet #3 (parse as 2D, using counters only)

register int i,j;           // we need to pass those in set_cell()

for (i=0; i<nrows; i++)
    for (j=0; j<ncols; j++)
        set_cell( &grid[i * ncols + j], i, j, !G_OPENED, !G_FOUND, value, NULL);

Free memory

free( grid );

EDIT: I fixed #2 form gp1++) to gp1+=ncols), in the 1st loop, after Paul's correction (thx!)

---

For anything like this, the answer is going to depend on the compiler and the machine you're running it on. You could try each of your code snippets, and calculating how long each one takes.

However, this is a prime example of premature optimization. The best thing to do is to pick the snippet which looks the clearest and most maintainable. You'll get much more benefit from doing that in the long run than from any savings you'd make from choosing the one that's fastest on your machine (which might not be fastest on someone else's anyway!)

---

Well, snippet 2 doesn't exactly work. You need different incrementing behavior; the outer loop should read for (gp1 = grid; gp1 < grid + (nrows * ncols); gp1 += ncols).

Of the other two, any compiler that's paying attention will almost certainly convert snippet 3 into something equivalent to snippet 1. But really, there's no way to know without profiling them.

Also, remember the words of Knuth: "Premature optimization is the ROOT OF ALL EVIL. I have seen more damage done in the name of 'optimization' than for all other causes combined, including sheer, wrongheaded stupidity." People who write compilers are smarter than you (unless you're secretly Knuth or Hofstadter), so let the compiler do its job and you can get on with yours. Trying to write "clever" optimized code will usually just confuse the compiler, preventing it from writing even better, more optimized code.

---

This is the way I'd write it. IMHO it's shorter, clearer and simpler than any of your ways.

int i, j;
gridType *gp = grid;

for (i = 0; i < nrows; i++)
    for (j = 0; j < ncols; j++)
        set_cell( gp++, i, j, !G_OPENED, !G_FOUND, value, NULL );

---

1. gprof not working isn't a real excuse. You can still set up a benchmark and measure execution time.
2. You might not be able to measure any difference on modern CPUs until nrows*ncols is getting very large or the reallocation happens very often, so you might optimize the wrong part of your code.
3. This certainly is micro-optimization as the most runtime will most probably be spent in set_cell and everything else could be optimized to the same or very similar code by the compiler.

---

You don't know until you measure it.

Any decent compiler may produce the same code, even if it doesn't the effects of caching, pilelining, predictive branching and other clever stuff means that simply guessing the number of instructions isn't enough