Skip to main content
2 of 6
added 9 characters in body
Engineer
  • 771
  • 5
  • 17

In your innermost loops, AKA critical sections, try to operate on no more than the system word size, but at least that size.

If you can manage this, then cache line size alignment should be no issue - this can either be handled transparently by cache in the case of your program only having an inner loop, or more explicitly by an outer loop that pulls back cache line sized chunks of data, less frequently than the inner loop runs.

Example1: A program to sum 2^12=4096 unsigned bytes. It can do so more efficiently by pulling sets of 8 bytes at a time and summing these in an unrolled inner loop, than requesting one byte and a time and summing these in a rolled innermost loop. (Indeed, this program could do this recursively for very fast performance, a bit like a binary sort.)

Example 2:* A program needing a large minimal dataset to do its work, for example an 8x8 matrix of 4 byte floats, requires 256B to perform the work in the innermost loop. For this, 4 cache line reads are required. In this case, the system word size is of little consequence unless we can pull 2x 4 byte floats at a time as a single 8 byte word, and working on cache line size boundaries is critical.

How do we pull sets of 8B at a time? Make arrays / buffers be of a type that matches that size, so that you can read / write it accordingly". For example, for 64-bit system word size (modern Intel):

struct MyTypeAlignedToWordSize
{
    unsigned byte bytes[8]; 
}
//add your language-specific alignment instructions / compiler hints

or

struct MyTypeAlignedToWordSize
{
    unsigned short bytes[4]; //4 * 2 bytes = 8 bytes.
}

or even just

using MyTypeAlignedToWordSize = unsigned long; //also 8 bytes.

...Where working with arrays of the same number of bytes, bytewise, would be around 8x slower.

For larger minimal datasets i.e. the dataset required for what you do per iteration of your innermost loop, aim for cache line size, or (preferably small) multiples thereof.

TL;DR match your innermost loop level to your system word size if possible (implies cache line size), or cache line size if not. Note that the implication here is that we work in arrays of small elements - always a good idea anyway, for code that needs to be performant.

See also: data-driven design & programming, cache-oblivious algorithms.

Engineer
  • 771
  • 5
  • 17