Comment by porcoda | Hacker News Reader

Comment by porcoda | Hacker News Reader

Parent Full thread

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

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.

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.

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?

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.

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?

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

Reply on news.ycombinator.com