Why does the order of the loops affect performance when iterating over a 2D array?

by

As others have said, the issue is the store to the memory location in the array: x[i][j]. Here’s a bit of insight why:

You have a 2-dimensional array, but memory in the computer is inherently 1-dimensional. So while you imagine your array like this:

0,0 | 0,1 | 0,2 | 0,3
----+-----+-----+----
1,0 | 1,1 | 1,2 | 1,3
----+-----+-----+----
2,0 | 2,1 | 2,2 | 2,3

Your computer stores it in memory as a single line:

0,0 | 0,1 | 0,2 | 0,3 | 1,0 | 1,1 | 1,2 | 1,3 | 2,0 | 2,1 | 2,2 | 2,3

In the 2nd example, you access the array by looping over the 2nd number first, i.e.:

x[0][0] 
        x[0][1]
                x[0][2]
                        x[0][3]
                                x[1][0] etc...

Meaning that you’re hitting them all in order. Now look at the 1st version. You’re doing:

x[0][0]
                                x[1][0]
                                                                x[2][0]
        x[0][1]
                                        x[1][1] etc...

Because of the way C laid out the 2-d array in memory, you’re asking it to jump all over the place. But now for the kicker: Why does this matter? All memory accesses are the same, right?

No: because of caches. Data from your memory gets brought over to the CPU in little chunks (called ‘cache lines’), typically 64 bytes. If you have 4-byte integers, that means you’re geting 16 consecutive integers in a neat little bundle. It’s actually fairly slow to fetch these chunks of memory; your CPU can do a lot of work in the time it takes for a single cache line to load.

Now look back at the order of accesses: The second example is (1) grabbing a chunk of 16 ints, (2) modifying all of them, (3) repeat 4000*4000/16 times. That’s nice and fast, and the CPU always has something to work on.

The first example is (1) grab a chunk of 16 ints, (2) modify only one of them, (3) repeat 4000*4000 times. That’s going to require 16 times the number of “fetches” from memory. Your CPU will actually have to spend time sitting around waiting for that memory to show up, and while it’s sitting around you’re wasting valuable time.

Important Note:

Now that you have the answer, here’s an interesting note: there’s no inherent reason that your second example has to be the fast one. For instance, in Fortran, the first example would be fast and the second one slow. That’s because instead of expanding things out into conceptual “rows” like C does, Fortran expands into “columns”, i.e.:

0,0 | 1,0 | 2,0 | 0,1 | 1,1 | 2,1 | 0,2 | 1,2 | 2,2 | 0,3 | 1,3 | 2,3

The layout of C is called ‘row-major’ and Fortran’s is called ‘column-major’. As you can see, it’s very important to know whether your programming language is row-major or column-major! Here’s a link for more info: http://en.wikipedia.org/wiki/Row-major_order

More Related Contents:

  1. optimized sum of an array of doubles in C [duplicate]
  2. Which ordering of nested loops for iterating over a 2D array is more efficient [duplicate]
  3. Improve INSERT-per-second performance of SQLite
  4. Is there a performance difference between i++ and ++i in C?
  5. Is it safe to read past the end of a buffer within the same page on x86 and x64?
  6. clflush to invalidate cache line via C function
  7. Efficient 4×4 matrix vector multiplication with SSE: horizontal add and dot product – what’s the point?
  8. Cache size estimation on your system?
  9. Why is memcmp so much faster than a for loop check?
  10. How does the CPU cache affect the performance of a C program
  11. C for loop indexing: is forward-indexing faster in new CPUs?
  12. Faster approach to checking for an all-zero buffer in C?
  13. Inline function v. Macro in C — What’s the Overhead (Memory/Speed)?
  14. C: Why is counter not resetting to 0 in for loop [closed]
  15. Why is transposing a matrix of 512×512 much slower than transposing a matrix of 513×513?
  16. How to write a large buffer into a binary file in C++, fast?
  17. Is it better to use std::memcpy() or std::copy() in terms to performance?
  18. Rounding up to next power of 2
  19. Does C# optimize the concatenation of string literals?
  20. Loop with function call faster than an empty loop
  21. How to do unsigned saturating addition in C?
  22. What does a ‘for’ loop without curly braces do?
  23. faster equivalent of gettimeofday
  24. Why doesn’t GCC optimize structs?
  25. How to determine if memory is aligned?
  26. Algorithm to find all the exact divisors of a given integer
  27. Which is better way to calculate nCr
  28. Which is faster/preferred: memset or for loop to zero out an array of doubles?
  29. Produce loops without cmp instruction in GCC
  30. Bit popcount for large buffer, with Core 2 CPU (SSSE3)

Leave a Comment