Thread: Iterating through a multidimensional array

  1. #1
    Kung Fu Kitty Angus's Avatar
    Join Date
    Oct 2008
    Location
    Montreal, Canada
    Posts
    115

    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.
    Last edited by Angus; 05-27-2009 at 11:21 AM. Reason: added something at the end

  2. #2
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    Code:
    atype *p = array[0];

  3. #3
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    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!
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  4. #4
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Angus View Post
    (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.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  5. #5
    Kung Fu Kitty Angus's Avatar
    Join Date
    Oct 2008
    Location
    Montreal, Canada
    Posts
    115
    I see. I thought a const atype [][] would cast well to a const atype **, but I guess that was wrong. Ok, thanks.

  6. #6
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    Quote Originally Posted by Angus View Post
    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.

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by Angus View Post
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by Angus View Post
    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 Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  9. #9
    Kung Fu Kitty Angus's Avatar
    Join Date
    Oct 2008
    Location
    Montreal, Canada
    Posts
    115
    Quote Originally Posted by iMalc View Post
    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.

  10. #10
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by Angus View Post
    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.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  11. #11
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by brewbuck View Post
    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?
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  12. #12
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by MK27 View Post
    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.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  13. #13
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    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]
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  14. #14
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    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
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  15. #15
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    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.
    Last edited by dwks; 05-27-2009 at 05:06 PM.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help -- allocating memory in a multidimensional array
    By jonathan.plumb in forum C Programming
    Replies: 10
    Last Post: 05-20-2009, 11:04 PM
  2. Pointer to multidimensional array
    By ejohns85 in forum C++ Programming
    Replies: 4
    Last Post: 03-24-2009, 11:17 AM
  3. Creating a Spreadsheet using a multidimensional array
    By Apiatan in forum C++ Programming
    Replies: 1
    Last Post: 03-21-2009, 04:18 PM
  4. Type and nontype parameters w/overloading
    By Mr_LJ in forum C++ Programming
    Replies: 3
    Last Post: 01-02-2004, 01:01 AM
  5. Help with an Array
    By omalleys in forum C Programming
    Replies: 1
    Last Post: 07-01-2002, 08:31 AM

Tags for this Thread