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.

Code:

atype *p = array[0];

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!

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.

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

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.

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.

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."

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.

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.

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?

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.

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.

[edit] BTW, the graphical diff output is from kompare, and this system is a 32-bit i386 Linux running gcc 4.1.2. [/edit]

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

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. :)

Quote:

Originally Posted by 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.

I think there are more appropriate places to discuss this kind of thing, dwks.

Amazingly, I did this one manually in "The GIMP" as well. You should see what's still to come...well, I guess that'll be later.

Okay, I'll stop talking now.

Just one last note: GCC doesn't optimize as well on SPARC as it does on i386, but it still does the loop-access-to-pointer optimization. (I picked SPARC because I know it's tricky to optimize for.)

Anyway, talk to you later.

>> As you can see, the generated assembly code is virtually identical.

I'm actually suprised their so similar. Interesting.

>> ps. nice avatar ;P

Isn't there some unspoken rule against stealing non-animated animated avatars?

Quote:

Originally Posted by dwks

Just one last note: GCC doesn't optimize as well on SPARC as it does on i386, but it still does the loop-access-to-pointer optimization. (I picked SPARC because I know it's tricky to optimize for.)

Is that the Perforce diff tool?

Quote:

Originally Posted by brewbuck

Is that the Perforce diff tool?

dwks tells us it is "kompare" which I will hazard a guess that it's a KDE app. Being addicted to fvwm2*, I may have trouble getting that to work because of all the excessive integration (dbus, etc.) Which might be just as well, my little mind should stay away from looking too hard at the asm side of things.

So I'm happy to get the bottom line here from the pros.

*I've actually starting making coffee with a config script.

Quote:

Is that the Perforce diff tool?

As I said, it's kompare, which is indeed a really nice diff tool for KDE. (That's the KDE 3 version of it.) It's my favourite diff tool. :)

You may be addicted to fvwm2*, but just wait until KDE 4's KDevelop becomes stable, and try it (and khexedit and kompare and kdiff3). You may have to reconsider your addiction.