6 ms·

For CPU bound stuff, the 80%/20% rule is to learn that an array/vector is typically much faster than a linked list, and this is due to how CPU caches work. (thi

For CPU bound stuff, the 80%/20% rule is to learn that an array/vector is typically much faster than a linked list, and this is due to how CPU caches work. (this is thinking about how much information is being moved around, but between the processor and RAM) Also, for parallel stuff: locks tend to be bottlenecks. Writing parallel code is tricky overall. Stick to libraries that provide high level lockless data structures like mpsc queues if possible.

adrianN 8y ago
Who uses linked lists? Outside of niche algorithms that splice lots of lists together there are practically zero occasions where linked lists beat dynamic arrays.
- deleted 8y ago
  [deleted]
- hvidgaard 8y ago
  Linked lists are very common, especially for non performance critical code. Dynamic arrays either carry a large performance cost at expansion, or is rather complicated to implement in a amortized way. Linked list in comparison is simple, and since it doesn't require a large continues block of memory, the memory pressure is smaller.
- Matt3o12_ 8y ago
  A dynamic array has an average (armotized) time of O(1) but a worst case of O(n) – whenever your next insert is longer then the size of the list. Furthermore, it needs a lot of ram whenever copying elements. A linked list is always O(1) and its ram usage is consistent (although not better – normally it is twice or three times as big). A linked list is basically only better on embedded systems because you have much better knowledge about the used ram/runtime. It’s also useful if you have a very large data structure and you need real time performance (a lag of a few hundred milliseconds are unacceptable for some applications such games or financial applications). But whenever your insert becomes too expensive, a linked list is probably not the best choice either and you should consider why your data structure is so big. Lastly a linked list is rather simple to implement but that’s also only really useful for embedded stuff.
- roel_v 8y ago
  I think it's a cultural thing rather than a technical one. I haven't used a linked list in 15+ years, because in C++ a std::vector is the 'default'. Before that, I wrote (some) C for Gnome, and the 'default' in Glib is a linked list. I don't know/remember if there is a reasonable, easy to use data structure that wraps a dynamically allocated array in Glib, but most of the 'sample' code at the time used the glib list. So that's what everybody kept on doing.
  - pm215 8y ago
    I think GArray is the wrapper for a dynamically allocated array.
    - roel_v 8y ago
      Ah yes it is, thank you. I should have know about this 15 years ago :)
  - blattimwind 8y ago
    I've seen LinkedList often used as the go-to list in Java, instead of ArrayList. They're also common in C, for example, a huge number of structures in the Linux kernel are linked lists.
    - majewsky 8y ago
      > for example, a huge number of structures in the Linux kernel are linked lists. Which allocator is used for these? I'm not familiar with the Linux kernel, but since there is no malloc() in the kernel, I would guess that they allocate from an arena that's going to be page-aligned and thus exhibit the same locality characteristics as a vector.
      - blattimwind 8y ago
        Oh, they have malloc, it's just kalled kmalloc.
- ramchip 8y ago
  Pretty much anyone using a functional language or immutable data structures.
  - Sharlin 8y ago
    The default immutable "list" types in current mainstream functional languages (eg. Scala, Clojure) have much better performance characteristics than naive head:tail linked lists. A typical implementation is a n-ary balanced tree where n is typically on the order of 100, making operations "effectively O(1)" and also keeping cache behavior acceptable in many common cases.
    - twanvl 8y ago
      Haskell still uses head:tail linked lists a lot. However, a lot of effort has been spent in optimizing away the data creation entirely. For example `sum [1..100]` will not actually allocate the list in memory.
- htgb 8y ago
  What about any time you're working with frequent adds/deletes in arbitrary positions, rather than just at the end of the list? That's not a "niche algorithm" to me, but rather a reasonable use case. The add and delete operations should be faster than for the array case. (Not that I actually use linked list much myself, but I mean I see the use of them.)
  - twanvl 8y ago
    Even then, linked lists are only faster than arrays if the list has at least 100s of items.
    - geezerjay 8y ago
      That's pretty much a standard use case. IIRC the rule of thumb is that if the container isn't expected to hold many elements then the default choice is to use std::vector no questions asked. Otherwise, random insertions and deletions in a sizable container requires a std::list.
  - adrianN 8y ago
    If the list fits in cache it is often to faster to insert into a dynamic array and shift the elements. It of course depends a bit on the allocator that you use how expensive creating a new list node is.
    - htgb 8y ago
      That's a good point, thanks.
- chrisseaton 8y ago
  > Who uses linked lists? Isn't the linked list pretty much the main collection data structure in the Linux kernel?
- jawilson2 8y ago
  I use deques A LOT, e.g. interthread messaging, and decaying/windowed time series calculations. Like, if you want a running mean of the last 250ms, you put a timestamp and value pair in the back a deque, and every update you check the front of the deque to see if it should be popped (i.e. the timestamp is older than 250ms), and the mean updated. I suppose you could use a circular buffer with a vector as well, but you have to guess what your max size will ever be, or handle dynamic resizing. Maybe it would be worth it in some circumstances.
  - adrianN 8y ago
    If those lists are anywhere on your hot path benchmarking with a deque build from two vectors, or a circular buffer as you suggested, would be worthwhile imho. The constants in linked lists are such that the O(1) operations are often slower than the O(n) operations in vectors, at least for lists that fit in cache, and depending on your allocator etc. Chasing pointers to more or less random memory locations is pretty much the worst case workload for a modern CPU.
- deleted 8y ago
  [deleted]

adrianN 8y ago

Who uses linked lists? Outside of niche algorithms that splice lots of lists together there are practically zero occasions where linked lists beat dynamic arrays.

deleted 8y ago
[deleted]
hvidgaard 8y ago
Linked lists are very common, especially for non performance critical code. Dynamic arrays either carry a large performance cost at expansion, or is rather complicated to implement in a amortized way. Linked list in comparison is simple, and since it doesn't require a large continues block of memory, the memory pressure is smaller.
Matt3o12_ 8y ago
A dynamic array has an average (armotized) time of O(1) but a worst case of O(n) – whenever your next insert is longer then the size of the list. Furthermore, it needs a lot of ram whenever copying elements. A linked list is always O(1) and its ram usage is consistent (although not better – normally it is twice or three times as big). A linked list is basically only better on embedded systems because you have much better knowledge about the used ram/runtime. It’s also useful if you have a very large data structure and you need real time performance (a lag of a few hundred milliseconds are unacceptable for some applications such games or financial applications). But whenever your insert becomes too expensive, a linked list is probably not the best choice either and you should consider why your data structure is so big. Lastly a linked list is rather simple to implement but that’s also only really useful for embedded stuff.
roel_v 8y ago
I think it's a cultural thing rather than a technical one. I haven't used a linked list in 15+ years, because in C++ a std::vector is the 'default'. Before that, I wrote (some) C for Gnome, and the 'default' in Glib is a linked list. I don't know/remember if there is a reasonable, easy to use data structure that wraps a dynamically allocated array in Glib, but most of the 'sample' code at the time used the glib list. So that's what everybody kept on doing.
- pm215 8y ago
  I think GArray is the wrapper for a dynamically allocated array.
  - roel_v 8y ago
    Ah yes it is, thank you. I should have know about this 15 years ago :)
- blattimwind 8y ago
  I've seen LinkedList often used as the go-to list in Java, instead of ArrayList. They're also common in C, for example, a huge number of structures in the Linux kernel are linked lists.
  - majewsky 8y ago
    > for example, a huge number of structures in the Linux kernel are linked lists. Which allocator is used for these? I'm not familiar with the Linux kernel, but since there is no malloc() in the kernel, I would guess that they allocate from an arena that's going to be page-aligned and thus exhibit the same locality characteristics as a vector.
    - blattimwind 8y ago
      Oh, they have malloc, it's just kalled kmalloc.
ramchip 8y ago
Pretty much anyone using a functional language or immutable data structures.
- Sharlin 8y ago
  The default immutable "list" types in current mainstream functional languages (eg. Scala, Clojure) have much better performance characteristics than naive head:tail linked lists. A typical implementation is a n-ary balanced tree where n is typically on the order of 100, making operations "effectively O(1)" and also keeping cache behavior acceptable in many common cases.
  - twanvl 8y ago
    Haskell still uses head:tail linked lists a lot. However, a lot of effort has been spent in optimizing away the data creation entirely. For example `sum [1..100]` will not actually allocate the list in memory.
htgb 8y ago
What about any time you're working with frequent adds/deletes in arbitrary positions, rather than just at the end of the list? That's not a "niche algorithm" to me, but rather a reasonable use case. The add and delete operations should be faster than for the array case. (Not that I actually use linked list much myself, but I mean I see the use of them.)
- twanvl 8y ago
  Even then, linked lists are only faster than arrays if the list has at least 100s of items.
  - geezerjay 8y ago
    That's pretty much a standard use case. IIRC the rule of thumb is that if the container isn't expected to hold many elements then the default choice is to use std::vector no questions asked. Otherwise, random insertions and deletions in a sizable container requires a std::list.
- adrianN 8y ago
  If the list fits in cache it is often to faster to insert into a dynamic array and shift the elements. It of course depends a bit on the allocator that you use how expensive creating a new list node is.
  - htgb 8y ago
    That's a good point, thanks.
chrisseaton 8y ago
> Who uses linked lists? Isn't the linked list pretty much the main collection data structure in the Linux kernel?
jawilson2 8y ago
I use deques A LOT, e.g. interthread messaging, and decaying/windowed time series calculations. Like, if you want a running mean of the last 250ms, you put a timestamp and value pair in the back a deque, and every update you check the front of the deque to see if it should be popped (i.e. the timestamp is older than 250ms), and the mean updated. I suppose you could use a circular buffer with a vector as well, but you have to guess what your max size will ever be, or handle dynamic resizing. Maybe it would be worth it in some circumstances.
- adrianN 8y ago
  If those lists are anywhere on your hot path benchmarking with a deque build from two vectors, or a circular buffer as you suggested, would be worthwhile imho. The constants in linked lists are such that the O(1) operations are often slower than the O(n) operations in vectors, at least for lists that fit in cache, and depending on your allocator etc. Chasing pointers to more or less random memory locations is pretty much the worst case workload for a modern CPU.
deleted 8y ago
[deleted]