Why Does This Improve Performance?

Question

I've two for loops that basically look up in two different arrays (each having a size around 2-4k at peak) and set a value in a 3rd array based on these values. For some weird reason there is a factor two difference between the performance of this piece of code depending on in which order I put the two for loops.

This is the first setup. It executes in ~150 milliseconds on my PC:

public static int[] SchoolMultiplication(int[] a, int[] b, int numberBase)
{
    List<double> times = new List<double>();
    TimeTest timeTest = new TimeTest();

    int aLen = a.Length;
    int bLen = b.Length;

    int[,] resultMatrix = new int[a.Length + b.Length, aLen];
    int[] result = new int[a.Length + b.Length];

    timeTest.Start();

    for (int horizontalIndex = 0; horizontalIndex < b.Length; horizontalIndex++)
    {
     for (int verticalIndex = 0; verticalIndex < a.Length; verticalIndex++)

     {
      resultMatrix[a.Length + b.Length - 1 - verticalIndex - horizontalIndex, verticalIndex] = a[a.Length - verticalIndex - 1] * b[b.Length - horizontalIndex - 1];
     }
    }

Now if I change nothing but the order of the loops like this

for (int verticalIndex = 0; verticalIndex < a.Length; verticalIndex++)
{
    for (int horizontalIndex = 0; horizontalIndex < b.Length; horizontalIndex++)
 {
  resultMatrix[a.Length + b.Length - 1 - verticalIndex - horizontalIndex, verticalIndex] = a[a.Length - verticalIndex - 1] * b[b.Length - horizontalIndex - 1];
 }
}

The total running time of the method drops to about ~400 milliseconds. How does a simple exchange of loop order improve performance by almost 300%? I suppose it is some kind of caching or pointer performance thing?

Answer 1

It is very likely related to the cache hits/misses. The difference lies in sequential vs scattered access that lies in size above the size of one cache line.

For plain c++ loops, it would also help to make the loops backwards to gain a bit of performance on the loop. Not sure how it fits for .NET.

Answer 2

Locality, locality, locality of data. From Wikipedia (which says it better than I would have):

Linear data structures: Locality often occurs because code contains loops that tend to reference arrays or other data structures by indices. Sequential locality, a special case of spatial locality, occurs when relevant data elements are arranged and accessed linearly. For example, the simple traversal of elements in a one-dimensional array, from the base address to the highest element would exploit the sequential locality of the array in memory.[2] The more general equidistant locality occurs when the linear traversal is over a longer area of adjacent data structures having identical structure and size, and in addition to this, not the whole structures are in access, but only the mutually corresponding same elements of the structures. This is the case when a matrix is represented as a sequential matrix of rows and the requirement is to access a single column of the matrix.

Answer 3

I remember reading about this in Code Complete. In most languages, arrays are set up with the last index set up sequentially, so you're accessing bytes directly in a row when iterating over last index, instead of skipping around when iterating over the first.

Answer 4

Your intuition is right, it is a caching issue. @Mike Daniels post to question below is essentially describing the exact same issue. The second bit of code will get far more cache hits.

http://stackoverflow.com/questions/997212/fastest-way-to-loop-through-a-2d-array

But, shhhh we're not supposed to care about performance right? :)

Answer 5

I would also think that the relative sizes of arrays a and b would make a difference.

If a.length is large and b.length is small, the second option should be faster. Conversely, if a.length is small and b.length is large, the first option would be faster. The issue is avoiding the setup/teardown cost of the inner loop.

BTW, why do you have

int aLen = a.Length;

But then also call a.Length directly? Seems like you should choose one or the other.