6 ms·

Understanding, and even sympathizing, with the machine's toil re: vectors vs manual linked list can separate a good engineer from a great one. We learn linked l

by andirk 4y ago

Understanding, and even sympathizing, with the machine's toil re: vectors vs manual linked list can separate a good engineer from a great one. We learn linked lists, assembly, and even machine code in Computer Science majors so that we know what's happening under the hood and can more easily surmise the runtime effects.

kibwen 4y ago
All of these are indeed important, and will eventually (one hopes) result in the student realizing that linked lists are to be avoided because of their poor mechanical sympathy resulting from their awful cache locality. Valid uses for a linked list are extremely niche. Yes, you can name some, and I can name several valid uses for bloom filters. Just because a simple linked list is easy to implement does not mean it should be used, any more than bubble sort should be used for its simplicity.
- throwawaymaths 4y ago
  Wait why do linked lists have bad cache locality? It depends on how your heap is set up. For example, you could have an allocator that gives relatively good locality by having high granularity and only bailing out if say your LL gets super long (so if your lists are usually short, they could have awesome locality)
  - AstralStorm 4y ago
    If you are in that place, you're probably using a linked list over small statically allocated memory, but you still need random ordering and fast remove or reorder.
  - duskwuff 4y ago
    That only works if you allocate lists all at once and never modify them. If there are any other allocations taking place at the same time -- say, allocations from other threads, or for other data you had to create while building the list, that locality is shot. Same goes if you insert more elements to the list later, or if you perform an operation which changes its order (like sorting it).
    - wtetzner 4y ago
      > That only works if you allocate lists all at once and never modify them. You can reorder and modify the contents of the list without losing locality.
      - duskwuff 4y ago
        I mean, if you modify the contents of the list nodes in place, sure. But at that point, you're just doing an array with extra steps. Changing any of the pointers, however, will make memory prefetch much less efficient. CPUs like linear memory access patterns; they're easy to predict. Chasing pointers is much less predictable, even if the pointers are all to the same region of memory.
        wtetzner 4y ago
        It might still be cheaper than copying the values if they’re large.
  - cerved 4y ago
    That doesn't seem to make much sense to me. LL are useful in cases where you deal with changing lists, where you'd be forced to allocate and deallocate memory often. If you know before hand the exact or approximate size of the list and it's contents you can store that continuously in memory with greater cache locality because you're not storing pointers in addition to data. Seems to me the use case of LL is perhaps as ill suited for cache locality as the structure itself
    - wtetzner 4y ago
      They’re also useful when you want to cheaply reorder nodes without copying the elements.
      - cerved 4y ago
        True. You could implement that using an array of structs where each struct contains indexes of the array to link other structures. instead of memory pointers, since they are 8 bytes in 64-bit applications. This way you get the nice properties of both linked lists and continuously allocated arrays
  - CalChris 4y ago
    If your list is short then you won't have a problem. But if your list is long then traversing it can be a major problem. For example, if your list item is page aligned like the task_struct in the Linux kernel, rescheduling the next process could traverse the process list. The process list links will be at the same page offset and associate with a restricted set of the L1/L2/L3 caches lines and thrash from memory. Worse, the TLB will thrash as well. This was actually the case for Linux until about 2000. https://www.usenix.org/legacy/publications/library/proceedings/als00/2000papers/papers/full_papers/sears/sears_html/ https://www.usenix.org/legacy/publications/library/proceedin...
- mst 4y ago
  http://trout.me.uk/lisp/vlist.pdf http://trout.me.uk/lisp/vlist.pdf
- atemerev 4y ago
  An order book in electronic trading. It is not too large (a few thousand of entries usually), but it needs to be accessed and modified extremely fast. There can be insertions and deletions anywhere, but it is strongly biased towards front. It is ordered by price, either ascending or descending. Various “ordered queue” implementations are usually a poor fit, as there are many insertions and deletions in the middle, and they need to avoid any additional latency. The same goes to vectors. Red-black trees etc. are too complex (and slow) for such a small size. So we start with a humble linked list, and optimize it (unrolled, skip search etc). But we respect linked lists, they work.
BeetleB 4y ago
> Understanding, and even sympathizing, with the machine's toil re: vectors vs manual linked list can separate a good engineer from a great one. I think your parent's point is that if you're a C++ programmer, recognizing that vectors outperform other data structures for most use cases is what separates a good engineer from a great one. Often even for things that require lookup (i.e. vector outperforming a set). During code reviews, a senior C++ programmer in my company (formerly sat in the C++ standards committee) would always demand benchmarks from the developer if they used anything else. In most cases, using representative real world data, they discovered that vectors outperformed even when the theoretical complexity of the other data structure was better. A great engineer knows the limitation of theory. Of course, my comment is only regarding C++. No guarantees that vectors are great in other languages.
- asveikau 4y ago
  > [V]ectors outperform other data structures ... even for things that require lookup (i.e. vector outperforming a set) This is something I've heard before (not often benchmarked) and it makes intuitive sense, and sometimes I've also told it to myself in order to not feel bad for writing O(n) where n is always small. But somehow, reading this snippet, I'm reminded that the vector does not maintain the semantic reminder that it's used in a key/value use case. So it has me thinking there should be a map/hashtable/dictionary interface that's really just a vector with linear lookup. Then I think, hmm, maybe the standard containers should just do that. Maybe the authors of those should have some heuristic of "when to get fancy".
  - KerrAvon 4y ago
    I think the cases where lookup is faster for a linearly scanned vector is where the hash computation overhead is greater than a linear scan. Assuming you have a good hash implementation, that should be true only for a small number of entries, where you need to determine "small" by measuring.
    - asveikau 4y ago
      I think it's about locality and quickness of compare. So if you have a small data structure and/or large cache, and the key is not complicated.

by andirk 4y ago

kibwen 4y ago

All of these are indeed important, and will eventually (one hopes) result in the student realizing that linked lists are to be avoided because of their poor mechanical sympathy resulting from their awful cache locality. Valid uses for a linked list are extremely niche. Yes, you can name some, and I can name several valid uses for bloom filters. Just because a simple linked list is easy to implement does not mean it should be used, any more than bubble sort should be used for its simplicity.

throwawaymaths 4y ago
Wait why do linked lists have bad cache locality? It depends on how your heap is set up. For example, you could have an allocator that gives relatively good locality by having high granularity and only bailing out if say your LL gets super long (so if your lists are usually short, they could have awesome locality)
- AstralStorm 4y ago
  If you are in that place, you're probably using a linked list over small statically allocated memory, but you still need random ordering and fast remove or reorder.
- duskwuff 4y ago
  That only works if you allocate lists all at once and never modify them. If there are any other allocations taking place at the same time -- say, allocations from other threads, or for other data you had to create while building the list, that locality is shot. Same goes if you insert more elements to the list later, or if you perform an operation which changes its order (like sorting it).
  - wtetzner 4y ago
    > That only works if you allocate lists all at once and never modify them. You can reorder and modify the contents of the list without losing locality.
    - duskwuff 4y ago
      I mean, if you modify the contents of the list nodes in place, sure. But at that point, you're just doing an array with extra steps. Changing any of the pointers, however, will make memory prefetch much less efficient. CPUs like linear memory access patterns; they're easy to predict. Chasing pointers is much less predictable, even if the pointers are all to the same region of memory.
      - wtetzner 4y ago
        It might still be cheaper than copying the values if they’re large.
- cerved 4y ago
  That doesn't seem to make much sense to me. LL are useful in cases where you deal with changing lists, where you'd be forced to allocate and deallocate memory often. If you know before hand the exact or approximate size of the list and it's contents you can store that continuously in memory with greater cache locality because you're not storing pointers in addition to data. Seems to me the use case of LL is perhaps as ill suited for cache locality as the structure itself
  - wtetzner 4y ago
    They’re also useful when you want to cheaply reorder nodes without copying the elements.
    - cerved 4y ago
      True. You could implement that using an array of structs where each struct contains indexes of the array to link other structures. instead of memory pointers, since they are 8 bytes in 64-bit applications. This way you get the nice properties of both linked lists and continuously allocated arrays
- CalChris 4y ago
  If your list is short then you won't have a problem. But if your list is long then traversing it can be a major problem. For example, if your list item is page aligned like the task_struct in the Linux kernel, rescheduling the next process could traverse the process list. The process list links will be at the same page offset and associate with a restricted set of the L1/L2/L3 caches lines and thrash from memory. Worse, the TLB will thrash as well. This was actually the case for Linux until about 2000. https://www.usenix.org/legacy/publications/library/proceedings/als00/2000papers/papers/full_papers/sears/sears_html/ https://www.usenix.org/legacy/publications/library/proceedin...
mst 4y ago
http://trout.me.uk/lisp/vlist.pdf http://trout.me.uk/lisp/vlist.pdf
atemerev 4y ago
An order book in electronic trading. It is not too large (a few thousand of entries usually), but it needs to be accessed and modified extremely fast. There can be insertions and deletions anywhere, but it is strongly biased towards front. It is ordered by price, either ascending or descending. Various “ordered queue” implementations are usually a poor fit, as there are many insertions and deletions in the middle, and they need to avoid any additional latency. The same goes to vectors. Red-black trees etc. are too complex (and slow) for such a small size. So we start with a humble linked list, and optimize it (unrolled, skip search etc). But we respect linked lists, they work.

BeetleB 4y ago

> Understanding, and even sympathizing, with the machine's toil re: vectors vs manual linked list can separate a good engineer from a great one. I think your parent's point is that if you're a C++ programmer, recognizing that vectors outperform other data structures for most use cases is what separates a good engineer from a great one. Often even for things that require lookup (i.e. vector outperforming a set). During code reviews, a senior C++ programmer in my company (formerly sat in the C++ standards committee) would always demand benchmarks from the developer if they used anything else. In most cases, using representative real world data, they discovered that vectors outperformed even when the theoretical complexity of the other data structure was better. A great engineer knows the limitation of theory. Of course, my comment is only regarding C++. No guarantees that vectors are great in other languages.

asveikau 4y ago
> [V]ectors outperform other data structures ... even for things that require lookup (i.e. vector outperforming a set) This is something I've heard before (not often benchmarked) and it makes intuitive sense, and sometimes I've also told it to myself in order to not feel bad for writing O(n) where n is always small. But somehow, reading this snippet, I'm reminded that the vector does not maintain the semantic reminder that it's used in a key/value use case. So it has me thinking there should be a map/hashtable/dictionary interface that's really just a vector with linear lookup. Then I think, hmm, maybe the standard containers should just do that. Maybe the authors of those should have some heuristic of "when to get fancy".
- KerrAvon 4y ago
  I think the cases where lookup is faster for a linearly scanned vector is where the hash computation overhead is greater than a linear scan. Assuming you have a good hash implementation, that should be true only for a small number of entries, where you need to determine "small" by measuring.
  - asveikau 4y ago
    I think it's about locality and quickness of compare. So if you have a small data structure and/or large cache, and the key is not complicated.