Loop interchange optimizations switch the order of inner and outer loops in nested loops in order to maximize cache locality. Automatically performing this task is difficult for compilers to do. In gcc, the -floop-interchange compiler flag exists but is currently not available by default. Therefore, it is a good idea for programmers to pay attention to how their code is accessing memory-composite data structures like arrays and matrices. As an example, let’s take a closer look at the matrixVectorMultiply() function in matrixVector.c.

The input and output matrices are dynamically allocated (second method discussed in C chapter). As a result, each row in the matrices are not contiguous to each other, while each element in every row are contiguous. The current ordering of the loops causes the program to cycle through each column instead of every row. Recall that data is loaded into cache in blocks not elements. As a result, when an element x in an array in either res or m is accessed, the elements adjacent to x are also loaded into cache. Cycling through every "column" of the matrix causes more cache misses, as the cache is forced to load new blocks with every access. Table 2 shows that adding optimization flags does not decrease the run-time of the function. However, simply switching the order of the loops (as shown above and in matrixVector2.c) makes the function nearly 8 times faster and allows the compiler to perform additional optimizations.

The Valgrind tool cachegrind (discussed in Chapter 11) is a great way to identify data locality issues, and reveals the cache access differences in the two versions of the matrixVectorMultiply() function shown above.

Re-running the improved program on 10,000 x 10,000 elements yields the following run-time numbers:

Now, matrix allocation and filling takes the most time. Additional timing reveals that it is the filling of the matrices that in fact takes the most time. Let’s take a closer look at that code:

To fill the input and output matrices, a for-loop cycles through all the rows, and calls the fillArrayRandom() and fillArrayZeros() functions on each matrix. In some scenarios, it may be advantageous for the compiler to split the single loop into two separate loops (known as loop fission), as shown in Table 3.

The process of taking two loops that operate over the same range and combining their contents into a single loop (i.e. the opposite of loop fission) is called loop fusion. Loop fission and fusion are examples of optimizations a compiler might perform to try and improve data locality. Compilers for multicore processors may also use loop fission or loop fusion to enable loops to execute efficiently on multiple cores. For example, a compiler may use loop fission to assign two loops to different cores. Likewise, a compiler may use loop fusion to combine together dependent operations into the body of the loop and distribute to each core a subset of the loop iterations (assuming data between iterations are independent).

In our case, applying loop fission manually does not directly improve program performance; there is virtually no change in the amount of time required to fill the array. However, it may make clear a more subtle optimization: the loop containing fillArrayZeros() is not necessary. The matrixVectorMultiply() assigns values to each element in the result array; a prior initialization to all zeroes is unnecessary.

Making the above change results in only a slight decrease in run-time. While it eliminates the step of filling in all elements in the result matrix with zeros, a significant time is still required to fill the input matrix with random numbers:

Even though each array is stored non-contiguously in memory, each array takes up 10,000 x sizeof(int) bytes, or 40,000 bytes. Since there is a total of 20,000 (10,000 each for the initial matrix and the result matrix) arrays allocated, this corresponds to 800 million bytes, or roughly 762 MB of space. Filling 762 MB with random numbers understandably takes a lot of time. With matrices, memory use increases quadratically with the input size, and can play a large role in performance.

Valgrind’s massif tool can help you profile memory use. Like the other Valgrind tools we covered in this book (memcheck, cachegrind, and callgrind), massif runs as a wrapper around a program’s executable. Specifically massif takes snapshots of program memory use throughout the program, and profiles how memory usage fluctuates. Programmers may find the massif tool useful for tracking how their programs use heap memory, and for identifying opportunities to improve memory use. Let’s run the massif tool on the matrixVector3 executable:

Running massif produces a massif.out.xxxx file, where xxxx is a unique id number. If you are typing along, type ls to reveal your corresponding massif file. In the example below, the corresponding file is massif.out.7030. Use the ms_print command to view the massif output:

At the top of the output is the memory use graph. The x-axis shows the number instructions executed. The y-axis shows memory use. The graph above indicates that a total of 9.778 billion (Gi) instructions executed during our run of matrixVector3. During execution, massif took a total of 80 snapshots to measure use on the heap. Memory use peaked in the last snapshot (79). Peak memory use for the program was 763.3 MB, and stayed relatively constant throughout the program.

Summaries of all the snapshots occur after the graph. For example, the table below corresponds to the snapshots around snapshot 79:

Each row corresponds to a particular snapshot, the time it was taken, the total heap memory consumption (in bytes) at that point, the number of bytes asked by the program ("useful-heap") at that point, the number of bytes allocated in excess of what the program asked for, and the size of the stack. By default, stack profiling is off (it slows massif down significantly). To enable stack profiling, use the --stacks=yes option when running massif.

The massif tool reveals that 99.96% of the program’s heap memory use occurred in the allocateArray() function, and that a total of 800 million bytes were allocated, consistent with the back-of-the-envelope calculation we performed above. Readers will likely find massif an useful to tool for identifying areas of high heap memory use in their programs, which often slows a program down. For example, memory leaks can occur in programs when programmers frequently call malloc() without calling free() at the first correct opportunity. The massif tool is incredibly useful for detecting such leaks.