5 ms·

Google for Intel hardware prefetcher and you'll turn up some info. Re: benchmarks. Not likely exactly what you're looking for, but the GigaUpdates Per Second

Google for Intel hardware prefetcher and you'll turn up some info. Re: benchmarks. Not likely exactly what you're looking for, but the GigaUpdates Per Second benchmark (https://en.wikipedia.org/wiki/Giga-updates_per_second https://en.wikipedia.org/wiki/Giga-updates_per_second) is sort of the most-pathological-case of pointer jumping where the jumps are random. Prefetchers don't do well with that (for obvious reasons) - they tend to work best when there is some pattern to the accesses. Linked data structures often live somewhere in between - they may start with good, regular stride patterns, but then over time as elements are added and moved around, it turns into a tangle of spaghetti. Edit: I should add more. While prefetchers do exist in hardware, they're a bit of a murky subject. Sometimes they speed things up, sometimes they do so bad they slow everything down. They can be very workload dependent. And to top it off, hardware vendors can sometimes be a bit opaque when explaining what their prefetching hardware actually does well on. It's probably safest to not assume your hardware will help you when it comes to tangled pointer jumping code, and if you can avoid it via a different data structure it's probably good to do so. That said, other data structures may entail other tradeoffs - better cache usage for lookups, but potentially more expensive insertions. As usual with data structures, its a game of balancing tradeoffs.

insanitybit 4y ago
I don't buy this. https://www.youtube.com/watch?v=WDIkqP4JbkE https://www.youtube.com/watch?v=WDIkqP4JbkE Prefetching in CPUs predates this talk. https://www.youtube.com/watch?v=Nz9SiF0QVKY https://www.youtube.com/watch?v=Nz9SiF0QVKY That talk is 2018. Cache prefetching works best for linear accesses like with a vector, not for random pointer lookups. Prefetchers are also going to have an extra harder time with double indirection since they're unable to see which value is going to be fed to the lea. Prefetching is also expensive in and of itself, the CPU doesn't do it unless you're already incurring cache hits. This makes cache misses even worse. There are also multiple prefetchers in the CPU and the L1 prefetcher is very basic and is only going to help with contiguous accesses. Your allocator might be doing some nice things for you that let the one of the L2 prefetchers help, I would expect that you'll see better L2 performance due to prefetching. If you have an example of a linked list being as fast as a vector for iteration, please do show it.
- porcoda 4y ago
  ... I didn't say it was for random pointer lookups. That's the pathological case that was the primary reason the Cray X-MT (formerly Tera MTA) was invented. As I said, when you have pointers with some regularity (hence my reference to regular or patterned striding), then you may get some benefit of prefetching when you're not just dealing with linear contiguous access. The "may" is important there - whether you do or don't get it is workload / data dependent. As I also said, more likely than not over time the data structure will lose regularity as pointers get re-wired, and the benefits of prefetching go out the window. I'm not sure what you "don't buy" - I didn't say definitively that prefetching does or does not always help. Sometimes it does, and when it does, it's highly dependent on the regularity of the way the pointers cause you to stride through memory. I even basically agreed with you -- to quote me, "It's probably safest to not assume your hardware will help you when it comes to tangled pointer jumping code". You appear to want to argue for some reason.
  - nice_byte 4y ago
    how do linked lists fit the regularity requirement? the only regularity in this pattern of access is the offset at which the next address to fetch is stored. this seems like a nontrivial amount of logic and state for the prefetcher to keep track of, unlike something like base * scale + offset when e.g. traversing a 2d array.
    - monocasa 4y ago
      It is more complex for hardware to keep track of for sure. It's been a feature of high performance cores for more than a decade though. Kernels tend to be based off of linked lists, so it's a massive win typically.
      - fuckstick 4y ago
        A bunch of people keep saying this with no substantiation - the best we saw was a link to the latest Intel optimization manual that quite specifically refutes this claim. I even quoted it upthread. Do you have anything substantial to add to that?

insanitybit 4y ago

I don't buy this. https://www.youtube.com/watch?v=WDIkqP4JbkE https://www.youtube.com/watch?v=WDIkqP4JbkE Prefetching in CPUs predates this talk. https://www.youtube.com/watch?v=Nz9SiF0QVKY https://www.youtube.com/watch?v=Nz9SiF0QVKY That talk is 2018. Cache prefetching works best for linear accesses like with a vector, not for random pointer lookups. Prefetchers are also going to have an extra harder time with double indirection since they're unable to see which value is going to be fed to the lea. Prefetching is also expensive in and of itself, the CPU doesn't do it unless you're already incurring cache hits. This makes cache misses even worse. There are also multiple prefetchers in the CPU and the L1 prefetcher is very basic and is only going to help with contiguous accesses. Your allocator might be doing some nice things for you that let the one of the L2 prefetchers help, I would expect that you'll see better L2 performance due to prefetching. If you have an example of a linked list being as fast as a vector for iteration, please do show it.

porcoda 4y ago
... I didn't say it was for random pointer lookups. That's the pathological case that was the primary reason the Cray X-MT (formerly Tera MTA) was invented. As I said, when you have pointers with some regularity (hence my reference to regular or patterned striding), then you may get some benefit of prefetching when you're not just dealing with linear contiguous access. The "may" is important there - whether you do or don't get it is workload / data dependent. As I also said, more likely than not over time the data structure will lose regularity as pointers get re-wired, and the benefits of prefetching go out the window. I'm not sure what you "don't buy" - I didn't say definitively that prefetching does or does not always help. Sometimes it does, and when it does, it's highly dependent on the regularity of the way the pointers cause you to stride through memory. I even basically agreed with you -- to quote me, "It's probably safest to not assume your hardware will help you when it comes to tangled pointer jumping code". You appear to want to argue for some reason.
- nice_byte 4y ago
  how do linked lists fit the regularity requirement? the only regularity in this pattern of access is the offset at which the next address to fetch is stored. this seems like a nontrivial amount of logic and state for the prefetcher to keep track of, unlike something like base * scale + offset when e.g. traversing a 2d array.
  - monocasa 4y ago
    It is more complex for hardware to keep track of for sure. It's been a feature of high performance cores for more than a decade though. Kernels tend to be based off of linked lists, so it's a massive win typically.
    - fuckstick 4y ago
      A bunch of people keep saying this with no substantiation - the best we saw was a link to the latest Intel optimization manual that quite specifically refutes this claim. I even quoted it upthread. Do you have anything substantial to add to that?