4 ms·

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 a

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

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.