Why is my program slow when looping over exactly 8192 elements?

by

The difference is caused by the same super-alignment issue from the following related questions:

But that’s only because there’s one other problem with the code.

Starting from the original loop:

for(i=1;i<SIZE-1;i++) 
    for(j=1;j<SIZE-1;j++) {
        res[j][i]=0;
        for(k=-1;k<2;k++) 
            for(l=-1;l<2;l++) 
                res[j][i] += img[j+l][i+k];
        res[j][i] /= 9;
}

First notice that the two inner loops are trivial. They can be unrolled as follows:

for(i=1;i<SIZE-1;i++) {
    for(j=1;j<SIZE-1;j++) {
        res[j][i]=0;
        res[j][i] += img[j-1][i-1];
        res[j][i] += img[j  ][i-1];
        res[j][i] += img[j+1][i-1];
        res[j][i] += img[j-1][i  ];
        res[j][i] += img[j  ][i  ];
        res[j][i] += img[j+1][i  ];
        res[j][i] += img[j-1][i+1];
        res[j][i] += img[j  ][i+1];
        res[j][i] += img[j+1][i+1];
        res[j][i] /= 9;
    }
}

So that leaves the two outer-loops that we’re interested in.

Now we can see the problem is the same in this question: Why does the order of the loops affect performance when iterating over a 2D array?

You are iterating the matrix column-wise instead of row-wise.

To solve this problem, you should interchange the two loops.

for(j=1;j<SIZE-1;j++) {
    for(i=1;i<SIZE-1;i++) {
        res[j][i]=0;
        res[j][i] += img[j-1][i-1];
        res[j][i] += img[j  ][i-1];
        res[j][i] += img[j+1][i-1];
        res[j][i] += img[j-1][i  ];
        res[j][i] += img[j  ][i  ];
        res[j][i] += img[j+1][i  ];
        res[j][i] += img[j-1][i+1];
        res[j][i] += img[j  ][i+1];
        res[j][i] += img[j+1][i+1];
        res[j][i] /= 9;
    }
}

This eliminates all the non-sequential access completely so you no longer get random slow-downs on large powers-of-two.

Core i7 920 @ 3.5 GHz

Original code:

8191: 1.499 seconds
8192: 2.122 seconds
8193: 1.582 seconds

Interchanged Outer-Loops:

8191: 0.376 seconds
8192: 0.357 seconds
8193: 0.351 seconds

More Related Contents:

  1. Why does GCC generate 15-20% faster code if I optimize for size instead of speed?
  2. Using bts assembly instruction with gcc compiler
  3. Measuring exception handling overhead in C++
  4. Memory-efficient C++ strings (interning, ropes, copy-on-write, etc) [closed]
  5. How does #include work in C++? [duplicate]
  6. delete vs delete[] [duplicate]
  7. Replacing a 32-bit loop counter with 64-bit introduces crazy performance deviations with _mm_popcnt_u64 on Intel CPUs
  8. Global memory management in C++ in stack or heap?
  9. What does this GCC error “… relocation truncated to fit…” mean?
  10. Compiling a C++ program with GCC
  11. Why doesn’t delete set the pointer to NULL?
  12. Does MinGW-w64 support std::thread out of the box when using the Win32 threading model?
  13. Is there a reason to call delete in C++ when a program is exiting anyway?
  14. GCC style weak linking in Visual Studio?
  15. Is inline assembly language slower than native C++ code?
  16. GCC C++ “Hello World” program -> .exe is 500kb big when compiled on Windows. How can I reduce its size?
  17. Linking libstdc++ statically: any gotchas?
  18. 5 years later, is there something better than the “Fastest Possible C++ Delegates”?
  19. Linking g++ 4.8 to libstdc++
  20. Implementing a std::vector like container without undefined behavior
  21. c++11 regex slower than python
  22. GCC: Difference between -O3 and -Os
  23. Call destructor and then constructor (resetting an object)
  24. Memory allocation and deallocation across dll boundaries
  25. What is a good random number generator for a game?
  26. If a 32-bit integer overflows, can we use a 40-bit structure instead of a 64-bit long one?
  27. GCC std::thread not found in namespace std
  28. C++ most efficient way to convert string to int (faster than atoi)
  29. Where can I find an official reference listing the operation of SSE intrinsic functions?
  30. How much overhead can the -fPIC flag add?

Leave a Comment