Thread: Why is one faster than the other?

  1. #1
    Registered User
    Join Date
    Mar 2009
    Posts
    11

    Why is one faster than the other?

    Code:
    #include <stdio.h>
    
    #define IMGX 8192
    #define IMGY 8192
    
    int red_freq[256];
    char img[IMGY][IMGX][3];
    
    main () {
      int i, j;
      long long total;
      long long redness;
    
      for (i = 0; i < 256; i++) 
        red_freq[i] = 0;
    
      for (i = 0; i < IMGY; i++) 
        for (j = 0; j < IMGX; j++) 
          red_freq[img[i][j][0]] += 1;
    
      total = 0;
      for (i = 0; i < 256; i++) 
        total += (long long)i * (long long)red_freq[i];
    
      redness = (total + (IMGX*IMGY/2))/(IMGX*IMGY);
    
      printf("The average redness of the image is %lld.\n", redness);
    }
    versus the same, but with the loops nested the other way

    Code:
    for (j = 0; j < IMGX; j++) 
        for (i = 0; i < IMGY; i++) 
          red_freq[img[i][j][0]] += 1;
    When executing, the first one is faster than the second, but I don't understand why. Any thoughts?

  2. #2
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    The way data is stored in memory and the differences between row-major and column-major access of that data?
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  3. #3
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    603
    For starters you are populating your 3D array much differently. Also is this slownes consistently reproduced? Also if you are familiar with strace and or looking over assembly language, this may give better clues. My think of using gdb as well.

    try using 'gcc -S' option to print out your .s file to view the asm code and note if there are drastic differences between your code changes.


    Knowing of such tools will greatly point you in the right direction to pindown and inefficiencies in the code

  4. #4
    Registered User
    Join Date
    Mar 2009
    Posts
    11
    what do you mean by "you're populating your 3d array much differently"? am i just not understanding some concept here?

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    You might want to consider hk_mp5kpdw's idea, e.g., you can get more cache misses when you access data contrary to how it is laid out in memory.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    look at the google results for loop optimization

    optimization Loop Interchanging - Google Search
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  7. #7
    Registered User
    Join Date
    Mar 2009
    Posts
    11
    thanks guys, I just worked it out!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Faster bitwise operator
    By Yarin in forum C++ Programming
    Replies: 18
    Last Post: 04-29-2009, 01:56 PM
  2. Faster way of printing to the screen
    By cacophonix in forum C Programming
    Replies: 16
    Last Post: 02-04-2009, 01:18 PM
  3. Computations - which is faster?
    By ulillillia in forum C Programming
    Replies: 9
    Last Post: 12-09-2006, 10:23 PM
  4. does const make functions faster?
    By MathFan in forum C++ Programming
    Replies: 7
    Last Post: 04-25-2005, 09:03 AM
  5. Floating point faster than fixed-point
    By VirtualAce in forum A Brief History of Cprogramming.com
    Replies: 5
    Last Post: 11-08-2001, 11:34 PM