Re:Things you can’t do in Rust (and what to do instead)
by kllrnohj on Sunday May 16, 2021 @12:16PM
(#27174654)
> One use case where I think linked lists would be far superior would be merging two sorted linked lists.
Benchmark it & prove it. I expect you're still vastly underestimating how slow it is to traverse a linked list.
To visit a node in a linked list you must first load the node before it. Every iteration is a dependent load. You get no pipelining here, so every node lookup is ~100ns. Meanwhile for vectors each index is independent, so they are nice & pipelined. Yeah you're copying, but you've got vastly more memory bandwidth than memory latency.
Also to zipper merge 2 linked lists means updating 2 * N pointers. That's essentially a copy of the entire list right there, depending on the size of the contained object.
Benchmark it & prove it. I expect you're still vastly underestimating how slow it is to traverse a linked list.
To visit a node in a linked list you must first load the node before it. Every iteration is a dependent load. You get no pipelining here, so every node lookup is ~100ns. Meanwhile for vectors each index is independent, so they are nice & pipelined. Yeah you're copying, but you've got vastly more memory bandwidth than memory latency.
Also to zipper merge 2 linked lists means updating 2 * N pointers. That's essentially a copy of the entire list right there, depending on the size of the contained object.