6 ms·

Why would one ever prefer a linked list over a dynamic array? I know about the asymptotic performance, but if you take actual memory performance into account (l

Why would one ever prefer a linked list over a dynamic array? I know about the asymptotic performance, but if you take actual memory performance into account (locality, cache, pointers are slow, etc), it seems dynamic arrays should be simpler and perform better.

dozzie 9y ago
Because (doubly) linked lists can do something an array cannot? Like join operations in O(1)? Or removing an arbitrary element in O(1) once you have its handle?
- blibble 9y ago
  if it's unordered (like you'd expect a list of sockets to be) you can get O(1) removal for an array by swapping the end item into the removed slot
  - dozzie 9y ago
    ...unless something else holds a pointer to the handle you're swapping with.
    - blibble 9y ago
      kernels don't tend to give userspace raw pointers into kernel memory
      - dozzie 9y ago
        But kernels tend to give raw pointers to other kernel code.
        blibble 9y ago
        a good chunk of the fun in kernel code is maintaining the various layers of self-referential lists and dealing with the cleanup
    - staticassertion 9y ago
      This is already a problem if you're removing an item, regardless of whether it's done with swap remove or not.
      - toast0 9y ago
        For the item you're removing, you are presumably removing it because all handles have been closed. But the item you're potentially swapping with may certainly have open handles.
        staticassertion 9y ago
        True.
bmon 9y ago
Insertion and deletion are prime examples, often requiring you to move large chunks of memory. The same operation just requires pointer changes (after finding where you want to insert or delete). I think in this example it would be common to be removing structs from the center of the list.
- signa11 9y ago
  > Insertion and deletion are prime examples, often requiring you to move large chunks of memory. on modern cpu's with huge caches, i seriously doubt this claim. fwiw, i have played around with synthetic problems where: i insert sequence of random integers into a sorted sequence, then remove those elements one by one as determined by a random sequence of positions. and almost always, vectors outperform lists by at least couple of orders of magnitude. or to put it another way, it is almost never about either lists / vectors or something else, and boils down to couple of 'rules' e.g. access data predictably (avoid trashing the cache), keep data compact (more cache utilization) etc. etc.
  - jstimpfle 9y ago
    > i insert sequence of random integers into a sorted sequence, then remove those elements one by one as determined by a random sequence of positions. Which means that you scan the list twice for each node. First for insertion and then for deletion. Starting at maybe a hundred that would be much more efficient with a balanced search tree. They have a good Red-black tree in Linux. But if it's only arrays vs lists - with linked lists, pointers to items are never invalidated. With dynamic arrays, they are. Dynamic arrays are fine for plain old data arrays. But it's harder for data that has "identity" and is frequently mutated. And if a node is in multiple lists, I guess arrays are out. You'd need to store the data redundantly. Extra bad if you need atomic mutations.
  - yongjik 9y ago
    Well on a 64-bit machine each node of a singly-linked list of integers will be 16 bytes (8 byte pointer + 4 byte integer + 4 byte for padding). That's 300% overhead. Becomes 500% for doubly-linked lists. So it's not surprising that linked lists perform very poorly in such circumstances.
SamReidHughes 9y ago
No error handling code when adding an element to the set. Also, a list maintains elements in order, unlike an array pointing to objects that keep track of their position in said array.
chriswarbo 9y ago
> Why would one ever prefer a linked list over a dynamic array? (Singly) linked lists are trivial to implement in an immutable way (the article talks about the difficulty of doubly-linked lists, implemented in a mutable way). It's trivial to have linked lists share a tail; this makes datastructures like cactus stacks really easy. Linked lists are amenable to reasoning by induction (e.g. in Coq, Agda, Idris, etc.). Linked lists are amenable to lazy algorithms (e.g. iterators/generators). Linked lists can be heavily optimised, e.g. using stream fusion. That's off the top of my head. Note that in many cases it might be preferable to use linked lists in the source, but have them compiled to some other representation like arrays (or, in the case of fusion, a single tight loop).
- jstimpfle 9y ago
  What you say doesn't apply to the kernel, which uses doubly linked lists.
- biocomputation 9y ago
  * Also, lists are a reasonable way of managing unrelated types.
koverstreet 9y ago
Because with intrusive lists, insertion/removal can't fail due to memory allocation failure - with dynamic arrays, it can. In the kernel, where you have to handle every single error path, this is a big deal.
robmccoll 9y ago
If you are using a slab allocator like in this case, you are effectively splitting the middle. Allocation of the nodes is contiguous in the slab, so locality of the nodes overall is likely better than malloc()ing each one. Allocation is cheap since you are likely just grabbing the head of a free list in the slab (or incrementing a counter if you never intend to free intermediate data), and you get less heap fragmentation/ higher utilization than a pure linked list. You still get fast insertion and removal anywhere in the list. There's a bit of storage overhead for pointers and pointer jumping on access, but ideally your list isn't super fragmented, so close to linear cache reads. If the list is long lived / has certain turnover patterns, some of these effects fall away. You could implement your own defrag/resort, but that assumes being able to relocate the data. Also in some cases the linked list header may be embedded in other structures, so you'd have to pull the header out to go with a purely vector-based approach for when you need to shift (assuming you can't move the entire structure). And if the structure needs to reference itself in the list for quick removal, that's a problem if its index is changing. Otherwise you could just search the vector for references at linear cost.
falcolas 9y ago
> Why would one ever prefer a linked list over a dynamic array? Consistent performance. Every insert and every delete requires the same amount of time, at the cost of a higher average traversal time. You can ameliorate some of the deletion reordering cost if you can change the order of the array, but not all use-cases allow for this. Also, intrusively linked lists (that is, the same item represented in multiple lists) are just as poor, performance wise, when implemented with arrays. I did a quick test of this at one point, comparing C++ std::list with a linked list; the performance of the dynamic array was significantly higher for most operations (about one order of magnitude for my test), but the worst-case was much, much worse than the linked list (somewhere close to two orders of magnitude).
jekub 9y ago
There is a lot of reason why you can prefer a linked-list over an array, even with the hardware changing they are still a lot more efficient in some cases : * In multi-threaded context insertion and deletion can be done lock-free which is not the case for arrays ; * For intrusive list, insertion and deletion can't fail due to memory allocation ; * If you do only insertion at the tail and removal at the head these operation need only a pointer change which is more efficient than an array ; * Merging two list is only one pointer operation ; * Intrusive list have better memory allocation properties ; * ... If you look at the usage of linked-list in the kernel you will see that they are used for reasons. The problem is that, on new hardware, linked list should be used in less cases that in the past and some people have generalized this to linked-list should never be used. This is false, if you care about performances you should keep thinking and testing what is the best data-structure in different cases. If you don't care about performances, you should use an abstraction who implement what you need and don't car about the underlying data-structure.
- josefx 9y ago
  > In multi-threaded context insertion and deletion can be done lock-free which is not the case for arrays I just love when multithreaded code frees the element I currently iterate over in a different thread. > For intrusive list, insertion and deletion can't fail due to memory allocation ; As long as you store your elements on the stack or use static values you mean? Heap allocation happens at some point, you just move the location where it happens. > If you do only insertion at the tail and removal at the head these operation need only a pointer change which is more efficient than an array Use a circular buffer. Until the array is full you can just modify the start/end pointers.
brenns10 9y ago
More important than any of the sibling arguments is that we're talking about a socket control block. I don't control where it is allocated or freed, so I can't dictate its location in memory. Even if I did control it, there are probably several lists a socket might be a part of. Storing the socket in a dynamic array will only work for one of those lists. It's similar to a sparse database index - you can only have one of them. The rest of the lists have to be linked. Not to mention, when items are shuffled around in a dynamic array, you lose the ability to have a consistent pointer to them.
dahart 9y ago
> Why would one ever prefer a linked list over a dynamic array? I thought this same thing when I started doing embedded console game development and saw a lot of linked lists going on. I came to realize there are a bunch of really good reasons to use linked lists. The biggest difference in practice is that linked list pointers are commonly fields inside the data that you're linking, as opposed to being a separate data structure. With a dynamic array, it's usually a separate data structure. Neither of those is absolute or always, but that's how it normally plays out. With that in mind: Sometimes you're loading a block of pre-formatted binary data off disk or from a network that has space for linked list pointers. Rather than allocate anything else, you can fill in the list pointers. Sometimes you have a lot of small lists to manage. If you're allocating space for your list data, and the dynamic array doesn't get big enough for amortizing to take over, then you're doing double allocations, one for the data and one for the dynamic array & potentially first couple of reallocs. Fragmentation is worse with a dynamic array (when it's a separate data structure), and re-ordering events are much costlier in arrays than with linked lists.

dozzie 9y ago

Because (doubly) linked lists can do something an array cannot? Like join operations in O(1)? Or removing an arbitrary element in O(1) once you have its handle?

blibble 9y ago
if it's unordered (like you'd expect a list of sockets to be) you can get O(1) removal for an array by swapping the end item into the removed slot
- dozzie 9y ago
  ...unless something else holds a pointer to the handle you're swapping with.
  - blibble 9y ago
    kernels don't tend to give userspace raw pointers into kernel memory
    - dozzie 9y ago
      But kernels tend to give raw pointers to other kernel code.
      - blibble 9y ago
        a good chunk of the fun in kernel code is maintaining the various layers of self-referential lists and dealing with the cleanup
  - staticassertion 9y ago
    This is already a problem if you're removing an item, regardless of whether it's done with swap remove or not.
    - toast0 9y ago
      For the item you're removing, you are presumably removing it because all handles have been closed. But the item you're potentially swapping with may certainly have open handles.
      - staticassertion 9y ago
        True.

bmon 9y ago

Insertion and deletion are prime examples, often requiring you to move large chunks of memory. The same operation just requires pointer changes (after finding where you want to insert or delete). I think in this example it would be common to be removing structs from the center of the list.

signa11 9y ago
> Insertion and deletion are prime examples, often requiring you to move large chunks of memory. on modern cpu's with huge caches, i seriously doubt this claim. fwiw, i have played around with synthetic problems where: i insert sequence of random integers into a sorted sequence, then remove those elements one by one as determined by a random sequence of positions. and almost always, vectors outperform lists by at least couple of orders of magnitude. or to put it another way, it is almost never about either lists / vectors or something else, and boils down to couple of 'rules' e.g. access data predictably (avoid trashing the cache), keep data compact (more cache utilization) etc. etc.
- jstimpfle 9y ago
  > i insert sequence of random integers into a sorted sequence, then remove those elements one by one as determined by a random sequence of positions. Which means that you scan the list twice for each node. First for insertion and then for deletion. Starting at maybe a hundred that would be much more efficient with a balanced search tree. They have a good Red-black tree in Linux. But if it's only arrays vs lists - with linked lists, pointers to items are never invalidated. With dynamic arrays, they are. Dynamic arrays are fine for plain old data arrays. But it's harder for data that has "identity" and is frequently mutated. And if a node is in multiple lists, I guess arrays are out. You'd need to store the data redundantly. Extra bad if you need atomic mutations.
- yongjik 9y ago
  Well on a 64-bit machine each node of a singly-linked list of integers will be 16 bytes (8 byte pointer + 4 byte integer + 4 byte for padding). That's 300% overhead. Becomes 500% for doubly-linked lists. So it's not surprising that linked lists perform very poorly in such circumstances.

SamReidHughes 9y ago

No error handling code when adding an element to the set. Also, a list maintains elements in order, unlike an array pointing to objects that keep track of their position in said array.

chriswarbo 9y ago

> Why would one ever prefer a linked list over a dynamic array? (Singly) linked lists are trivial to implement in an immutable way (the article talks about the difficulty of doubly-linked lists, implemented in a mutable way). It's trivial to have linked lists share a tail; this makes datastructures like cactus stacks really easy. Linked lists are amenable to reasoning by induction (e.g. in Coq, Agda, Idris, etc.). Linked lists are amenable to lazy algorithms (e.g. iterators/generators). Linked lists can be heavily optimised, e.g. using stream fusion. That's off the top of my head. Note that in many cases it might be preferable to use linked lists in the source, but have them compiled to some other representation like arrays (or, in the case of fusion, a single tight loop).

jstimpfle 9y ago
What you say doesn't apply to the kernel, which uses doubly linked lists.
biocomputation 9y ago
* Also, lists are a reasonable way of managing unrelated types.

koverstreet 9y ago

Because with intrusive lists, insertion/removal can't fail due to memory allocation failure - with dynamic arrays, it can. In the kernel, where you have to handle every single error path, this is a big deal.

robmccoll 9y ago

If you are using a slab allocator like in this case, you are effectively splitting the middle. Allocation of the nodes is contiguous in the slab, so locality of the nodes overall is likely better than malloc()ing each one. Allocation is cheap since you are likely just grabbing the head of a free list in the slab (or incrementing a counter if you never intend to free intermediate data), and you get less heap fragmentation/ higher utilization than a pure linked list. You still get fast insertion and removal anywhere in the list. There's a bit of storage overhead for pointers and pointer jumping on access, but ideally your list isn't super fragmented, so close to linear cache reads. If the list is long lived / has certain turnover patterns, some of these effects fall away. You could implement your own defrag/resort, but that assumes being able to relocate the data. Also in some cases the linked list header may be embedded in other structures, so you'd have to pull the header out to go with a purely vector-based approach for when you need to shift (assuming you can't move the entire structure). And if the structure needs to reference itself in the list for quick removal, that's a problem if its index is changing. Otherwise you could just search the vector for references at linear cost.

falcolas 9y ago

> Why would one ever prefer a linked list over a dynamic array? Consistent performance. Every insert and every delete requires the same amount of time, at the cost of a higher average traversal time. You can ameliorate some of the deletion reordering cost if you can change the order of the array, but not all use-cases allow for this. Also, intrusively linked lists (that is, the same item represented in multiple lists) are just as poor, performance wise, when implemented with arrays. I did a quick test of this at one point, comparing C++ std::list with a linked list; the performance of the dynamic array was significantly higher for most operations (about one order of magnitude for my test), but the worst-case was much, much worse than the linked list (somewhere close to two orders of magnitude).

jekub 9y ago

There is a lot of reason why you can prefer a linked-list over an array, even with the hardware changing they are still a lot more efficient in some cases : * In multi-threaded context insertion and deletion can be done lock-free which is not the case for arrays ; * For intrusive list, insertion and deletion can't fail due to memory allocation ; * If you do only insertion at the tail and removal at the head these operation need only a pointer change which is more efficient than an array ; * Merging two list is only one pointer operation ; * Intrusive list have better memory allocation properties ; * ... If you look at the usage of linked-list in the kernel you will see that they are used for reasons. The problem is that, on new hardware, linked list should be used in less cases that in the past and some people have generalized this to linked-list should never be used. This is false, if you care about performances you should keep thinking and testing what is the best data-structure in different cases. If you don't care about performances, you should use an abstraction who implement what you need and don't car about the underlying data-structure.

josefx 9y ago
> In multi-threaded context insertion and deletion can be done lock-free which is not the case for arrays I just love when multithreaded code frees the element I currently iterate over in a different thread. > For intrusive list, insertion and deletion can't fail due to memory allocation ; As long as you store your elements on the stack or use static values you mean? Heap allocation happens at some point, you just move the location where it happens. > If you do only insertion at the tail and removal at the head these operation need only a pointer change which is more efficient than an array Use a circular buffer. Until the array is full you can just modify the start/end pointers.

brenns10 9y ago

More important than any of the sibling arguments is that we're talking about a socket control block. I don't control where it is allocated or freed, so I can't dictate its location in memory. Even if I did control it, there are probably several lists a socket might be a part of. Storing the socket in a dynamic array will only work for one of those lists. It's similar to a sparse database index - you can only have one of them. The rest of the lists have to be linked. Not to mention, when items are shuffled around in a dynamic array, you lose the ability to have a consistent pointer to them.

dahart 9y ago

> Why would one ever prefer a linked list over a dynamic array? I thought this same thing when I started doing embedded console game development and saw a lot of linked lists going on. I came to realize there are a bunch of really good reasons to use linked lists. The biggest difference in practice is that linked list pointers are commonly fields inside the data that you're linking, as opposed to being a separate data structure. With a dynamic array, it's usually a separate data structure. Neither of those is absolute or always, but that's how it normally plays out. With that in mind: Sometimes you're loading a block of pre-formatted binary data off disk or from a network that has space for linked list pointers. Rather than allocate anything else, you can fill in the list pointers. Sometimes you have a lot of small lists to manage. If you're allocating space for your list data, and the dynamic array doesn't get big enough for amortizing to take over, then you're doing double allocations, one for the data and one for the dynamic array & potentially first couple of reallocs. Fragmentation is worse with a dynamic array (when it's a separate data structure), and re-ordering events are much costlier in arrays than with linked lists.