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

11–20 of 31 posts

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

#11

Post by mtanski »

One of the things to keep in mind here is that this trick won't work or work as well for every architecture or every processor family in that architecture.

Some architectures do not support unaligned memory access and will raise an exception. If you're using things like packed attribute with your structs your compiler will generate the correct code but that code will be slower. In almost all cases it will generate many more instructions and because of that your cache will be less effective (due to larger code size) your decoder cache will be less effective, etc...

The author has a more modern Intel processor. The x86 family always supported unaligned access, albeit it was always slower in terms of cycles. More recent Intel processor have made this penalty much shorter. I believe this was driven network applications many of which focus on efficiency of packing as many bytes down the channel and less on the alignment requirements. http://www.agner.org/optimize/blog/read.php?i=142&v=t

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

#12

Post by ihenriksen »

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 ?

The #pragma pack directive in C++ might be useful for stack allocations. http://stackoverflow.com/questions/3318410/pragma-pack-effec... For heap allocation you have _aligned_malloc() and memalign().

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

#13

Post by cowsandmilk »

I see many comments here acting like this means not aligning on word boundaries (e.g. using packed pragma, sandy bridge have unaligned access, etc.). This has nothing to do with word alignment. As the article states at the beginning, this is about aligning to page boundaries, which is on a very different level than word boundaries or structure packing. Let's not get these confused.

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

#14

Post by danso »

> Well, I’ve now managed to blog about three of the areas where I have the biggest comparative advantage. Three or four more blog posts and I’ll be able to write myself straight out of my job. I must be moving up in the world, because I was able to automate myself out of my first job with a couple shell scripts and a bit of Ruby. At least this requires some human intervention.

This was a great explanation of caching architecture, but I really want to hear the story of how the OP automated himself out of his first job with some shells scripts and Ruby.

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

#16

Post by alexkus »

acqq wrote: post #9
alexkus wrote: post #8

Earlier quoted context omitted.

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 structu…

True, but having every structure aligned to exactly the same offset into each page is extremely unlikely. Given a page size of 4KB then a whole bunch of 32 byte structures aligned in such a way would represent a huge waste of memory. No sane allocator will allocate things like this.

If your structures happen to be very close to the system's page size it could easily happen, then you'd need to avoid this yourself with your own incremental allocator (or other tricks).

Definitely agree with your last point, I've seen lots of code (in commercial applications) where people are optimising completely the wrong thing.

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

#17

Post by jere »

jbl wrote: post #6
brokenparser wrote: post #4

Can 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.

Ah good explanation. The use of "vs" in a graph title makes me assume it's describing X vs Y, which is confusing.

It also helped when I realized the graph starts at 1 for working set size of 8 and the author corresponding says:

>Except for very small working sets (1-8), the unaligned version is noticeably faster

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

#18

Post by cube13 »

mtanski wrote: post #11

One of the things to keep in mind here is that this trick won't work or work as well for every architecture or every processor family in that architecture. Some architectures do not support unaligned memory access and will raise an exception. If you're using things like packed attribute with your structs your compiler will generate the correct code but that code will be slower. In almost all cases it will generate ma…

You're talking about word aligned boundries, which is absolutely an issue with certain architectures(I remember dealing with the issue with older SPARC processors). The article is talking about L2 and L3 processor cache hash collisions, which can result in lost performance as the cache's are overwritten.

This optimization doesn't preclude those architectures necessarily, it's saying that instead of allocating at address 512, 1024, etc., there might be a boost from allocating at off-page addresses.

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

#20

Post by mtanski »

cube13 wrote: post #18
mtanski wrote: post #11

One of the things to keep in mind here is that this trick won't work or work as well for every architecture or every processor family in that architecture. Some architectures do not support unaligned memory access and will raise an exception. If you're using things like packed attribute with your structs your compiler will generate the correct code but that code will be slower. In almost all cases it will generate ma…

You're talking about word aligned boundries, which is absolutely an issue with certain architectures(I remember dealing with the issue with older SPARC processors). The article is talking about L2 and L3 processor cache hash collisions, which can result in lost performance as the cache's are overwritten. This optimization doesn't preclude those architectures necessarily, it's saying that instead of allocating at addr…

You are correct.
Post reply on HN