Hacker News Reader

Comment by LinaLauneBaer | Hacker News Reader

Can someone explain why zeroarray2 is so much slower than zeroarray1 (regarding question 2)? I have profiled the two functions and it turns out for inner for-loop and the line which zeros out the entry in the array are much slower... (optimisations turned off). The only real difference is the name of the variables. Right? Has this something to do with memory alignment?

View on HN

In zeroarray1 the address to be zeroed goes linearly from 0 to (1024^2)-1. This generates less cache misses because the address is much more likely to already be in the cache, which is in turn because the address only differes by one from the previous value of the address.

zeroarray2 jumps around (0, 1024, 2048, 4096, ..., 1, 1025, 2049, 4097, ...) in a way that intentionally makes life difficult for the cpu's cache manager, and generating lots of cache misses.

Also worth noting that this is language dependent. What you say is true in C (which is admittedly what the question was about), but not true in for example Fortran.

edit: Ignore. I'm wrong, see below

I'm not doubting what you say, but could you elaborate on why Fortran is different?

I could understand a difference for two-dimensional (or more) arrays, where different languages lay-out the array contents in memory differently. Does Fortran lay-out the contents of one dimensional arrays in an unusual way?

Sorry, I screwed up. I skimmed the question and mis-remebered it when making my post. I thought the question looked like:

  for(i=0...
    for(j=0...
      A[i][j]=0;

  for(i=0...
    for(j=0...
      A[j][i]=0;

In which case C vs Fortran makes a difference to the way multidimensional arrays are stored in memory.

A simple rule of thumb is contiguous memory access = cache friendly => fast operations. zeroarry2's access to memory jumps by 1024 for every assignment. Far apart non-contiguous memory access is not cache friendly at all.

I'm still learning my way around caches and memory timing, so if someone better educated than I could correct me if I'm wrong, I'd be very appreciative. That said, here's what I'd say:

The core of the issue is with cache-friendly access patterns. This is a simplified explanation, but here goes: CPUs only have so much cache, and the processor needs to keep enough data in that cache that it won't be left waiting for too long before the next batch of data requested from ram is available. To that end, when you access a chunk of memory, the CPU will grab the requested region and then some, hoping that most of your work for the next few microseconds will be within that region. The second implementation jumps by 1024 x sizeof(double) at each access (so, on my system that's 8k), which is plenty far to blow through whatever memory was prefetched with your access, and in so doing force the processor to sit around and wait for another memory location to be cached.

There's another, probably less significant way in which this is a pathological access pattern: alignment. When, in the first implementation, the processor operates on contiguous blocks of memory it is free to prefetch memory in nicely sized chunks that begin and end on convenient numbers, which is important because memory today is nothing if not a tower of multiplexed access -- asking for a few extra bits over the edge of a row, wherever those borders happen to be for your system (probably the width of the memory bus is a good guess), may not seem like much, but if it means the memory controller has to access a row of ram that it otherwise wouldn't, that involves first writing the data in the starting row, then waiting for the appropriate delay to save that data before switching rows and repeating the process. Looking at zeroarray2 in that context, you're asking the memory controller to save sizeof(double)*8 bits of zeroes, a fraction of a row, at once before moving on to another row only to revisit the first some time later.

Answers to the questions pertaining to memory (rather than concurrency) can all be found in Ulrich Drepper's excellent tour of contemporary memory systems, "What Every Programmer Should Know About Memory" ( http://www.akkadia.org/drepper/cpumemory.pdf ).

edit: fixed accidental italics, added useful additional reading link.

I believe when traversing memory in a predictable, linear fashion the CPU will prefetch data. I thought the CPUs are smart enough to do that for the more complex examples as well, but maybe not for steps of 1024.

Intel Core architecture has a stride prefetcher, but it will not prefetch across page boundaries (which you hit pretty often with a 1k step size).

You'll hit it every time given a typical x86 4KB page size and a step of 1024*sizeof(double)=8KB.

I would guess that the example was explicitly contrived so that prefetching would be useless.

I would guess that the example was explicitly contrived so that prefetching would be useless.

Yes -- even if prefetching could happen, the first function would be faster than the second, but I thought removing the whole issue of prefetching would simplify the question.

On the one assembly language I vaguely remember, it has to do with how mul is implemented. The 2nd function has to swap out the i repeatedly.

Reply on news.ycombinator.com