News for hackers. Stuff that matters.
Re:Things you can’t do in Rust (and what to do instead) by Misdicorl on Saturday May 15, 2021 @11:37PM (#27170993)
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.

Re:Things you can’t do in Rust (and what to do instead) by kllrnohj on Sunday May 16, 2021 @08:37AM (#27173264)
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

Re:Things you can’t do in Rust (and what to do instead) by atq2119 on Sunday May 16, 2021 @01:09AM (#27171371)
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.