2 ms·

That's interesting data. I guess I nerd-sniped you. One use case where I think linked lists would be far superior would be merging two sorted linked lists. Tha

by titzer 5y ago

That's interesting data. I guess I nerd-sniped you. One use case where I think linked lists would be far superior would be merging two sorted linked lists. That can be done completely in-place with a linked list, consuming no intermediate memory. With vectors, you end up with an intermediate copy, either of one of the lists, or both. If you take the result of merging two lists, then merge it with a third list, then take that and merge it with a fourth list, etc, you can't really do this with a vector-of-lists representation that might come to mind.

kllrnohj 5y ago
> 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.
ScottMichaud 5y ago
There are situations where you can have a linked list perform faster than a vector. It's good to consider linked lists if you have the time to think about your solution and profile multiple options... but the point is that memory latency is a huge hurdle to overcome. For context: A cold memory fetch is ~200 cycles. That's around 10 incorrectly-predicted branches. That's around 100 correctly-predicted branches. You need to be skipping a lot of work to justify injecting 100s of cycles of lag inside a loop of some sort. (And, of course, those situations would need to be the common, relevant case. Don't follow a 10x performance speed-up in a one-off situation at a time no-one cares about to justify a 5x slowdown in a critical, hot loop.) If you have big objects, then this might also start to become a concern. However, in those cases, a vector of pointers (or structs of pointers + metadata) would appear as a new challenger. In that case, you would only take the latency hit if you actually need to go to the object (and those objects could be held in contiguous storage, etc. etc. etc.). Chances are that, unless you have data for your specific case showing otherwise, vector will probably win. It should be the default unless you have a reason not to, and evidence to back it up.

by titzer 5y ago

kllrnohj 5y ago

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

ScottMichaud 5y ago

There are situations where you can have a linked list perform faster than a vector. It's good to consider linked lists if you have the time to think about your solution and profile multiple options... but the point is that memory latency is a huge hurdle to overcome. For context: A cold memory fetch is ~200 cycles. That's around 10 incorrectly-predicted branches. That's around 100 correctly-predicted branches. You need to be skipping a lot of work to justify injecting 100s of cycles of lag inside a loop of some sort. (And, of course, those situations would need to be the common, relevant case. Don't follow a 10x performance speed-up in a one-off situation at a time no-one cares about to justify a 5x slowdown in a critical, hot loop.) If you have big objects, then this might also start to become a concern. However, in those cases, a vector of pointers (or structs of pointers + metadata) would appear as a new challenger. In that case, you would only take the latency hit if you actually need to go to the object (and those objects could be held in contiguous storage, etc. etc. etc.). Chances are that, unless you have data for your specific case showing otherwise, vector will probably win. It should be the default unless you have a reason not to, and evidence to back it up.