6 ms·
Modern CPUs detect patterns of pointer chasing common in linked list use and prefetch to cache just fine. Your comment would have been valid a decade or more ag
by dmitrygr 4y ago
Modern CPUs detect patterns of pointer chasing common in linked list use and prefetch to cache just fine. Your comment would have been valid a decade or more ago.
And plenty of use cases are much better with linked lists than resizable vectors. Eg: queues.
- vbezhenar 4y agoRAM latency is huge. No amount of prefetching can fix that. If anything, prefetching works better with arrays as RAM reads multiple bytes at once.
- xxs 4y agoQueues are best implemented with a pow2 cyclic array, and you have a free deque, too.
- attractivechaos 4y agoA ring-buffer based queue is mostly better than a linked list but it is not necessarily the best. The typical STL deque implementation [1], with all its complexity, is usually faster than a ring buffer. [1] https://stackoverflow.com/questions/6292332/what-really-is-a-deque-in-stl https://stackoverflow.com/questions/6292332/what-really-is-a...
- Borealid 4y agoI think there's more to cache locality than prefetching. In an array, consecutive elements will be usually be adjacent in physical memory (excepting page boundaries ), so each cache line load where a cache line is larger than the array element will "overfetch" into the next element. This should mean fewer total cache loads and thus more efficient use of memory bandwidth for situations where it is constrained (such as walking a list).
- AstralStorm 4y agoThen again, if you have control over allocations you can prefetch whole chunks of data to which the list refers making this point moot. 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.
- howinteresting 4y agoFor most use cases a ring buffer either with or without a maximum length will do much better as a queue than a linked list will. 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).
- anonymoushn 4y agoHigh-performance SPSC queues are always implemented with an array. 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.
- gamegoblin 4y agoThe place I see linked lists pop up the mosts are when implementing LRU caches. You need a linked hashmap of sorts where the hashmap gives O(1) lookup to the linked list node in question, and then you can extract that node and move it to the head of the queue in O(1) as well. This is a special case of where they also appear: linked hashmap implementations, where you want a hashmap that has a consistent iteration order.
- josephg 4y agoI’ve seen them show up in lots of situations through intrusive lists, which I think is the general form of the example you’re giving. 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.
- xxs 4y agoHaving linked nodes of a hashmap, is just that - I'd not call it a linked list. You can do moving median with a binary tree and linked nodes, too.
- xxs 4y ago>where you need hard O(1) insert even with a high constant factor 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).
- spijdar 4y agoThere are a lot of factors involved, but given a limited number of cache lines that can be stored in low level cache, I would think there'd be at least some performance penalty for prefetching from non-linear blocks of memory vs the inherent spatial locality in an array/vector, if only because it'd cause more old cache to be evicted.
- AstralStorm 4y agoOr the opposite, prefetching a whole vector when you just need one item, evicting more than needed unnecessarily. There is a reason why non-embedded CPUs have sizable L2 caches now.
- colinmhayes 4y agoQueues are generally implemented with with a vector of pointers to vectors. Nicely diagrammed here https://stackoverflow.com/questions/6292332/what-really-is-a-deque-in-stl https://stackoverflow.com/questions/6292332/what-really-is-a... Ring buffers also work better than linked lists
- waynesonfire 4y agois Erlang and JDK general enough for you? Oh, both use linked lists, https://github.com/erlang/otp/blob/master/lib/stdlib/src/queue.erl#L55 https://github.com/erlang/otp/blob/master/lib/stdlib/src/que... https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/share/classes/java/util/concurrent/LinkedBlockingQueue.java https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/...
- xxs 4y agowhy would your refer LinkedBlockingQueue? You have ArrayBlockingQueue, too. ArrayDeque is just better than LinkedList.
- anonymoushn 4y agoEven if your linked list is backed by an array and all the elements are right next to each other, computing some cheap function of the elements of a linked list is incredibly slow compared to the alternative because of the unnecessary and very long dependency chain. Vectors are basically perfect for queues.
- optymizer 4y agoI'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 agoFeast 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 agoMy benchmarks say you’re wrong. https://www.forrestthewoods.com/blog/memory-bandwidth-napkin-math/ https://www.forrestthewoods.com/blog/memory-bandwidth-napkin...
- dmitrygr 4y agoYou'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 agoSorry 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.
- tylerhou 4y agoI have some experience using/modifying linked-list benchmarks (https://github.com/google/multichase https://github.com/google/multichase) specifically to test memory latency. 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).
- AstralStorm 4y agoWhy let the CPU guess when you can tell it what you want? (Prefetch a small arena of objects linked to by the list.)
- deleted 4y ago[deleted]
- gpderetta 4y agoEven with a perfect prefercher a linked list would still be slower to iterate than a vector as it is inherently serial (unless your CPU does address prediction and I don't think any CPU does).