1
$\begingroup$

Hi I have a program which accesses memory words that are located X bytes apart in virtual address space. For instance, for (int i=0;<some stop condition>;i+=X){array[i]=4;}.

I measure the execution time with a varying value of X. Interestingly, when X is the power of 2 and is about page size, e.g., X=1024,2048,4096,8192..., I get to huge performance slowdown. But on all other values of X, like 1023 and 1025, there is no slowdown. The performance results are attached in the figure below.

X axis is the value of <code>X</code> and Y axis is execution time in milliseconds

I test my program on several personal machines, all are running Linux with x86_64 on Intel CPU.

What could be the cause of this slowdown? We have tried row buffer in DRAM, L3 cache, etc. which do not seem make sense...

Improve this question
$\endgroup$
2
  • $\begingroup$ You're not measuring latency, are you? Isn't that just overall or average throughput for the store loop? But anyway, my guess is that you're aliasing the same set in L1d cache when your stride is 4k. It's "only" 8-way associative, but Skylake has 12 LFBs (line-fill buffers). You didn't mention what specific microarchitecture you have. (e.g. i7-6700k Skylake?) $\endgroup$
    – Peter Cordes
    Mar 10 at 23:57
  • $\begingroup$ Oh, you also posted this on Stack Overflow as Slowdown when accessing data at page boundaries? where I wrote that as an answer 2 years ago :P This question just happened to come up while I was searching for something else. $\endgroup$
    – Peter Cordes
    Mar 11 at 0:01
3
$\begingroup$

Go to Agner manuals page and download them all, you will find tons of interesting info there. In particular, microarchitecture.pdf says

There is a false dependence between memory addresses with the same set and offset, i.e. with a distance that is a multiple of 4 Kbytes:

;Example 9.6. Sandy bridge false memory dependence
mov [rsi],eax
mov ebx,[rsi+1000H] ;False memory dependence

I.e. the access becomes slower because cpu thinks that it may be the same address, so the load in the second line may depend on the store in the first line and thus cpu serializes execution of these operations.

AFAIR, it wasn't changed in latest Intel cpus.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Not really. The loop from the question contains only stores, but 4K aliasing can only occur if there are loads as well in the loop. $\endgroup$
    – Hadi Brais
    Jul 10 '19 at 9:56
  • $\begingroup$ @HadiBrais, it was my first reaction, but then I found "For instance" part, so he probably oversimplified the real code $\endgroup$
    – Bulat
    Jul 10 '19 at 11:09
  • 1
    $\begingroup$ I'm not sure. If you look at the graph, you'll see that even the "cost" always increases with X, it's just that when X is a power of two it appears to increase much faster. If even if the code is different an, 4K aliasing may be just one of the factors. We also don't know what the y-axis represent. The question in it's current form is unanswerable really. $\endgroup$
    – Hadi Brais
    Jul 10 '19 at 11:40
  • 1
    $\begingroup$ @HadiBrais: Yeah, I'm not sure about 4k aliasing applying to pure stores. This might be due to a 4k stride making all the stores alias the same set in L1d cache, vs. any other stride distributing them over multiple sets, allowing better memory-level parallelism. $\endgroup$
    – Peter Cordes
    Mar 10 at 23:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.