5 ms·

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 lib

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 ?

acqq 13y ago
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?
- alexkus 13y ago
  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).
  - acqq 13y ago
    "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.
    - alexkus 13y ago
      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.
tokenrove 13y ago
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.
mtanski 13y ago
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 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.
ihenriksen 13y ago
The #pragma pack directive in C++ might be useful for stack allocations. http://stackoverflow.com/questions/3318410/pragma-pack-effect http://stackoverflow.com/questions/3318410/pragma-pack-effec... For heap allocation you have _aligned_malloc() and memalign().
stephencanon 13y ago
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).

acqq 13y ago

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?

alexkus 13y ago
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).
- acqq 13y ago
  "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.
  - alexkus 13y ago
    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.

tokenrove 13y ago

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.

mtanski 13y ago

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

ihenriksen 13y ago

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

stephencanon 13y ago

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