Comment by insanitybit | Hacker News Reader

Comment by insanitybit | Hacker News Reader

Parent Full thread

I don't buy this.

https://www.youtube.com/watch?v=WDIkqP4JbkE

Prefetching in CPUs predates this talk.

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.

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

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

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.

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.

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?

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.

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?

Reply on news.ycombinator.com