9 ms·

It's true that they have a high constant factor, but I think it's too harsh to say they are not useful. One could also say that linked-lists don't match the me

by willtim 10y ago

It's true that they have a high constant factor, but I think it's too harsh to say they are not useful. One could also say that linked-lists don't match the memory model of real hardware.

dom0 10y ago
> One could also say that linked-lists don't match the memory model of real hardware. They don't, and they almost always perform (much) worse.
- qwertyuiop924 10y ago
  True. But they're also very simple. It's okay to lean on the hardware a bit, provided you're careful: most programmers don't have to squeeze maximal performace out of the hardware, just good enough performance. The extra code you need to make arrays work may not be worth the speed boost. Also, if you're working in an HLL, investigate your implementation details. In Common Lisp, for example, a lot of work has been put into making LLs as fast as possible: If you create a list with QUOTE (such lists are immutable), then thanks to an optimization called CDR-coding, you'll get a data layout very similar to an array under the hood. OTOH, it is important to understand why LL perf isn't actually what the textbooks claim, and to consider using a different structure in contexts where performance matters. Just don't go too far the other way, either: LLs aren't dead just yet.
  - dom0 10y ago
    I believe (intrusive, as they usually are) LLs are so prevalent in C applications mainly because they are the simplest-ever list structure where insertion and deletion of items is just a no-brainer to implement in a couple lines of C macros. They are also inherently self-describing (ie. you don't need to pass around anything except one pointer). And this is totally fine in many places. However, when the list is frequently (ie. performance is relevant) used, then it's likely that a LL is not the right choice. And usually one notices that in these cases no LL is used. For example, one might use a LL for a list of drivers, while eg. directory entries will be kept in a hash-table, tree or trie.
    - qwertyuiop924 10y ago
      ...sounds about right.
- willtim 10y ago
  The context here is of course persistent data structures. Linked-lists permit very efficient structural sharing.
  - geocar 10y ago
    So do real arrays on real hardware (pagetable trie). Small arrays are contiguous so memcpy is fast. For large arrays, if you create a dummy file (or uses a memfd) you can mmap a region, and then copy it by mmaping the same region with the appropriate flags. You can resize (grow) it almost as easily. They're so much faster than linked lists, that there's no (performance) reason to use linked-lists on real hardware.
    - chii 10y ago
      except when you want fast prepending.
      - dom0 10y ago
        There are many strategies to deal with that efficiently. Eg. negative indices (having memory before index 0), append-and-reverse. You can also map memory before an existing mapping, but it's a bit system-and-platform dependent. (But an entirely feasible thing to do). Naively you can also grow-and-shift or copy ... the first one is actually incredibly fast due to perfect locality, and also very simple to implement. It's still, technically, O(n^2) when building a list, so it's usually a better idea to go for append-and-reverse (which works outside the actual list implementation). Normally that's not a problem at all, and often no reversal has to be materialized.
      - geocar 10y ago
        If you know the format you want, and read infrequently, just implement it as an append and read it backwards. If you have frequent reads, you can also consider writing your data to a file (or a memfd), and then using mmap to construct the memory layout you want. You will then see that prepend is worse-case log^3 (depth of the pagetable, assuming you have to keep moving the whole thing) time, which is much better than finger trees, and if you prepend often you can make it constant time (by choosing a high start virtual address: remember, there's 64 bits of address but only 48 bits of memory, so you can have 64k big objects without much work) which makes it faster than linked lists. Another idea: use VMX extensions and collaborate between each layer to trade a lower constant mean and coefficient to parameterise max to log^k. Gains here might require very big data sets though.
- mojomark 10y ago
  >they almost always perform (much) worse. 'Much worse' relative to what exactly?
  - geocar 10y ago
    Than real arrays, which are backed by a pagetable trie.

by willtim 10y ago

It's true that they have a high constant factor, but I think it's too harsh to say they are not useful. One could also say that linked-lists don't match the memory model of real hardware.

dom0 10y ago

> One could also say that linked-lists don't match the memory model of real hardware. They don't, and they almost always perform (much) worse.

qwertyuiop924 10y ago
True. But they're also very simple. It's okay to lean on the hardware a bit, provided you're careful: most programmers don't have to squeeze maximal performace out of the hardware, just good enough performance. The extra code you need to make arrays work may not be worth the speed boost. Also, if you're working in an HLL, investigate your implementation details. In Common Lisp, for example, a lot of work has been put into making LLs as fast as possible: If you create a list with QUOTE (such lists are immutable), then thanks to an optimization called CDR-coding, you'll get a data layout very similar to an array under the hood. OTOH, it is important to understand why LL perf isn't actually what the textbooks claim, and to consider using a different structure in contexts where performance matters. Just don't go too far the other way, either: LLs aren't dead just yet.
- dom0 10y ago
  I believe (intrusive, as they usually are) LLs are so prevalent in C applications mainly because they are the simplest-ever list structure where insertion and deletion of items is just a no-brainer to implement in a couple lines of C macros. They are also inherently self-describing (ie. you don't need to pass around anything except one pointer). And this is totally fine in many places. However, when the list is frequently (ie. performance is relevant) used, then it's likely that a LL is not the right choice. And usually one notices that in these cases no LL is used. For example, one might use a LL for a list of drivers, while eg. directory entries will be kept in a hash-table, tree or trie.
  - qwertyuiop924 10y ago
    ...sounds about right.
willtim 10y ago
The context here is of course persistent data structures. Linked-lists permit very efficient structural sharing.
- geocar 10y ago
  So do real arrays on real hardware (pagetable trie). Small arrays are contiguous so memcpy is fast. For large arrays, if you create a dummy file (or uses a memfd) you can mmap a region, and then copy it by mmaping the same region with the appropriate flags. You can resize (grow) it almost as easily. They're so much faster than linked lists, that there's no (performance) reason to use linked-lists on real hardware.
  - chii 10y ago
    except when you want fast prepending.
    - dom0 10y ago
      There are many strategies to deal with that efficiently. Eg. negative indices (having memory before index 0), append-and-reverse. You can also map memory before an existing mapping, but it's a bit system-and-platform dependent. (But an entirely feasible thing to do). Naively you can also grow-and-shift or copy ... the first one is actually incredibly fast due to perfect locality, and also very simple to implement. It's still, technically, O(n^2) when building a list, so it's usually a better idea to go for append-and-reverse (which works outside the actual list implementation). Normally that's not a problem at all, and often no reversal has to be materialized.
    - geocar 10y ago
      If you know the format you want, and read infrequently, just implement it as an append and read it backwards. If you have frequent reads, you can also consider writing your data to a file (or a memfd), and then using mmap to construct the memory layout you want. You will then see that prepend is worse-case log^3 (depth of the pagetable, assuming you have to keep moving the whole thing) time, which is much better than finger trees, and if you prepend often you can make it constant time (by choosing a high start virtual address: remember, there's 64 bits of address but only 48 bits of memory, so you can have 64k big objects without much work) which makes it faster than linked lists. Another idea: use VMX extensions and collaborate between each layer to trade a lower constant mean and coefficient to parameterise max to log^k. Gains here might require very big data sets though.
mojomark 10y ago
>they almost always perform (much) worse. 'Much worse' relative to what exactly?
- geocar 10y ago
  Than real arrays, which are backed by a pagetable trie.