How misaligning data can increase performance 12x by reducing cache misses
1–10 of 31 posts
Re: How misaligning data can increase performance 12x by reducing cache misses
#2It's important to at least know about the n in n-way set associative cache (i.e. that it exists) and this article is a good reminder. Next time you see data accesses that ought to be fast (ought to be hot in cache) but seem not to be, this is another thing you can look for.
It's easy, from a software engineer perspective, to know that your CPU has cache, and just think it's like any other cache you might implement in software. But the implementation details - the hashing by masking the address, and only having a few slots available for things that hash to the same bucket - are actually important, as shown here.
Re: How misaligning data can increase performance 12x by reducing cache misses
#3Interesting. One question. How would I take advantage of this ? Are there special flags for the compiler or special memory allocator that I would need ? Do libraries like BLAS already account for this ?
Re: How misaligning data can increase performance 12x by reducing cache misses
#4Can someone explain those charts?
Re: How misaligning data can increase performance 12x by reducing cache misses
#5Interesting. One question. How would I take advantage of this ? Are there special flags for the compiler or special memory allocator that I would need ? Do libraries like BLAS already account for this ?
I'm not aware of any flags of C compilers that would "fix potential cache-slot-collisions" for you automatically, neither of any allocators. Intel processors have some profiling registers that can point you to this kind of problems, but typically you first have to know what you want to profile.
Compilers are actually built to align the structures you write as there are a lot of processors which have significantly slower access to the misaligned values. Allocators also have to return you aligned addresses for each "malloc." The newest Intel iX processors are actually an exception in being able to amortize misaligned accesses.
I've actually used hand-made unaligned "string" stores. As soon as you allocate some bigger memory block and store the character sequences of the variable size one after another, their starts won't be aligned unless you want that. For doubles and other fixed-size values it's still better to keep them aligned.
Moreover I wasn't able to extract some value out of the article. Something constructed can be constructed to be slow or fast, fine. But I don't see anything that would inspire me to improve my real code. Maybe somebody who reads the article manages to produce such examples?
Re: How misaligning data can increase performance 12x by reducing cache misses
#6Can someone explain those charts?
The OP is plotting the ratio of page-aligned vs. unaligned access time against problem size. So, on the y-axis, a value of 2 means the page-aligned access took twice as long as the unaligned access.
Took me a few moments to grok the charts too, since I haven't had my coffee yet.
Re: How misaligning data can increase performance 12x by reducing cache misses
#7Interesting. One question. How would I take advantage of this ? Are there special flags for the compiler or special memory allocator that I would need ? Do libraries like BLAS already account for this ?
If you go through to the original discussion on comp.arch, there are some interesting ideas, including converting arrays of power-of-2 structures into structures of arrays if you're often walking them and not hitting all the fields every time.
Re: How misaligning data can increase performance 12x by reducing cache misses
#8Interesting. One question. How would I take advantage of this ? Are there special flags for the compiler or special memory allocator that I would need ? Do libraries like BLAS already account for this ?
I'm not aware of any flags of C compilers that would "fix potential cache-slot-collisions" for you automatically, neither of any allocators. Intel processors have some profiling registers that can point you to this kind of problems, but typically you first have to know what you want to profile. Compilers are actually built to align the structures you write as there are a lot of processors which have significantly slo…
You can always write your own incremental allocator to provide word aligned (or whatever alignment) blocks of memory (from a large block of memory you obtain via a usual malloc() call) for the individual structures such that their page offsets are spread evenly (and avoid other problems such as spanning pages).
[EDIT] although it is tricky to do optimally given that different processors will have different cache set characteristics (as the article shows).
Re: How misaligning data can increase performance 12x by reducing cache misses
#9Earlier quoted context omitted.
I'm not aware of any flags of C compilers that would "fix potential cache-slot-collisions" for you automatically, neither of any allocators. Intel processors have some profiling registers that can point you to this kind of problems, but typically you first have to know what you want to profile. Compilers are actually built to align the structures you write as there are a lot of processors which have significantly slo…
You can always write your own incremental allocator to provide word aligned (or whatever alignment) blocks of memory (from a large block of memory you obtain via a usual malloc() call) for the individual structures such that their page offsets are spread evenly (and avoid other problems such as spanning pages). [EDIT] although it is tricky to do optimally given that different processors will have different cache set…
"Spreading" which will produce optimal cache use is something that depends on dynamic and not static properties of the program, so you'd have to "spread" differently depending on the use patterns. I can't imagine any universal solution.
And most of the programmers make much bigger omissions than those mentioned in this topic. Like using wrong algorithms, wrong libraries, doing too many allocations, having bad structures of the data... So this topic effects are invisible unless you already fixed other issues.
Re: How misaligning data can increase performance 12x by reducing cache misses
#10Interesting. One question. How would I take advantage of this ? Are there special flags for the compiler or special memory allocator that I would need ? Do libraries like BLAS already account for this ?
In C / C++ (in POD structs) you can use the pack attribute. Here's more documentation: http://gcc.gnu.org/onlinedocs/gcc/Type-Attributes.html I would still recommend you try to lay out the struct by hand to try to the right alignment for the variable.
Having said all that, before you do this. Why don't you first measure where you're seeing high cache misses and only optimize those. On Linux the perf tool is a god send, you can annotate down to the source code line.