10 ms·

Never head of that, though I don't use C much. Are you referring to the CPU cache?

saagarjha 6y ago
Yeah, linked lists are bad for the data cache since each element is in some totally random area of memory and thus less likely to be in a cache. Whereas for a linear array the data is next to each other and can be cached effectively and accesses can be easily predicted.
- philsnow 6y ago
  You can also force-align (with padding if necessary) your structures to be along whatever boundaries make sense for your processor's cache lines. Ensuring an oft-loaded structure always fits inside a single cache line (instead of splaying across ~1.9 cache lines on average) is good not only for fitting lots of those structures into your L1 but for not blowing out cache bandwidth (read _and_ write, if you're modifying them).
  - a_t48 6y ago
    It's much more difficult to prefetch them, though - if you're traversing a large list it misses the cache every time, rather than just the first element. (someone please correct me if I'm wrong)
    - asdfasgasdgasdg 6y 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.
      - pushrax 6y 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.
        cma 6y 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.
        saagarjha 6y ago
        You can imagine a linked list whose “API” is “take this node and insert after it”.
        cma 6y ago
        If a bunch of insertions happen like that, based on some other data structure, and then a periodic iteration eventually happens at some point, you could also imagine an array version being batching together all the array inserts in another simple array and applying them all at once before iteration.
        whimsicalism 6y ago
        B-tree would be faster than either
        reificator 6y 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 https://www.youtube.com/watch?v=YQs6IC-vgmo [1]: https://airspeedvelocity.files.wordpress.com/2015/08/pasted_image_8_2_15__1_17_pm.png https://airspeedvelocity.files.wordpress.com/2015/08/pasted_... [2]: https://www.youtube.com/watch?v=WDIkqP4JbkE https://www.youtube.com/watch?v=WDIkqP4JbkE
- pushrax 6y ago
  Expanding on this: usually linked lists allocate each element with a separate malloc() on the heap, so they end up all over the place in memory. You could, in principle, allocate your linked list out of contiguous memory in such a way that sequentially reading the list doesn't cause so many page accesses. That would itself be a complicated data structure to maintain, so simply using a linear array is often the right tradeoff.
  - AlotOfReading 6y ago
    That's just a slab allocator. They're not what I'd call trivial, but still simple enough to be common in small projects and CS homework. I agree that an array is still generally simpler though.
    - pushrax 6y ago
      Once you are implementing your own allocator you need to worry about fragmentation under many operations, which would be the majority of the complexity.
- yencabulator 6y ago
  Some 20 years ago, when I was a kernel developer with high performance requirements, my favorite data structure was a linked list of smallish arrays. Each array was small enough to be cheap to completely rewrite on insert/delete, if you needed to e.g. preserve insertion order; most of the time, it was enough to preserve order only across the linked list, treat each array like a hash table slot, or sort at consumption time.
  - skavi 6y ago
    I’ve considered making a vector sorta thing implemented as a linked list of arrays. Assuming you sized the arrays to fit well inside the CPU cache, are there really many tradeoffs?
    - yencabulator 6y ago
      Even if the array overflows the cache, it's not too bad for most access patterns. CPUs will easily prefetch data on a linear scan, so the "second half of the array" will most definitely be in cache by the time you get there. And a linear scan-once shouldn't even evict too much other stuff out of the cache. In practice, I would let benchmarks decide the array size. Modern CPUs are surprisingly good at prefetching even linked lists, and x86 works weird out-of-order magic and speculation while waiting for memory. My rules of two thumbs were 1) where performance really matters, don't trust your intuition, program and benchmark alternative implementations 2) don't trust microbenchmarks, e.g. total icache pressure changes whether inlining is good or not.
    - jacoblambda 6y ago
      It sounds like you are talking about an unrolled linked list[1]. I'd argue in most cases that while they are better than linked lists in just about every way (except data objects larger than the cache line), in most cases there is a better data structure to use. I'd find that the hashed array tree[2] would likely be a better/more versatile data structure solely due to the improved lookup time. [1]: https://en.wikipedia.org/wiki/Unrolled_linked_list https://en.wikipedia.org/wiki/Unrolled_linked_list [2]: https://en.wikipedia.org/wiki/Hashed_array_tree https://en.wikipedia.org/wiki/Hashed_array_tree
netheril96 6y ago
The language doesn't matter. In almost all languages linked list has worse performance due to cache.
- pfundstein 6y ago
  Forgive me but are linked lists common in other languages?
  - smabie 6y ago
    Super common? Main data structure in Scala, any kind of Lisp, Haskell, Erlang, etc. Linked lists are a functional programmer's goto data structure.
    - pfundstein 6y ago
      Well that would explain why I've only encountered them in C.
      - azernik 6y ago
        C is the only language where they're called "linked lists"; everything else just calls them "lists".
        pjmlp 6y ago
        Nope, plenty of literature refers to them as linked lists. Here is an article about them in Modula-2, to use a language of similar age as C. https://www.modula2.org/tutor/chapter11.php https://www.modula2.org/tutor/chapter11.php
        azernik 6y ago
        I was being loose with the words "everything" and "only". GP comment was curious about why they've only heard about "linked lists" in a language, C, which like Modula-2 does not use them as the basic standard library collections type. When you have to implement linked lists yourself if you want to use them, you're always going to refer to them by implementation detail. In the vast majority of cases where they're used, though, it's as the fundamental standard library collection, and in that case they're usually just called Lists without telling the caller about their implementation. (This idiom is true to the point that the Python implementers feel the need to point out that CPython uses arrays to implement the list type, as they feel that this would be unexpected to users of other languages that call their basic collections type a "list".)

Yeah, linked lists are bad for the data cache since each element is in some totally random area of memory and thus less likely to be in a cache. Whereas for a linear array the data is next to each other and can be cached effectively and accesses can be easily predicted.

philsnow 6y ago
You can also force-align (with padding if necessary) your structures to be along whatever boundaries make sense for your processor's cache lines. Ensuring an oft-loaded structure always fits inside a single cache line (instead of splaying across ~1.9 cache lines on average) is good not only for fitting lots of those structures into your L1 but for not blowing out cache bandwidth (read _and_ write, if you're modifying them).
- a_t48 6y ago
  It's much more difficult to prefetch them, though - if you're traversing a large list it misses the cache every time, rather than just the first element. (someone please correct me if I'm wrong)
  - asdfasgasdgasdg 6y 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.
    - pushrax 6y 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.
      - cma 6y 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.
        saagarjha 6y ago
        You can imagine a linked list whose “API” is “take this node and insert after it”.
        cma 6y ago
        If a bunch of insertions happen like that, based on some other data structure, and then a periodic iteration eventually happens at some point, you could also imagine an array version being batching together all the array inserts in another simple array and applying them all at once before iteration.
      - whimsicalism 6y ago
        B-tree would be faster than either
      - reificator 6y 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 https://www.youtube.com/watch?v=YQs6IC-vgmo [1]: https://airspeedvelocity.files.wordpress.com/2015/08/pasted_image_8_2_15__1_17_pm.png https://airspeedvelocity.files.wordpress.com/2015/08/pasted_... [2]: https://www.youtube.com/watch?v=WDIkqP4JbkE https://www.youtube.com/watch?v=WDIkqP4JbkE
pushrax 6y ago
Expanding on this: usually linked lists allocate each element with a separate malloc() on the heap, so they end up all over the place in memory. You could, in principle, allocate your linked list out of contiguous memory in such a way that sequentially reading the list doesn't cause so many page accesses. That would itself be a complicated data structure to maintain, so simply using a linear array is often the right tradeoff.
- AlotOfReading 6y ago
  That's just a slab allocator. They're not what I'd call trivial, but still simple enough to be common in small projects and CS homework. I agree that an array is still generally simpler though.
  - pushrax 6y ago
    Once you are implementing your own allocator you need to worry about fragmentation under many operations, which would be the majority of the complexity.
yencabulator 6y ago
Some 20 years ago, when I was a kernel developer with high performance requirements, my favorite data structure was a linked list of smallish arrays. Each array was small enough to be cheap to completely rewrite on insert/delete, if you needed to e.g. preserve insertion order; most of the time, it was enough to preserve order only across the linked list, treat each array like a hash table slot, or sort at consumption time.
- skavi 6y ago
  I’ve considered making a vector sorta thing implemented as a linked list of arrays. Assuming you sized the arrays to fit well inside the CPU cache, are there really many tradeoffs?
  - yencabulator 6y ago
    Even if the array overflows the cache, it's not too bad for most access patterns. CPUs will easily prefetch data on a linear scan, so the "second half of the array" will most definitely be in cache by the time you get there. And a linear scan-once shouldn't even evict too much other stuff out of the cache. In practice, I would let benchmarks decide the array size. Modern CPUs are surprisingly good at prefetching even linked lists, and x86 works weird out-of-order magic and speculation while waiting for memory. My rules of two thumbs were 1) where performance really matters, don't trust your intuition, program and benchmark alternative implementations 2) don't trust microbenchmarks, e.g. total icache pressure changes whether inlining is good or not.
  - jacoblambda 6y ago
    It sounds like you are talking about an unrolled linked list[1]. I'd argue in most cases that while they are better than linked lists in just about every way (except data objects larger than the cache line), in most cases there is a better data structure to use. I'd find that the hashed array tree[2] would likely be a better/more versatile data structure solely due to the improved lookup time. [1]: https://en.wikipedia.org/wiki/Unrolled_linked_list https://en.wikipedia.org/wiki/Unrolled_linked_list [2]: https://en.wikipedia.org/wiki/Hashed_array_tree https://en.wikipedia.org/wiki/Hashed_array_tree

netheril96 6y ago

The language doesn't matter. In almost all languages linked list has worse performance due to cache.

pfundstein 6y ago
Forgive me but are linked lists common in other languages?
- smabie 6y ago
  Super common? Main data structure in Scala, any kind of Lisp, Haskell, Erlang, etc. Linked lists are a functional programmer's goto data structure.
  - pfundstein 6y ago
    Well that would explain why I've only encountered them in C.
    - azernik 6y ago
      C is the only language where they're called "linked lists"; everything else just calls them "lists".
      - pjmlp 6y ago
        Nope, plenty of literature refers to them as linked lists. Here is an article about them in Modula-2, to use a language of similar age as C. https://www.modula2.org/tutor/chapter11.php https://www.modula2.org/tutor/chapter11.php
        azernik 6y ago
        I was being loose with the words "everything" and "only". GP comment was curious about why they've only heard about "linked lists" in a language, C, which like Modula-2 does not use them as the basic standard library collections type. When you have to implement linked lists yourself if you want to use them, you're always going to refer to them by implementation detail. In the vast majority of cases where they're used, though, it's as the fundamental standard library collection, and in that case they're usually just called Lists without telling the caller about their implementation. (This idiom is true to the point that the Python implementers feel the need to point out that CPython uses arrays to implement the list type, as they feel that this would be unexpected to users of other languages that call their basic collections type a "list".)