14 ms·

Ok, summary: This article lays out three scenarios: 1) accessing two random elements 2) accessing 3 random elements 3) accessing two pairs of adjacent elemen

by wrsh07 6y ago

Ok, summary: This article lays out three scenarios: 1) accessing two random elements 2) accessing 3 random elements 3) accessing two pairs of adjacent elements (same as (1) but also the elements after each random element) It then does some trivial math to use the loaded data. A naive model might only consider memory accesses and might assume accessing an adjacent element is free. On the Mac m1 core, this is not the case. While the naive model might expect cases 1 & 3 to cost the same and case 2 to cost 50% more, instead cases 2 & 3 are nearly the same (3 slightly faster) and case 2 is about 50% more expensive than 1.

jayd16 6y ago
I don't really understand the comparison because it seems like scenario 3 (2+) is doing more XORs and twice the accesses to array over the same amount of iterations. We have to assume these are byte arrays, yes? Or at least some size that's smaller than the cache line. You would still pay for the extra unaligned fetches. I don't think this is a valid scenario at all, M1 or not. Anyone want to run these tests on an Intel machine and let us know if the authors "naive model" test hold there?
- africanboy 6y ago
  I did it on an old i7 laptop https://news.ycombinator.com/item?id=25661055 https://news.ycombinator.com/item?id=25661055
- wrsh07 6y ago
  The point of the naive model is that you assume memory accesses dominate That is, the math part is so trivial compared to the memory access that you could do a bunch of math and you would still only notice a change in the number of memory accesses. Also it looks like the response to yours links their test and the naive model predicts correctly
  - jayd16 6y ago
    I think 5% is a non-trivial difference but alright, its a much bigger difference on the M1. I guess I still don't understand whats going on here. Scenario 1 has two spatially close reads followed by two dependent random access reads. Scenario 3 (2+) has two spatially close reads, and two pairs of dependent random access reads of two spatially close locations. Why does it follow that this is caused by a change in memory access concurrency? The two required round trips should dominate both on the M1 and an Intel but for some reason the M1 performs worse than that. Why? I can't help but feel the first snippet triggers some SIMD path while the 3rd snippet fails to.
    - wrsh07 6y ago
      I think the 5% can maybe be accounted for by the cache line (you mentioned this above, and I don't think the experiment does anything to prevent the issue)? If it's 1/16th chance of crossing the cache line, that maybe is about 5% of the time? I say that with pretty low confidence though I think you raise a good question, though -- what really is going on here? Is this just a missed optimization compiling for the m1? Or is it actually something fundamental about how reads happen with an m1? I'm definitely not knowledgeable enough to know how to answer this
temac 6y ago
> A naive model might only consider memory accesses and might assume accessing an adjacent element is free. Really depends on the level of naivety and the definition of "free". It would be less insane to write that: accessing an adjacent element has a negligible overhead if the data must be loaded from RAM and there are some OOO bubbles to execute the adjacent loads. If some data are in cache the free adjacent load claim immediately is less probable. If the latency of a single load is already filled by OOO, adding another one will obviously have an impact. If the workload is highly regular you can get quite chaotic results when making even some trivial changes (even sometimes when aligning the .text differently!) And the proposed microbenchmark is way too simplistic: it is possible that it saturates some units in some processors and completely different units in others... Is the impact of an extra adjacent load from RAM likely to be negligible in a real world workloads? Absolutely. With precise characteristics depending on your exact model / current freq / other memory pressure at this time, etc.

by wrsh07 6y ago

jayd16 6y ago

I don't really understand the comparison because it seems like scenario 3 (2+) is doing more XORs and twice the accesses to array over the same amount of iterations. We have to assume these are byte arrays, yes? Or at least some size that's smaller than the cache line. You would still pay for the extra unaligned fetches. I don't think this is a valid scenario at all, M1 or not. Anyone want to run these tests on an Intel machine and let us know if the authors "naive model" test hold there?

africanboy 6y ago
I did it on an old i7 laptop https://news.ycombinator.com/item?id=25661055 https://news.ycombinator.com/item?id=25661055
wrsh07 6y ago
The point of the naive model is that you assume memory accesses dominate That is, the math part is so trivial compared to the memory access that you could do a bunch of math and you would still only notice a change in the number of memory accesses. Also it looks like the response to yours links their test and the naive model predicts correctly
- jayd16 6y ago
  I think 5% is a non-trivial difference but alright, its a much bigger difference on the M1. I guess I still don't understand whats going on here. Scenario 1 has two spatially close reads followed by two dependent random access reads. Scenario 3 (2+) has two spatially close reads, and two pairs of dependent random access reads of two spatially close locations. Why does it follow that this is caused by a change in memory access concurrency? The two required round trips should dominate both on the M1 and an Intel but for some reason the M1 performs worse than that. Why? I can't help but feel the first snippet triggers some SIMD path while the 3rd snippet fails to.
  - wrsh07 6y ago
    I think the 5% can maybe be accounted for by the cache line (you mentioned this above, and I don't think the experiment does anything to prevent the issue)? If it's 1/16th chance of crossing the cache line, that maybe is about 5% of the time? I say that with pretty low confidence though I think you raise a good question, though -- what really is going on here? Is this just a missed optimization compiling for the m1? Or is it actually something fundamental about how reads happen with an m1? I'm definitely not knowledgeable enough to know how to answer this

temac 6y ago

> A naive model might only consider memory accesses and might assume accessing an adjacent element is free. Really depends on the level of naivety and the definition of "free". It would be less insane to write that: accessing an adjacent element has a negligible overhead if the data must be loaded from RAM and there are some OOO bubbles to execute the adjacent loads. If some data are in cache the free adjacent load claim immediately is less probable. If the latency of a single load is already filled by OOO, adding another one will obviously have an impact. If the workload is highly regular you can get quite chaotic results when making even some trivial changes (even sometimes when aligning the .text differently!) And the proposed microbenchmark is way too simplistic: it is possible that it saturates some units in some processors and completely different units in others... Is the impact of an extra adjacent load from RAM likely to be negligible in a real world workloads? Absolutely. With precise characteristics depending on your exact model / current freq / other memory pressure at this time, etc.