Why is one faster than the other?

This is a discussion on Why is one faster than the other? within the C Programming forums, part of the General Programming Boards category; Code: #include <stdio.h> #define IMGX 8192 #define IMGY 8192 int red_freq[256]; char img[IMGY][IMGX][3]; main () { int i, j; long ...

  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,793
    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
    602
    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
    21,310
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

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

    optimization Loop Interchanging - Google Search
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  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, 12:18 PM
  3. Computations - which is faster?
    By ulillillia in forum C Programming
    Replies: 9
    Last Post: 12-09-2006, 09: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, 10:34 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21