And plenty of use cases are much better with linked lists than resizable vectors. Eg: queues.
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?
It details the prefetchers, how they work, what patterns they recognize (section 3.7)
https://www.forrestthewoods.com/blog/memory-bandwidth-napkin...
"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" ?
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.
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.
> 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.
"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."
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.
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.
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.
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'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.
Do you have anything substantial to add to that?
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.
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 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.
> 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
A -> B -> C -> D -> E
It is extremely difficult, maybe impossible, to design a prefetcher that can predict the next cacheline(s) to prefetch while traversing in a linked-list. I am not aware of a single CPU that can do this consistently. For instance, if you run multichase (a linked-list chaser) on GCP servers, you generally get the expected memory latency (~70-100ns, depending on the platform).
https://github.com/erlang/otp/blob/master/lib/stdlib/src/que... https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/...
There are some niche use cases where linked lists are good. Lock-free queues are one, and another big set of use cases is where you need hard O(1) insert even with a high constant factor, not amortized O(1).
If you need hard O(1) insert you can usually just allocate an array much bigger than you will need. The combination of hard performance requirements and willingness to wait for an allocator all the time is unusual.
This is a special case of where they also appear: linked hashmap implementations, where you want a hashmap that has a consistent iteration order.
Intrusive lists are used in the Linux kernel, in physics engines (eg Chipmunk2d) and game engines. The way Redis uses them for TTL expiry follows the same pattern.
You will need a truly concurrent memory allocator for that, too... or if you are just the kernel (one of the reasons the linux kernel can benefit from linked lists)
Overall, allocating new objects/memory is not guaranteed O(1).
Often lists refer to arrays or sections of memory. The performance loss if any appears in bigger structures where you do want to have explicit control anyway.
There is a reason why non-embedded CPUs have sizable L2 caches now.
Vectors are basically perfect for queues.
[1] https://stackoverflow.com/questions/6292332/what-really-is-a...