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.
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.
My guess is that the linked list impl remains almost the same while vec sees a linear ish slowdown.