4 ms·

Everything you mentioned can be done with statically allocated arrays - if you have known bounds - or lists of large arrays, as mentioned before. Lists will ev

Everything you mentioned can be done with statically allocated arrays - if you have known bounds - or lists of large arrays, as mentioned before. Lists will eventually become a problem since your next/prev pointers may not be pointing to adjacent memory positions, now your linear iteration over elements will not be cache friendly. Not only that but you need to retrieve pointers and dereference them, more pressure and worse for the cache again. You also add a "load" dependency between all elements so you can't easily break processing between multiple cores. Lists may be conceptually elegant but they are not the most suited for performance or efficiency.

dragontamer 6y ago
> Lists will eventually become a problem since your next/prev pointers may not be pointing to adjacent memory positions But what if they were pointing to adjacent memory positions in the common case? What if the problem you're suggesting doesn't exist in some circumstances? Like in Knuth's Dancing Links. The neighbors of links are laid out in memory next to each other. If the list upon program startup is "1 -> 2 -> 3", we know that 1, 2, and 3 are neighbors in memory. And what if it is demonstrated that this weird "linked list with nodes laid out next to each other" is shown to be sufficient to solve NP-complete problems like the exact-cover problem with great efficiency in practice? ----------------- What if, when creating 100 nodes at a time, we lay out all 100-nodes in a row. chunk = malloc(sizeof(Node) * 100). for(int i=99; i>=0; i--){ chunk[i].next = head; chunk[i].data = foobar(); head = chunk[i]; } Now we have the spatial locality you so desire, while still retaining the ability to rearrange the list. In fact, add/remove is still possible (though the malloc/free is harder to keep track of: if you're in a Dancing-links scenario, you may not ever need to call free)
- Twisol 6y ago
  Perhaps naively, would a struct-of-arrays perform better than an array-of-structs? I imagine that the separate `next` and `data` arrays might be packed better, and instead of processing one cache line at a time, you could load two cache lines simultaneously to process double the sequential data with every round-trip to RAM. More to the point of the discussion, it seems to me that you're describing situations where the cells of your container do have a natural inherent order, but may have additional relationships imposed on top of them. In the case of Algorithm X, the matrix has an inherent, consistent sense of order across rows and columns, but any particular line may skip elements depending on the state of the algorithm. I think that doubly-layered structure is important to recognize; it's not something all data will have, and it's an inherent property of the problem or domain, not of the linked list data structure itself.
  - dragontamer 6y ago
    Hmm. Good thoughts. I'd like to respond more deeply but I'm not sure what to say, lol. You've just got a good post here so I feel like I should acknowledge it.
- ameixaseca 6y ago
  I mentioned 3 points, you addressed one for a very specific scenario. In any case, even if you say your list has adjacent elements, the other two points still apply. I don't know why you keep bringing this algorithm to the discussion, everything that was mentioned applies to any linked list. It's a fundamental property of linked lists, period. Seems like you're completely missing the point: the discussion started on performance properties of data structures. That's what's being pointed out, and it's going to be a fact regardless of how you want to apply it.
  - dragontamer 6y ago
    I can address the other point too. > You also add a "load" dependency between all elements so you can't easily break processing between multiple cores. You might be surprised. Lets say we have that Node arrayOfNodes[100]. However, we do not know which node is the beginning, the end, which nodes are in the array, or which ones have been erased. You might think that its an innately sequential algorithm to discover all the nodes in the array as well as its length. You'd be wrong: its a parallel algorithm, called Pointer Jumping. https://en.wikipedia.org/wiki/Pointer_jumping https://en.wikipedia.org/wiki/Pointer_jumping This "Pointer Jumping" methodology can be implemented on a GPU with high degrees of parallelism (one GPU-core per node), as long as you have enough nodes. In this arrayOfNodes[100] example, the parallelism is at best 100 (for example). We can even perform order-dependent operations such as "prefix sum" over the arrayOfNodes, in parallel, while we are discovering the order of the nodes thanks to Pointer jumping. So in fact: it is very possible to operate linked lists in parallel (even SIMD / GPU parallel). No, its not how the typical programmer traverses a linked list. But its a good trick for speeding things up in some circumstances. A great example of pointer jumping is in the paper "Data Parallel Algorithms" by Hillis and Steele. ----------- I'm not sure what your "3rd point" is. I only count two points. > the discussion started on performance properties of data structure The root of the discussion is a linked-list discussion. The literal text of the submission and title is: "Drop millions of allocations by using a linked list" The point I make is that there's a great many tricks of Linked Lists that typical programmers don't seem to know about that mitigate the common complaints of linked-lists.

dragontamer 6y ago

> Lists will eventually become a problem since your next/prev pointers may not be pointing to adjacent memory positions But what if they were pointing to adjacent memory positions in the common case? What if the problem you're suggesting doesn't exist in some circumstances? Like in Knuth's Dancing Links. The neighbors of links are laid out in memory next to each other. If the list upon program startup is "1 -> 2 -> 3", we know that 1, 2, and 3 are neighbors in memory. And what if it is demonstrated that this weird "linked list with nodes laid out next to each other" is shown to be sufficient to solve NP-complete problems like the exact-cover problem with great efficiency in practice? ----------------- What if, when creating 100 nodes at a time, we lay out all 100-nodes in a row. chunk = malloc(sizeof(Node) * 100). for(int i=99; i>=0; i--){ chunk[i].next = head; chunk[i].data = foobar(); head = chunk[i]; } Now we have the spatial locality you so desire, while still retaining the ability to rearrange the list. In fact, add/remove is still possible (though the malloc/free is harder to keep track of: if you're in a Dancing-links scenario, you may not ever need to call free)

Twisol 6y ago
Perhaps naively, would a struct-of-arrays perform better than an array-of-structs? I imagine that the separate `next` and `data` arrays might be packed better, and instead of processing one cache line at a time, you could load two cache lines simultaneously to process double the sequential data with every round-trip to RAM. More to the point of the discussion, it seems to me that you're describing situations where the cells of your container do have a natural inherent order, but may have additional relationships imposed on top of them. In the case of Algorithm X, the matrix has an inherent, consistent sense of order across rows and columns, but any particular line may skip elements depending on the state of the algorithm. I think that doubly-layered structure is important to recognize; it's not something all data will have, and it's an inherent property of the problem or domain, not of the linked list data structure itself.
- dragontamer 6y ago
  Hmm. Good thoughts. I'd like to respond more deeply but I'm not sure what to say, lol. You've just got a good post here so I feel like I should acknowledge it.
ameixaseca 6y ago
I mentioned 3 points, you addressed one for a very specific scenario. In any case, even if you say your list has adjacent elements, the other two points still apply. I don't know why you keep bringing this algorithm to the discussion, everything that was mentioned applies to any linked list. It's a fundamental property of linked lists, period. Seems like you're completely missing the point: the discussion started on performance properties of data structures. That's what's being pointed out, and it's going to be a fact regardless of how you want to apply it.
- dragontamer 6y ago
  I can address the other point too. > You also add a "load" dependency between all elements so you can't easily break processing between multiple cores. You might be surprised. Lets say we have that Node arrayOfNodes[100]. However, we do not know which node is the beginning, the end, which nodes are in the array, or which ones have been erased. You might think that its an innately sequential algorithm to discover all the nodes in the array as well as its length. You'd be wrong: its a parallel algorithm, called Pointer Jumping. https://en.wikipedia.org/wiki/Pointer_jumping https://en.wikipedia.org/wiki/Pointer_jumping This "Pointer Jumping" methodology can be implemented on a GPU with high degrees of parallelism (one GPU-core per node), as long as you have enough nodes. In this arrayOfNodes[100] example, the parallelism is at best 100 (for example). We can even perform order-dependent operations such as "prefix sum" over the arrayOfNodes, in parallel, while we are discovering the order of the nodes thanks to Pointer jumping. So in fact: it is very possible to operate linked lists in parallel (even SIMD / GPU parallel). No, its not how the typical programmer traverses a linked list. But its a good trick for speeding things up in some circumstances. A great example of pointer jumping is in the paper "Data Parallel Algorithms" by Hillis and Steele. ----------- I'm not sure what your "3rd point" is. I only count two points. > the discussion started on performance properties of data structure The root of the discussion is a linked-list discussion. The literal text of the submission and title is: "Drop millions of allocations by using a linked list" The point I make is that there's a great many tricks of Linked Lists that typical programmers don't seem to know about that mitigate the common complaints of linked-lists.