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

|cite|improve this question
$\endgroup$
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.

|cite|improve this answer
$\endgroup$
  • $\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
  • $\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

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.