← Back to context

Comment by asdfasgasdgasdg

5 years ago

That's right. The reason why you see linked lists so much in old C stuff is (IMO) similar to the reason you see null terminated strings (and the associated bugs if you truncate incorrectly). And that's because of one of C's original sin: the failure to include size information in array objects.

There is also the claim that linked lists are better in certain types of performance sensitive code because you can sometimes avoid allocating. I don't fully understand the logic there myself but I trust that there are cases where this is true.

18 comments

asdfasgasdgasdg

Reply
flohofwoe  5 years ago

The actual reason why you see linked lists (and similar pointer-chasing data structures) so much in old code is because the entire problem of slow-vs-fast memory accesses didn't exist back then. Memory access always happened in a fixed and very low number of CPU cycles (the entire RAM essentially had L1 cache performance). The cpu-memory-gap only slowly started to widen during the 90's when CPU frequencies started to skyrocket and caches had to be added to CPUs. Unfortunately this problem still isn't as widely recognized as it should be in high-level programming circles even today.

pushrax  5 years ago

If your primary operation is inserting at a random location in the list, linked lists are faster than arrays at large sizes. You avoid having to move all the memory after the index you are modifying (to make space for the inserted element).

A linked list also avoids copying the entire array when you need to insert more elements than you have allocated space for.

  • reificator  5 years ago

    > If your primary operation is inserting at a random location in the list, linked lists are faster than arrays at large sizes. You avoid having to move all the memory after the index you are modifying (to make space for the inserted element).

    This is false. Big O notation says it should be true, you'll get marked wrong if you say arrays are faster in your algorithms & data structures final, but when you're running on actual hardware the array is faster at all sizes of n and as n becomes larger so does the gap in performance.

    Here is a talk[0] by Bjarne Stroustrop (Creator of C++) that even includes imaginary graphs demonstrating this phenomenon. If you want a visual for what the missing graph was supposed to look like, here's a similar one.[1]

    Here's another video[2] by Scott Meyers (Author of Effective C++) that goes into more detail about why this happens.

    [0]: https://www.youtube.com/watch?v=YQs6IC-vgmo [1]: https://airspeedvelocity.files.wordpress.com/2015/08/pasted_... [2]: https://www.youtube.com/watch?v=WDIkqP4JbkE

    • jodrellblank  5 years ago

      Summary of the Stroustrop video - inserting or removing an item at a point in an array of 100k items needs a linear scan from the start of the data structure to get to the point - an array does that very quickly, a linked list is much slower, lots of random memory indirection, a pointer for every list node blowing out the cache - in practice this linear scan to to the change point dominates the runtime, and arrays come out much faster.

      While the array change does need on average 50k items to be shuffled up to make room or close the gap, modern caches are very good at that.

      If the array is sorted it can be binary searched to get to the change point, which improves its performance even more, linked lists can’t do that.

      Interesting.

      4 replies →

    • pushrax  5 years ago

      I think it's also worth noting that this is specific to (common) CPU architecture where cache is sufficiently big and orders of magnitude faster than main memory, and where main memory reads and writes have similar cost.

      The tradeoff in moving memory at the end of the array vs scanning to the point of linked list insertion could be different on some existing and some hypothetical systems where these concepts may be relevant. For example, storage write cycle minimization could be a priority in rare cases.

      That said this is an excellent point about the majority of use cases. I hadn't considered the dominance of the time it takes to locate the element to modify. I've never had a reason to benchmark a linked list since even a basic idea of the effect of cache/prefetch precludes its use in every use case I've actually come across.

      Probably useful for CS education to start comparing linked lists to bubble sort. There's always a better algorithm, but here's a simple one to learn so you understand how to compare data structure performance.

  • cma  5 years ago

    Depends on element size and some other stuff, but if it is a singly linked list, and truely random insertion location, iterating to that location is N/2 on average, where inserting and copying the rest of the array is also N/2. Small elements and the array could still be much faster since they are all prefetched during the copy, vs jumping all over memory during the list iteration and potentially stalling on each for ~200 instructions waiting on main memory.