Node deletion in doubly linked list only takes O(1).
On write, invalidation needs to be propagated to both directions.
pk267
One thing to note here: if 2 nodes want to do a read at the same time. They will both make themselves the head and have their next pointer to the previous head of the list (and there will be no error when they do that). Thus this LinkedList will then have 2 head pointers!
hzxa21
@pk267 If we end up having 2 head pointers, then how to set the prev ptr of the previous head of the list. Do you mean that there can be multiple pre ptrs for a node in the list?
paracon
@Master, I think the reason for a doubly linked list is to handle evictions easily, i.e node deletions. Invalidations take the same time for singly and doubly linked list.
bochet
@paracon I don't see how eviction in a doubly linked list is easier. If we need to traverse the linked list to find the node to evict, we just need to remember the previous node, and deletion can be easily done. Unless we have some pointer to go directly from processor id to the linked element.
RomanArena
Invalidation is traversed from the head node, so I think on write-miss, singly and doubly linked list have the same cost.
coffee7
@bochet eviction in a doubly linked list is easier because we can delete the node just given the location of the node. In a singly linked list, even if we are given the location of the node we want to delete, we still have to traverse the list to find the predecessor. In short, deletion in a doubly linked list is O(1), but deletion in a singly linked list is O(n).
lfragago
One interesting point is that although a double linked list has better performance for deletions, we need to spend extra memory overhead to keep an extra pointer pointing to the previous element, so we are trading memory for efficiency.
Why do we need a doubly linked list here?
Node deletion in doubly linked list only takes O(1).
On write, invalidation needs to be propagated to both directions.
One thing to note here: if 2 nodes want to do a read at the same time. They will both make themselves the head and have their next pointer to the previous head of the list (and there will be no error when they do that). Thus this LinkedList will then have 2 head pointers!
@pk267 If we end up having 2 head pointers, then how to set the prev ptr of the previous head of the list. Do you mean that there can be multiple pre ptrs for a node in the list?
@Master, I think the reason for a doubly linked list is to handle evictions easily, i.e node deletions. Invalidations take the same time for singly and doubly linked list.
@paracon I don't see how eviction in a doubly linked list is easier. If we need to traverse the linked list to find the node to evict, we just need to remember the previous node, and deletion can be easily done. Unless we have some pointer to go directly from processor id to the linked element.
Invalidation is traversed from the head node, so I think on write-miss, singly and doubly linked list have the same cost.
@bochet eviction in a doubly linked list is easier because we can delete the node just given the location of the node. In a singly linked list, even if we are given the location of the node we want to delete, we still have to traverse the list to find the predecessor. In short, deletion in a doubly linked list is O(1), but deletion in a singly linked list is O(n).
One interesting point is that although a double linked list has better performance for deletions, we need to spend extra memory overhead to keep an extra pointer pointing to the previous element, so we are trading memory for efficiency.