5 ms·

I'm going to call you out on this one, because it's a bold claim, and I'd love to see an explanation and some perf numbers. For example, I'm wondering how the

I'm going to call you out on this one, because it's a bold claim, and I'd love to see an explanation and some perf numbers. For example, I'm wondering how the CPU knows what the next item in the list to prefetch it. Unlike the next item in an array, list items could be pointing anywhere in process memory. Also, what counts as a modern CPU in this context? Are we talking latest generation desktop CPUs from Intel, or anything after Core 2 Duo? How about mobile devices with ARM CPUs? Would those just be ignored? Is there a benchmark?

dmitrygr 4y ago
Feast your eyes on the "Intel® 64 and IA-32 Architectures Optimization Reference Manual": https://cdrdv2-public.intel.com/671488/248966_software_optimization_manual.pdf https://cdrdv2-public.intel.com/671488/248966_software_optim... (newer link, as requested by one of the child comments) It details the prefetchers, how they work, what patterns they recognize (section 3.7)
- deleted 4y ago
  [deleted]
- forrestthewoods 4y ago
  My benchmarks say you’re wrong. https://www.forrestthewoods.com/blog/memory-bandwidth-napkin-math/ https://www.forrestthewoods.com/blog/memory-bandwidth-napkin...
  - dmitrygr 4y ago
    You're joking right? "I made an extra test that wraps matrix4x4 in std::unique_ptr." And that is your test? One piece of code? Not even presenting disassembly? Who the hell knows what your compiler wrought in response to your "std::unique_ptr" and "matrix4x4" ?
    - attractivechaos 4y ago
      Sorry for my ignorance – linked list matching the performance of vector is something new to me. I would like to learn more. The best way to prove your point is to show us a benchmark. However, I couldn't find one with a quick google search.
    - forrestthewoods 4y ago
      Well I’ve provided 1 benchmark to your 0. I’d say I’m ahead. My code benchmark is actually far more pre-fetch friendly than a LinkedList because it can prefetch more than one “node” at a time. In a LinkedList you can’t prefetch N+1 and N+2 at the same time because N+2 is dependent on the result of N+1. I’m always open to learning new things. Modern compiler magic is deep and dark. If sometimes a compiler magically makes it fast and sometimes slow that’d be quite interesting! If you have any concrete examples I’d love to read them.
- josephg 4y ago
  It doesn’t claim linked lists are fast. And it doesn’t have any benchmarking data. Actually the only reference to linked lists I see is in the prefetcher section (3.7.3), where it explicitly recommends that consecutive items are stored in a single 4kb cache line or in consecutive cache lines. They give a positive code example using an array, like other commenters are suggesting.
- fuckstick 4y ago
  It's a link to a document on architectures well over a decade old - the most recent mentioned is the original Core architecture (from 2008). Honestly, based on your first comment I thought you were implying something about content dependent prefetch or other techniques that I am familiar in the academic literature but unaware of ever being used in mainstream hardware. > Organize the data so consecutive accesses can usually be found in the same 4-KByte page. > • Access the data in constant strides forward or backward IP Prefetcher. 3-72 > Method 2: >• Organize the data in consecutive lines. > • Access the data in increasing addresses, in sequential cache lines. Nothing new here that contradicts the GPs skepticism. Certainly not enough evidence for you to be a dick.
  - dmitrygr 4y ago
    yup, was link to old a document with same title. updated. thanks.
    - fuckstick 4y ago
      Ok, but the hardware data prefetch functionality seems basically unchanged: "Characteristics of the hardware prefetcher are: • It requires some regularity in the data access patterns. — If a data access pattern has constant stride, hardware prefetching is effective if the access stride is less than half of the trigger distance of hardware prefetcher. — If the access stride is not constant, the automatic hardware prefetcher can mask memory latency if the strides of two successive cache misses are less than the trigger threshold distance (small- stride memory traffic). — The automatic hardware prefetcher is most effective if the strides of two successive cache misses remain less than the trigger threshold distance and close to 64 bytes."
- NavinF 4y ago
  Prefetching just one element ahead does fuck-all when ram is 100x slower than cache especially if you need to precharge and activate a new row which is always the case when you're spraying tiny objects all over the place.
  - AstralStorm 4y ago
    So don't spray tiny objects around. :) Keep them nicely tucked away in an arena. Vectors actually tend to create a spray of tiny objects... As opposed to a true dynamic array which has limitations in resize. If you're lucky, they will keep a single dynamic array per vector. You're usually not this lucky with bigger data.
    - josephg 4y ago
      If you never free your objects, you may as well use an array anyway - it'll be much more simple. And if you use an arena with an object pool, you're back in cache miss territory. Vectors only "create a spray of tiny objects" if you have a vector-of-references or something like that. And even then, reading data requires 2 reads from memory (1 to read the pointer in the vector, and another to read the object). Finding item N in a linked list will require N reads (since you need to read each item before the target). Yes, resizing a vector is O(n). But every time I measure memcpy, it always goes faster than I expect. If you disagree, try to prove it with code. At least one of us will learn something that way.
- insanitybit 4y ago
  This is a great document that will absolutely confirm, in a number of ways, that linked lists are going to be terrible for prefetching.
  - AstralStorm 4y ago
    That depends more on what they link to. Not prefetching a worthless list of pointers when you could prefetch data instead is typically faster. Prefetchers have limited capabilities and capacity for loads.
    - insanitybit 4y ago
      The prefetcher doesn't even have to get involved for linear sequences, it would only get involved after a cache miss threshold is met. The fastest and simplest prefetcher, L1, is stream based and will work great for sequential data.
porcoda 4y ago
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.
Sirened 4y ago
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.

dmitrygr 4y ago

Feast your eyes on the "Intel® 64 and IA-32 Architectures Optimization Reference Manual": https://cdrdv2-public.intel.com/671488/248966_software_optimization_manual.pdf https://cdrdv2-public.intel.com/671488/248966_software_optim... (newer link, as requested by one of the child comments) It details the prefetchers, how they work, what patterns they recognize (section 3.7)

deleted 4y ago
[deleted]
forrestthewoods 4y ago
My benchmarks say you’re wrong. https://www.forrestthewoods.com/blog/memory-bandwidth-napkin-math/ https://www.forrestthewoods.com/blog/memory-bandwidth-napkin...
- dmitrygr 4y ago
  You're joking right? "I made an extra test that wraps matrix4x4 in std::unique_ptr." And that is your test? One piece of code? Not even presenting disassembly? Who the hell knows what your compiler wrought in response to your "std::unique_ptr" and "matrix4x4" ?
  - attractivechaos 4y ago
    Sorry for my ignorance – linked list matching the performance of vector is something new to me. I would like to learn more. The best way to prove your point is to show us a benchmark. However, I couldn't find one with a quick google search.
  - forrestthewoods 4y ago
    Well I’ve provided 1 benchmark to your 0. I’d say I’m ahead. My code benchmark is actually far more pre-fetch friendly than a LinkedList because it can prefetch more than one “node” at a time. In a LinkedList you can’t prefetch N+1 and N+2 at the same time because N+2 is dependent on the result of N+1. I’m always open to learning new things. Modern compiler magic is deep and dark. If sometimes a compiler magically makes it fast and sometimes slow that’d be quite interesting! If you have any concrete examples I’d love to read them.
josephg 4y ago
It doesn’t claim linked lists are fast. And it doesn’t have any benchmarking data. Actually the only reference to linked lists I see is in the prefetcher section (3.7.3), where it explicitly recommends that consecutive items are stored in a single 4kb cache line or in consecutive cache lines. They give a positive code example using an array, like other commenters are suggesting.
fuckstick 4y ago
It's a link to a document on architectures well over a decade old - the most recent mentioned is the original Core architecture (from 2008). Honestly, based on your first comment I thought you were implying something about content dependent prefetch or other techniques that I am familiar in the academic literature but unaware of ever being used in mainstream hardware. > Organize the data so consecutive accesses can usually be found in the same 4-KByte page. > • Access the data in constant strides forward or backward IP Prefetcher. 3-72 > Method 2: >• Organize the data in consecutive lines. > • Access the data in increasing addresses, in sequential cache lines. Nothing new here that contradicts the GPs skepticism. Certainly not enough evidence for you to be a dick.
- dmitrygr 4y ago
  yup, was link to old a document with same title. updated. thanks.
  - fuckstick 4y ago
    Ok, but the hardware data prefetch functionality seems basically unchanged: "Characteristics of the hardware prefetcher are: • It requires some regularity in the data access patterns. — If a data access pattern has constant stride, hardware prefetching is effective if the access stride is less than half of the trigger distance of hardware prefetcher. — If the access stride is not constant, the automatic hardware prefetcher can mask memory latency if the strides of two successive cache misses are less than the trigger threshold distance (small- stride memory traffic). — The automatic hardware prefetcher is most effective if the strides of two successive cache misses remain less than the trigger threshold distance and close to 64 bytes."
NavinF 4y ago
Prefetching just one element ahead does fuck-all when ram is 100x slower than cache especially if you need to precharge and activate a new row which is always the case when you're spraying tiny objects all over the place.
- AstralStorm 4y ago
  So don't spray tiny objects around. :) Keep them nicely tucked away in an arena. Vectors actually tend to create a spray of tiny objects... As opposed to a true dynamic array which has limitations in resize. If you're lucky, they will keep a single dynamic array per vector. You're usually not this lucky with bigger data.
  - josephg 4y ago
    If you never free your objects, you may as well use an array anyway - it'll be much more simple. And if you use an arena with an object pool, you're back in cache miss territory. Vectors only "create a spray of tiny objects" if you have a vector-of-references or something like that. And even then, reading data requires 2 reads from memory (1 to read the pointer in the vector, and another to read the object). Finding item N in a linked list will require N reads (since you need to read each item before the target). Yes, resizing a vector is O(n). But every time I measure memcpy, it always goes faster than I expect. If you disagree, try to prove it with code. At least one of us will learn something that way.
insanitybit 4y ago
This is a great document that will absolutely confirm, in a number of ways, that linked lists are going to be terrible for prefetching.
- AstralStorm 4y ago
  That depends more on what they link to. Not prefetching a worthless list of pointers when you could prefetch data instead is typically faster. Prefetchers have limited capabilities and capacity for loads.
  - insanitybit 4y ago
    The prefetcher doesn't even have to get involved for linear sequences, it would only get involved after a cache miss threshold is met. The fastest and simplest prefetcher, L1, is stream based and will work great for sequential data.

porcoda 4y ago

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.

Sirened 4y ago

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.