Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How misaligning data can increase performance 12x by reducing cache misses

danluu.com

Post reply on HN
Print view View original

21–30 of 31 posts

Re: How misaligning data can increase performance 12x by reducing cache misses

#21

Post by stephencanon »

mikerg87 wrote: post #3

Interesting. 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 ?

BLAS doesn’t layout data for you; it needs to work with the alignment of buffers that you pass as arguments. High-performance BLAS implementations do often allocate their own temporary workspace, and some account for issues like this (because BLAS access on large buffers is dense, the exact issue described here is rarely a problem, but 4k false aliasing frequently is for huge power-of-two sized matrices, for example).

Re: How misaligning data can increase performance 12x by reducing cache misses

#22

Post by rossjudson »

bwzhou wrote: post #19

Why would you want to make an in-memory data structure page-aligned instead of cache-line-aligned?

It's not that you would want to. It's that certain data structures (particularly in kernel land) naturally form around powers-of-2 sizing. Since the hashing in an n-way associative cache is done by masking away bits, you can get into this nasty situation where multiple elements of your data structure end up hashing to the same location set (the N in an N-way associative cache). You don't want that if you are going to walk the elements in your structure.

Either avoid walking the elements, or do whatever it takes to ensure that you don't end up getting stuck behind the N.

Hardware is inescapable.

It's also worth noting that you can use this to your advantage, ensuring that accesses to certain elements does not push much else out of the associative cache.

Re: How misaligning data can increase performance 12x by reducing cache misses

#23

Post by dded »

Many modern processors hash some of the address bits before using them as a cache index to avoid these problems.

To avoid them in code, it's often sufficient to round to convenient decimal numbers when allocating arrays, instead of powers-of-2. That is, allocate an array of 1000, instead of an array of 1024.

Re: How misaligning data can increase performance 12x by reducing cache misses

#24

Post by nkurz »

Hi Dan --

Great example. I looked briefly at the source, and wasn't sure whether "pointer_chase" was on or off in your graphs. Or maybe it didn't make a difference?

Page-aligned accesses like these also make compulsory misses worse, because prefetchers won’t prefetch beyond a page boundary. But if you have enough data that you’re aligning things to page boundaries, you probably can’t do much about that anyway.

To the contrary, I think this is one of the relatively rare cases that explicit prefetching can help you. But maybe this helps only once your sets are too large for L3?

I wrote a little a few months ago on my attempts to speed up a Stream benchmark for Sandy Bridge that might have some overlap with your post: http://software.intel.com/en-us/forums/topic/480004#comment-...

Re: How misaligning data can increase performance 12x by reducing cache misses

#25

Post by joe_the_user »

I understand this only enough to understand that it may or may not be a surprising and paradoxical result.

As a not-systems c++ programmer, it seems to reinforce the usual lesson: don't optimize your structures initially for anything but readability, once you have your system running and can pinpoint the bottlenecks, then try things like aligning structures to various things. But naturally always have a real-world-like test-suite to verify you are improving things.

Sorry if this is boring.

Re: How misaligning data can increase performance 12x by reducing cache misses

#26

Post by [deleted] »

rossjudson wrote: post #22
bwzhou wrote: post #19

Why would you want to make an in-memory data structure page-aligned instead of cache-line-aligned?

It's not that you would want to. It's that certain data structures (particularly in kernel land) naturally form around powers-of-2 sizing. Since the hashing in an n-way associative cache is done by masking away bits, you can get into this nasty situation where multiple elements of your data structure end up hashing to the same location set (the N in an N-way associative cache). You don't want that if you are going to…

[deleted]

Re: How misaligning data can increase performance 12x by reducing cache misses

#28

Post by scott_s »

The linked usenet discussion is worth reading, partially because a student asks for help on their homework, and it eventually pulls in Linus Torvalds: https://groups.google.com/d/msg/comp.arch/_uecSnSEQc4/jkdcQc...

The actual discussion is good, too.

Re: How misaligning data can increase performance 12x by reducing cache misses

#29

Post by scott_s »

bwzhou wrote: post #19

Why would you want to make an in-memory data structure page-aligned instead of cache-line-aligned?

It's commonly done in memory allocators at various levels. You inherently want to manage pages, and you'll carve out the start of the page itself to hold its own data structure.

You can see an example of this technique here: https://github.com/scotts/streamflow/blob/master/streamflow....

This bit of code executes when a call to malloc() could not find any free memory, and it has to request more memory from the operating system. The function supermap() allocates a large chunk of memory from the kernel. We then write the meta-information to keep track of that chunk of memory directly to itself - that "meta-information" is the pageblock_t struct. In malloc(), we then use that chunk of memory to find a sub-chunk inside of it to return to the user.

Note that internal to malloc(), we will maintain lists of these pageblock_t structures, and they will all be page-aligned. So, anytime we want to search for free memory among the managed pages, we're going to access page-aligned structures.

Post reply on HN