3 ms·

I think one important variable to tune would be the element size (since supposedly linked list shines more with bigger data). Curious to see what the numbers ar

I think one important variable to tune would be the element size (since supposedly linked list shines more with bigger data). Curious to see what the numbers are at 100b/1kb My guess is that the linked list impl remains almost the same while vec sees a linear ish slowdown.

atq2119 5y ago
That's true. And there is seriously optimized software out there using linked lists (e.g. in the Linux kernel). However, with bigger data in my experience a very good solution is often to have a vector of pointers to the actual data. This loses some locality of course, but during traversal the fact that you don't have dependencies between iterations can still be a win.
kllrnohj 5y ago
Oh, absolutely! Linked lists do have a quite useful strength in that they are agnostic to data size and, potentially more importantly, that pointers to the data are not invalidated when a linked list changes size as they are in vector. Both those properties combined make linked lists good data structures for holding large data as more of an allocator than a list type usage. Where it's not the O(1) inserts-anywhere that matters so much as the O(data-never-moves) that does. But since you asked I adjusted the benchmark to instead contain a 100byte & 1kb payload (just an array of ints). And in the loop I just use the first number of the array in the summation. I assumed an iteration isn't accessing the entire payload but say instead an ID or whatever. I also added a vector that is pointers to the data instead of the data itself (always a new allocation, none of the pointers are the same) For 100 bytes: Vector; payload sizeof=100 of count 100 took 142ns Vector-of-pointers; payload sizeof=8 of count 100 took 150ns Linked-list; payload sizeof=100 of count 100 took 180ns Vector; payload sizeof=100 of count 10,000 took 18,796ns Vector-of-pointers; payload sizeof=8 of count 10,000 took 8,670ns Linked-list; payload sizeof=100 of count 10,000 took 32,853ns Gap shrunk, but possibly not by as much as you would have expected. For 1kb Results: Vector; payload sizeof=1000 of count 100 took 1137ns Vector-of-pointers; payload sizeof=8 of count 100 took 549ns Linked-list; payload sizeof=1000 of count 100 took 387ns Vector; payload sizeof=1000 of count 10,000 took 120,709ns Vector-of-pointers; payload sizeof=8 of count 10,000 took 10,681ns Linked-list; payload sizeof=1000 of count 10,000 took 105,927ns Linked-list finally manages to pass up vector, but then vector of pointers runs away from linked-lists in the 1kb test. Think about it like this: Traversal speeds of linked lists are bottlenecked by memory latency. Traversal speeds of vectors are bottlenecked by memory bandwidth. Only one of those metrics has been improving over the years. Code: https://paste.ofcode.org/hYTf6PYPJegWLReSGQyUBg https://paste.ofcode.org/hYTf6PYPJegWLReSGQyUBg

atq2119 5y ago

That's true. And there is seriously optimized software out there using linked lists (e.g. in the Linux kernel). However, with bigger data in my experience a very good solution is often to have a vector of pointers to the actual data. This loses some locality of course, but during traversal the fact that you don't have dependencies between iterations can still be a win.

kllrnohj 5y ago

Oh, absolutely! Linked lists do have a quite useful strength in that they are agnostic to data size and, potentially more importantly, that pointers to the data are not invalidated when a linked list changes size as they are in vector. Both those properties combined make linked lists good data structures for holding large data as more of an allocator than a list type usage. Where it's not the O(1) inserts-anywhere that matters so much as the O(data-never-moves) that does. But since you asked I adjusted the benchmark to instead contain a 100byte & 1kb payload (just an array of ints). And in the loop I just use the first number of the array in the summation. I assumed an iteration isn't accessing the entire payload but say instead an ID or whatever. I also added a vector that is pointers to the data instead of the data itself (always a new allocation, none of the pointers are the same) For 100 bytes: Vector; payload sizeof=100 of count 100 took 142ns Vector-of-pointers; payload sizeof=8 of count 100 took 150ns Linked-list; payload sizeof=100 of count 100 took 180ns Vector; payload sizeof=100 of count 10,000 took 18,796ns Vector-of-pointers; payload sizeof=8 of count 10,000 took 8,670ns Linked-list; payload sizeof=100 of count 10,000 took 32,853ns Gap shrunk, but possibly not by as much as you would have expected. For 1kb Results: Vector; payload sizeof=1000 of count 100 took 1137ns Vector-of-pointers; payload sizeof=8 of count 100 took 549ns Linked-list; payload sizeof=1000 of count 100 took 387ns Vector; payload sizeof=1000 of count 10,000 took 120,709ns Vector-of-pointers; payload sizeof=8 of count 10,000 took 10,681ns Linked-list; payload sizeof=1000 of count 10,000 took 105,927ns Linked-list finally manages to pass up vector, but then vector of pointers runs away from linked-lists in the 1kb test. Think about it like this: Traversal speeds of linked lists are bottlenecked by memory latency. Traversal speeds of vectors are bottlenecked by memory bandwidth. Only one of those metrics has been improving over the years. Code: https://paste.ofcode.org/hYTf6PYPJegWLReSGQyUBg https://paste.ofcode.org/hYTf6PYPJegWLReSGQyUBg