Copyright 2013, Clinton A Staley
In this segment we'll use what we learned about cache architecture to explore strategies for optimizing code efficiency taking cache behavior into account.
Cachegrind tool (v)
Spatial contiguity (v)
We'll use the supplied CountInversions1.c test case as our study subject. There are four versions, each with progressively better cache performance. Look at only the first version for now; we'll have in-lecture questions to develop the other three.
As you can see from the source code, CountInversions1.c sets up a rather large testing type we'll call CacheHog. CacheHog has two TagName fields, each comprising a long tag and a character array. The arrays are mostly there to fill space; they stand in for what might be more complex other fields in a realistic type.
The code fills in simple test values for nm1.tag and nm2.tag, as you can see on lines 25 and 26. The nm1.tag values are in descending order, and the nm2.tag values are in ascending order. The loop on lines 29-35 then tests both tags for inversions – pairs of tags where the tag earlier in the array is larger than the one later in the array. Such inversions are an indication of how "unsorted" a sequence is. Given the test values created on lines 25 and 26, we'd expect no inversions for nm2.tag, which is in sorted order, and we'd expect the maximum number for nm1.tag, which is in reverse order.
Counting inversions has some relevance to algorithmic research, but here it's just a simple task that has one important characteristic: it compares all pairs of CacheHogs. General pair-comparison is a common code pattern, and it illustrates some important principles of cache optimization.
I'll run CountInversions on a test server here, entering 10000 for the number of CacheHogs. We can see it's taking around 6.7 seconds to work on an array of that size.
Now let's profile the code to see how it's interacting with the cache. There are a number of tools for cache-profiling; we'll use cachegrind, which is a subtool in the valgrind suite, which suite you have encountered in a prior module/course. We run cachegrind on an executable, say CountInversions1, thus:
valgrind -–tool=cachegrind ./CountInversions1
You actually run valgrind, with an option to invoke the cachegrind subtool. After a banner announcement, we can run the program as though it were executing normally on the commandline. We'll enter 10000 again and....
One of the first things we'll notice is that it's taking a lot longer than the 7 second nonprofiled test run. That's because cachegrind emulates the execution of the program, simulating CPU and cache behavior rather than running the machine language directly. This lets it track cache behavior as part of the emulation. You get really nice cache data that is not necessarily obtainable directly from the hardware, but at the cost of long test runs.
Cachegrind produces a file cachegrind.xxxxx where the xxxxx is a number that varies for each run. It also outputs an immediate summary of cache results, which summary will be repeated in the file. We'll talk more about the summary in a bit, but we can see that we have a pretty hefty cache miss rate right off the bat – look at that 39.6%.
Let's get the full details from the output file. You can look directly at the cachegrind.xxxxx file, but the utility cg_annotate produces a more readable digest of it, with source lines (provided you compiled with -g) listed alongside a per-sourceline table of cache statistics. You need a wide screen to look at it, but it's very complete. Just run cg_annotate with the cachegrind output and the executable as commandline arguments, along with a –auto=yes to cause source lines to be added:
cg_annotate cachegrind.xxxxx ./CountInversions1 --auto=yes
The result for our first profile run is shown here, and in the attached CacheGrind1.txt. It starts with a header giving details of our cache architecture. From it you can see we have 16K of L1 instruction cache, and 8K of L1 data cache (labelled I1 for instructions and D1 for data). The instruction cache has 32 byte cache lines, and is 8-way associative. The data cache has 64 byte cache lines, and is 4-way associative. LL (last level) cache, which is simply L2 cache in our case, is much larger, but has the same cache line size.
The 9 columns give statistics for instruction cache reads, data cache reads, and data cache writes, with source lines to which the statistics apply, to the right. (There are no instruction cache writes for obvious reasons – code is readonly in modern architectures)
Each three-column set shows the number of accesses (reads or writes) of the cache in question in the leftmost column, the number of top level cache misses in the middle column, and the number of second and lower level (IL and DL) cache misses in the right column.
The concept of a cache miss is central to optimizing for cache. A cache miss occurs when a desired datum is not in cache, and the relevant cache line must be read from RAM, or from a lower level cache. Obviously you have to have some cache misses or there'd be no data in the cache at all, but given the much slower speed of the lower-level memory, too many cache misses can seriously slow a program. This is especially true for misses in the L1 caches (I1 and D1 cache in cachegrind terms). Optimizing cache use involves using data while it's in cache, and not having to load it repeatedly to cache.
Let's start by looking at the first three columns -- those for instruction cache. Right off we can see that there are very few cache misses, and this makes sense, since we have a relatively small program that fits easily, in its entirety, in I1 cache. Still, there are a few interesting points here worth asking about.
The widely varying numbers in the leftmost Ir column tell you something interesting about the lines to which they apply. Why do they vary so much, and what does that indicate?
Nothing surprising here. All I1 reads come from the CPU advancing through the program and reading instructions from cache. Those numbers simply show the number of times each line is executed, times the number of instructions fetched per line.
That's a bit different from execution time, of course, since instructions don't all take the same amount of time. But it's a good proxy for a line-by-line execution time profile. We can see, for instance, that the line to increment the count of inversions in the nm2.tag fields is never run, since there are no inversions in that field.
Why do some lines show instruction cache misses, ranging from 1 to 3, while others show none? How can that be? (Think about the 32 byte instruction cache lines.)
An instruction cache miss will bring in a full 32 byte cache line, which may well include several machine instructions. So, depending on the number of machine instructions per code line, the instructions for the next one or two lines may be automatically loaded by a cache miss from the lines above, leaving the later one or two lines with no cache misses.
A line with more than 32 bytes worth of instructions will span two cache lines and a shorter one might too, depending on the alignment of instructions on cache line boundaries. Plus, if the line is a for-loop header, the incrementer is down at the bottom of the loop, despite being written at the top, and thus may be in an entirely different cache line. Thus the 3 cache misses for the line 24 loop header.
In another program, we might need to do some code reorganization to improve cache use, but this program appears to have no problems. Let's move on to the data cache.
There are a couple of points worth discussing in the data cache stats, including the obvious pain point for optimization.
Why are there 10,000 cache writes, apparently all of them misses (writes to data not present in cache) in the body lines of the line 24-27 loop? Are they something we should try to optimize? How much do they slow the program?
They're writing the contents of the tag fields, of course, and while each is a cache miss (those fields are not in the cache till written) the write-through to RAM can continue without stopping the CPU, unlike a read cache miss. So we don't need to worry about them.
Just out of curiosity, why are there no read cache misses on lines 25 and 26? Apparently there are 40,000 reads from cache for each, but no need at all to draw from RAM? Indeed, there are no read cache misses at all up to and including that loop. How is that possible?
If you look closely at what data those lines need, they require vals, numHogs, and i, all of which were put into cache on preceding lines, and are now in cache for the duration of the loop. And they never needed to be loaded from RAM, either, because they were written on the lines above, before ever being read.
That's exactly how cache is supposed to function. The main RAM sees nothing from this code but writes of those three variables, and then a bunch of tag values, and the CPU doesn't need to wait for anything since it reads what it just wrote, straight out of cache, and doesn't wait for the write-throughs to RAM, which are done on the side by the hardware.
So there's no optimization to be had in this first loop. But, the nested loop is a different story. The line 31 and 33 if-statements each are missing cache about 1/6 of the time (50 million misses each, out of 300 million reads). That's gotta be hurting performance. Let's see what we can do about it, starting by cutting the number of misses in half.
Why are both lines missing cache? They're accessing the same CacheHogs, at the same time. Wouldn't the first line's cache miss load up the cache for the benefit of the second line?
They would, if a CacheHog fit in a 64 byte cache line, but at 1024 bytes, a CacheHog requires 16 cache lines. Only the first of these would be loaded by accessing nm1.tag. Grabbing nm2.tag will require another cache line to be loaded.
And, note, even if the CPU anticipates that we'll access memory in sequence, and preloads the next cache line after the most recently loaded one, it still won't help. The cache line holding nm2.tag is 7 cache lines past the one holding nm1.tag.
So, how do we arrange for the nm1.tag cache miss to serve the nm2.tag access as well? Feel free to redesign CacheHog for this.
As the hint obviously suggests, we need to move the two tags together, so that they are both at the start of CacheHog. This requires breaking the nice nested data structure with the two TagNames, and just jamming all four fields (two tags and two names) into CacheHog directly, as we do in CountInversions2.c.
A cachegrind run (output given in CountInversions2.txt) shows that we've now eliminated all cache misses for the second if-statement. And, a timed run of the app shows a drop from 7s to just under 4s, a nearly 50% improvement, simply by shifting the order of a couple of data items. Also, it's very interesting that eliminating half the cache misses has cut the time by around 3s. It's reasonable to estimate that the other half of the misses are responsible for another 3s of runtime, and thus that around 6s out of the original 7s is due entirely to cache misses, with the underlying (admittedly simple) logic of the program accounting for at most 1s. Those other cache misses are looking like a good target for optimization.
Before we do that, however, let's summarize the lessons learned so far.
Cache Optimization Rule 1: Make frequently accessed data spatially contiguous or at least proximate.
Cache Optimization Rule 2: Access cache data in memory-order sequence, without gaps, so that precaching can reduce misses.
Keeping those tags together allowed one cache line to cover them. And even if they had fallen in two successive cache lines, any pre-loading on the part of the CPU would have reduced the misses on the second cache line, as long as there was not that huge 508 byte gap between them.
The unfortunate side-effect of this rule is that it often requires tearing apart neat data structures, as happened to the TagNames. This is a necessary evil of cache optimization in some cases.
In the next segment we'll do a more sophisticated set of optimizations to eliminate all but 2-3% of those remaining 50,000,000 cache misses.