Casey in his refterm lecture said the "array is faster than linked list" statement is "fake optimization". It's at best neutral or worse counter-productive https://youtu.be/pgoetgxecw8?t=722
What do you think about having two separate arrays: one for the nodes (which just hold a pointer to the next node and a pointer to the value) and one for the actual values?
Thanks for the great post. It made me realize that I am also dogmatically leaning on contiguous arrays far too much "because cache", creating unnecessarily complex allocation code just to manage them.
I'm particularly interested in the idea of storing a number of entities per linked list node, to be able to handle a large number of total entities and still iterate over them with relative speed. However, I'm wondering how one would handle updating entity references when the block is updated with additions/deletions/insertions with such an arrangement?
My guess is each entity would require a pointer to the block, and an index to the entity within that block. To delete an entity, we might need to do something like marking it, and then freeing the block when all entities are marked? Maybe it's not the best approach for my particular situation: I also need to sort entities, which would ruin any references if using anything other than a single entity per node linked list.
Isn't the case with packing multiple elements in a node essentially a different data structure? Yes, nominally it is a linked list in that you link nodes and content can be whatever, but packing elements makes it a hybrid, if you consider the element the basic data unit of the whole structure. Semantically it is to linked lists what a B-tree is to balanced trees. (And surely not a coincidence that in practice B-trees often exhibit massive performance benefits compared to "classic" balanced trees (e.g. BST, AVL, red-black) in that domain.)
It certainly is in tune with the composable data structures theme, but also likely not what people readily associate with the "linked list" moniker.
I think that I will try to utilize linked lists more after reading this article. I feel a little embarrassed because I was definitely one of the people talking about the cache locality, but I would like to ask about one use case of linked lists that I have seen. If you had an isolated function that needed to return a list (like a string split, for example), could you use the way that arenas allocate memory to dynamically grow a traditional list, or are linked lists still better in the case? I have not tried to implement something like this, but I have a gut feeling that it might fall apart at some level. Nevertheless, this was an interesting read and I will look for places where linked lists would be applicable in my code in the future.
Casey in his refterm lecture said the "array is faster than linked list" statement is "fake optimization". It's at best neutral or worse counter-productive https://youtu.be/pgoetgxecw8?t=722
What do you think about having two separate arrays: one for the nodes (which just hold a pointer to the next node and a pointer to the value) and one for the actual values?
Thanks for the great post. It made me realize that I am also dogmatically leaning on contiguous arrays far too much "because cache", creating unnecessarily complex allocation code just to manage them.
I'm particularly interested in the idea of storing a number of entities per linked list node, to be able to handle a large number of total entities and still iterate over them with relative speed. However, I'm wondering how one would handle updating entity references when the block is updated with additions/deletions/insertions with such an arrangement?
My guess is each entity would require a pointer to the block, and an index to the entity within that block. To delete an entity, we might need to do something like marking it, and then freeing the block when all entities are marked? Maybe it's not the best approach for my particular situation: I also need to sort entities, which would ruin any references if using anything other than a single entity per node linked list.
Isn't the case with packing multiple elements in a node essentially a different data structure? Yes, nominally it is a linked list in that you link nodes and content can be whatever, but packing elements makes it a hybrid, if you consider the element the basic data unit of the whole structure. Semantically it is to linked lists what a B-tree is to balanced trees. (And surely not a coincidence that in practice B-trees often exhibit massive performance benefits compared to "classic" balanced trees (e.g. BST, AVL, red-black) in that domain.)
It certainly is in tune with the composable data structures theme, but also likely not what people readily associate with the "linked list" moniker.
I think that I will try to utilize linked lists more after reading this article. I feel a little embarrassed because I was definitely one of the people talking about the cache locality, but I would like to ask about one use case of linked lists that I have seen. If you had an isolated function that needed to return a list (like a string split, for example), could you use the way that arenas allocate memory to dynamically grow a traditional list, or are linked lists still better in the case? I have not tried to implement something like this, but I have a gut feeling that it might fall apart at some level. Nevertheless, this was an interesting read and I will look for places where linked lists would be applicable in my code in the future.