4 ms·

Apple's M1 has a data dependent prefetcher (superset form of pointer chase prefetcher), as discovered by the researchers behind the Augury paper [1]. They discu

Apple's M1 has a data dependent prefetcher (superset form of pointer chase prefetcher), as discovered by the researchers behind the Augury paper [1]. They discuss how it works, how and when it activates, as well as a couple other cool details which should more than answer your curiosity. They don't have benchmarks for performance, but these sorts of prefetchers do exist (and possible in hardware you're using right now!). [1] https://www.prefetchers.info/augury.pdf https://www.prefetchers.info/augury.pdf

tylerhou 4y ago
The prefetcher described in the paper implemented in the M1 is nowhere near a prefetcher that would be able to prefetched linked-list nodes. > We tested for the existence of four DMPs: both single- and two-level versions of pointer-chasing and indirection-based DMPs (Section IV). Our findings show the existence of a single-level pointer-chasing DMP.... When activated, the prefetcher described will also issue loads for pointers in a contiguous array of pointers. In particular, the pointer/addresses are already known by the core (because they themselves were presumably prefetched far ahead of time by the stream/stride prefetcher), so the core knows which addresses to prefetch. But in a linked-list, the address of the next node is not known by the core until after the node is retrieved from memory. I.e. there is an additional data dependency, and it takes a round trip to memory to resolve that data dependency. It's the difference between prefetching B's in A0 A1 A2 A3 A4 v v v v v B0 B1 B2 B3 B4 and prefetching B, C, D, E in A -> B -> C -> D -> E The former is much easier to do than the latter as 1) the A's are easy to prefetch, and 2) the B's can be fetched in parallel. In the second, the core has to wait until B resolves before it can fetch C, and it has to wait until C resolves before it can fetch D, etc.

tylerhou 4y ago

The prefetcher described in the paper implemented in the M1 is nowhere near a prefetcher that would be able to prefetched linked-list nodes. > We tested for the existence of four DMPs: both single- and two-level versions of pointer-chasing and indirection-based DMPs (Section IV). Our findings show the existence of a single-level pointer-chasing DMP.... When activated, the prefetcher described will also issue loads for pointers in a contiguous array of pointers. In particular, the pointer/addresses are already known by the core (because they themselves were presumably prefetched far ahead of time by the stream/stride prefetcher), so the core knows which addresses to prefetch. But in a linked-list, the address of the next node is not known by the core until after the node is retrieved from memory. I.e. there is an additional data dependency, and it takes a round trip to memory to resolve that data dependency. It's the difference between prefetching B's in A0 A1 A2 A3 A4 v v v v v B0 B1 B2 B3 B4 and prefetching B, C, D, E in A -> B -> C -> D -> E The former is much easier to do than the latter as 1) the A's are easy to prefetch, and 2) the B's can be fetched in parallel. In the second, the core has to wait until B resolves before it can fetch C, and it has to wait until C resolves before it can fetch D, etc.