# Iterating through a multidimensional array

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 05-27-2009
Angus
Iterating through a multidimensional array
As everyone knows this
Code:

```        atype array[4] = {1, 2, 3, 4};         atype *p = array;         for (int i = 0; i < 4; i++) {                 OperateOn(*p);                 p++;         }```
is more efficient than this
Code:

```        atype array[4] = {1, 2, 3, 4};         for (int i = 0; i < 4; i++) {                 OperateOn(array[i]);         }```
(except for those of you who don't know, dereferencing an array can amount to a multiplication operation and an addition operation, while the first solution just does an increment)

But what if you have
Code:

`        atype array[4][4] = { {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16} };`
how do you go about iterating through that without using the square brackets? I tried
Code:

```        const atype **arrayy = (const atype **)array;         const atype *arrayx = *array;```
But my first dereference of arrayx won me a seg fault. And arrayy was a sober-looking 0x7fffffffdb90 while arrayx was 0x200000001. No points for guessing where the "2" and the "1" of that come from. I just don't see how.
• 05-27-2009
itCbitC
Code:

`atype *p = array[0];`
• 05-27-2009
Sebastiani
Quote:

const atype **arrayy = (const atype **)array;
const atype *arrayx = *array;
That doesn't work simply because 'array' is not an array of pointers. That is, the address of 'array' is the actual starting address of 16 contigious elements of type 'atype'. The solution is deceptively simple:

Code:

```atype array[4][4] = { {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16} }; atype* ptr = (atype*)array, * end = ptr + 16; while (ptr != end) {     OperateOn(*ptr++); }```
Note that this works for 'flat' arrays of any dimension!
• 05-27-2009
MK27
Quote:

Originally Posted by Angus
(except for those of you who don't know, dereferencing an array can amount to a multiplication operation and an addition operation, while the first solution just does an increment)

I didn't know that, thanks. I would not have regarded array[i] as dereferencing, either.
• 05-27-2009
Angus
I see. I thought a const atype [][] would cast well to a const atype **, but I guess that was wrong. Ok, thanks.
• 05-27-2009
itCbitC
Quote:

Originally Posted by Angus
I see. I thought a const atype [][] would cast well to a const atype **, but I guess that was wrong. Ok, thanks.

Nope, it won't because by itself array is a pointer to a 4 item array of atypes instead of being a pointer to pointer to atype.
• 05-27-2009
iMalc
Quote:

Originally Posted by Angus
As everyone knows this
Code:

```        atype array[4] = {1, 2, 3, 4};         atype *p = array;         for (int i = 0; i < 4; i++) {                 OperateOn(*p);                 p++;         }```
is more efficient than this
Code:

```        atype array[4] = {1, 2, 3, 4};         for (int i = 0; i < 4; i++) {                 OperateOn(array[i]);         }```
(except for those of you who don't know, dereferencing an array can amount to a multiplication operation and an addition operation, while the first solution just does an increment)

Not necessarily, it depends on the platform and CPU. The first one can have more aliasing issues, and the second one may involve generating certain CISC instructions that do the whole array lookup in one instruction anyway.
I've been through threads before that indicate that it certainly is not as clear-cut as you make it out to be.
• 05-27-2009
Elysia
Quote:

Originally Posted by Angus
As everyone knows this
Code:

```        atype array[4] = {1, 2, 3, 4};         atype *p = array;         for (int i = 0; i < 4; i++) {                 OperateOn(*p);                 p++;         }```
is more efficient than this
Code:

```        atype array[4] = {1, 2, 3, 4};         for (int i = 0; i < 4; i++) {                 OperateOn(array[i]);         }```
(except for those of you who don't know, dereferencing an array can amount to a multiplication operation and an addition operation, while the first solution just does an increment)

You would be amazed at how easily the compiler optimizes the second piece of code, making it not "less efficient."
• 05-27-2009
Angus
Quote:

Originally Posted by iMalc
Not necessarily, it depends on the platform and CPU. The first one can have more aliasing issues, and the second one may involve generating certain CISC instructions that do the whole array lookup in one instruction anyway.
I've been through threads before that indicate that it certainly is not as clear-cut as you make it out to be.

Perhaps I should have said not less efficient than instead of more efficient than. I'd be surprised if there was a CPU out there that can perform a multiplication and addition faster than an increment. At any rate, it certainly is a popular measure to take.
• 05-27-2009
brewbuck
Quote:

Originally Posted by Angus
Perhaps I should have said not less efficient than instead of more efficient than. I'd be surprised if there was a CPU out there that can perform a multiplication and addition faster than an increment. At any rate, it certainly is a popular measure to take.

Induction variable detection and loop index strength reduction have been known since... I don't know, the 1960s?

Determining that the second loop can be rewritten as the first loop is one of the more trivial things the compiler is able to do.
• 05-27-2009
MK27
Quote:

Originally Posted by brewbuck
Determining that the second loop can be rewritten as the first loop is one of the more trivial things the compiler is able to do.

Does that me I just wasted my afternoon going through all my important code performing a non-existent optimization?
• 05-27-2009
brewbuck
Quote:

Originally Posted by MK27
Does that me I just wasted my afternoon going through all my important code performing a non-existent optimization?

Well, you never know exactly which optimizations the compiler will perform, but this is definitely one of the simpler ones.
• 05-27-2009
dwks
Probably. :)

I did a test. Attached are the results.
Code:

```\$ cat flat.c #include <stdio.h> int main() {     int array[] = {1, 2, 3, 4, 5};     int *end = array + sizeof(array)/sizeof(*array);     int *p;     for(p = array; p != end; p ++) {         printf("%d\n", *p);     }     return 0; } \$ cat normal.c #include <stdio.h> int main() {     int array[] = {1, 2, 3, 4, 5};     size_t x;     for(x = 0; x < sizeof(array)/sizeof(*array); x ++) {         printf("%d\n", array[x]);     }     return 0; } \$ gcc -O2 -S flat.c \$ gcc -O2 -S normal.c \$ gcc flat.c -o flat \$ gcc normal.c -o normal \$ ./flat 1 2 3 4 5 \$ ./normal 1 2 3 4 5 \$ diff flat.s normal.s 1c1 <      .file  "flat.c" --- >      .file  "normal.c" 16a17 >      xorl    %ebx, %ebx 19c20 <      leal    -28(%ebp), %ebx --- >      leal    -32(%ebp), %esi 21d21 <      leal    -8(%ebp), %esi 28,29c28,29 <      movl    -4(%ebx), %eax <      addl    \$4, %ebx --- >      movl    (%esi,%ebx,4), %eax >      addl    \$1, %ebx 33c33 <      cmpl    %esi, %ebx --- >      cmpl    \$5, %ebx \$```
(-O2 tells gcc to optimize, -S tells it to generate .s [assembly] files instead of compiling fully.)

As you can see, the generated assembly code is virtually identical. The compiler's just using slightly different registers, more or less. (Also, one version has an xorl and the other a leal, but these instructions probably execute in the same amount of time.)

Optimizations like unrolling loops, using pointers instead of arrays, writing a complex expression instead of using a temporary, usually aren't worth it these days.

 BTW, the graphical diff output is from kompare, and this system is a 32-bit i386 Linux running gcc 4.1.2. [/edit]
• 05-27-2009
MK27
Wow dwks, I'm impressed.

It's just as well I actually went jogging then, and can continue to enjoy

Code:

`array[i]`
ps. nice avatar ;P
• 05-27-2009
dwks
I'm glad you're impressed, and gladder still you like our avatar. As long as you keep in mind who originally made it, laboriously and by hand, in the Gimp. Yes, I calculated the exact angles I'd need to rotate the image in, the corresponding X and Y offsets, and did it all by hand. (Well, I probably calculated the angles with a program, but still.)

Then a few months later I made an SDL program to do it automatically. It was smoother and everything (originally I was limited to integral angles, whereas the SDL program wasn't), but I never got around to uploading it. My jerky swirl has character. :)
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last