4 ms·

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

... 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?
  - josephg 4y ago
    I'm sure CPUs will try their best to optimize these usage patterns. But I suspect vector / array based approaches will still always outcompete linked lists in actual benchmarks. Thats always been my experience of them. Linked lists still show up in the kernel, in redis, in game engines and so on because you can't build fast intrusive collections using arrays. Making linked lists "as fast as we can make them" doesn't mean they're competitive with a vector.
  - optymizer 4y ago
    Look, people who are excited about this and just want to learn are asking for proof. You can't just make a claim like "it's been a feature of high performance for more a decade" and provide 0 evidence for the claim, because it's not common knowledge and explicitly contradicts what is commonly taught. I can time how long it takes to iterate through an array and show that it is faster than iterating through a linked list with the same number of elements. Now, what optimization would I have to impleemnt to end up with a program that iterates through this linked list faster than the equivalent array?
insanitybit 4y ago
> 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. I would need a source to believe this. The only way I can imagine this working is that the L2 prefetcher might incidentally work well with your allocator - your allocator might try to hand out more or less colocated or evenly strided data. > I'm not sure what you "don't buy" This statement, primarily: > Modern CPUs detect patterns of pointer chasing common in linked list use and prefetch to cache just fine To me, this statement reads as: 1. Prefetchers in CPUs can prefetch data by examining loads that have yet to be executed 2. That they do this well, or at least that's how I read "just fine" To my knowledge neither of those is true. > You appear to want to argue for some reason. I'm not trying to argue at all, I'm trying to learn. What you're saying does not sound right to be but it would be extremely interesting to me if I learned that CPUs are doing something that I'm not aware of. If you're actually saying that an allocator may end up striding allocations such that the prefetcher can reliably predict where to load next, sure I'll buy that, at least for L2. That's a fine thing to say, it just isn't what I took away from your initial statement, which is what I wanted to drill into because, again, it would be very interesting to me. Sorry if I'm coming off as argumentative, I was rushing that previous comment, which isn't really fair to put on you. I genuinely just am curious and if this is a case of miscommunication, no worries at all. I'd just be remiss if I didn't try to suss out if I'm wrong.

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?
- josephg 4y ago
  I'm sure CPUs will try their best to optimize these usage patterns. But I suspect vector / array based approaches will still always outcompete linked lists in actual benchmarks. Thats always been my experience of them. Linked lists still show up in the kernel, in redis, in game engines and so on because you can't build fast intrusive collections using arrays. Making linked lists "as fast as we can make them" doesn't mean they're competitive with a vector.
- optymizer 4y ago
  Look, people who are excited about this and just want to learn are asking for proof. You can't just make a claim like "it's been a feature of high performance for more a decade" and provide 0 evidence for the claim, because it's not common knowledge and explicitly contradicts what is commonly taught. I can time how long it takes to iterate through an array and show that it is faster than iterating through a linked list with the same number of elements. Now, what optimization would I have to impleemnt to end up with a program that iterates through this linked list faster than the equivalent array?

insanitybit 4y ago

> 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. I would need a source to believe this. The only way I can imagine this working is that the L2 prefetcher might incidentally work well with your allocator - your allocator might try to hand out more or less colocated or evenly strided data. > I'm not sure what you "don't buy" This statement, primarily: > Modern CPUs detect patterns of pointer chasing common in linked list use and prefetch to cache just fine To me, this statement reads as: 1. Prefetchers in CPUs can prefetch data by examining loads that have yet to be executed 2. That they do this well, or at least that's how I read "just fine" To my knowledge neither of those is true. > You appear to want to argue for some reason. I'm not trying to argue at all, I'm trying to learn. What you're saying does not sound right to be but it would be extremely interesting to me if I learned that CPUs are doing something that I'm not aware of. If you're actually saying that an allocator may end up striding allocations such that the prefetcher can reliably predict where to load next, sure I'll buy that, at least for L2. That's a fine thing to say, it just isn't what I took away from your initial statement, which is what I wanted to drill into because, again, it would be very interesting to me. Sorry if I'm coming off as argumentative, I was rushing that previous comment, which isn't really fair to put on you. I genuinely just am curious and if this is a case of miscommunication, no worries at all. I'd just be remiss if I didn't try to suss out if I'm wrong.