interlocked linked list [modified]
-
nevermind.. i think ill give up for now and just use a modified spinlock! im writing a simple lock-free queue (intended for efficient multithreaded use) and im not sure ive quite figured out the logic behind the use of Interlocked.CompareExchange(). would code like the following produce the correct result of adding a new linked list node to the tail of a list under multithreading conditions??
while (null != Interlocked.CompareExchange(ref _tail.next, newNode, null)) Thread.Sleep(1); _tail = newNode;thanks in advance ;) -- modified at 12:40 Monday 8th January, 2007
-
nevermind.. i think ill give up for now and just use a modified spinlock! im writing a simple lock-free queue (intended for efficient multithreaded use) and im not sure ive quite figured out the logic behind the use of Interlocked.CompareExchange(). would code like the following produce the correct result of adding a new linked list node to the tail of a list under multithreading conditions??
while (null != Interlocked.CompareExchange(ref _tail.next, newNode, null)) Thread.Sleep(1); _tail = newNode;thanks in advance ;) -- modified at 12:40 Monday 8th January, 2007
Hi, I dont think this is thread-safe: you perform two operations on the list 1. CompareExchange 2. modify tail (_tail=newNode) the combined operations should be atomic. And I dont think you can achieve it with the Interlocked class at all, since inserting or removing a node to/from a linked list involves modifying two references or pointers, which is more than any Interlocked method offers. SO you will need a lock after all. :)
Luc Pattyn
-
Hi, I dont think this is thread-safe: you perform two operations on the list 1. CompareExchange 2. modify tail (_tail=newNode) the combined operations should be atomic. And I dont think you can achieve it with the Interlocked class at all, since inserting or removing a node to/from a linked list involves modifying two references or pointers, which is more than any Interlocked method offers. SO you will need a lock after all. :)
Luc Pattyn
sorry, i dont think u were very convincing, im pretty sure this would work...
- in neutral state, _tail.next is null; the end of the list.
- the first thread executes the interlocked operation which succeeds and atomically sets _tail.next to something other than null.
- this causes the interlocked operation to fail on any other thread, and spin.
- the final assignment returns _tail.next to null (as a new list node has no next-node) and the list is coherent.
i think i just answered my own question there but i do get the feeling im missing something. i have more of an issue dequeuing a list node; ascertaining just how the de/enqueue code can interfere with each other and how i can get it to safely execute in parallel.
I worship his divine shadow. ^
-
sorry, i dont think u were very convincing, im pretty sure this would work...
- in neutral state, _tail.next is null; the end of the list.
- the first thread executes the interlocked operation which succeeds and atomically sets _tail.next to something other than null.
- this causes the interlocked operation to fail on any other thread, and spin.
- the final assignment returns _tail.next to null (as a new list node has no next-node) and the list is coherent.
i think i just answered my own question there but i do get the feeling im missing something. i have more of an issue dequeuing a list node; ascertaining just how the de/enqueue code can interfere with each other and how i can get it to safely execute in parallel.
I worship his divine shadow. ^
Well, yes and no: Yes, if you have a single-linked list and a _last reference, then you can append a node to it correctly with your code, but that's about it. If there is no _head, and no backward link (prev), then you can not reach any other node. A single-linked list with a head only typically uses the following logic (I use a dummy head node to simplify code: when head.next is the first node (or null), then head itself never changes and never is null):
void addNode(Node newNode) { // unsafe version
newNode.next=head.next;
head.next=newNode;
}
Node removeFirstNode() { // unsafe version
Node firstNode=head.next;
head.next=firstNode.next; // <<--- modified
return firstNode;
}the safe versions would be:
void addNode(Node newNode) { // safe version
do {
Node firstNode=head.next;
newNode.next=firstNode;
} while (firstNode!=Interlocked.ExchangeCompare(head.next,newNode,firstNode));
}Node removeFirstNode() { // safe version
do {
Node firstNode=head.next;
} while (firstNode!=Interlocked.ExchangeCompare(head.next, firstNode.next, firstNode));
return firstNode;
}But now there are a lot of functional limitations: there is no access to any other node 1) we do not maintain a tail 2) we do not maintain a backward link so we have what is known as a stack, certainly not a queue. If we want more than stack functionality, we'd better have head+tail+nextlinks+prevlinks; but we must perform multiple stores atomically, and you cannot achieve that with a single Interlocked method. You can of course synthesize a lock yourself, something like:
while (0!=Interlocked.ExchangeCompare(lockVar, 1, 0)) Thread.Sleep(1); // do whatever you want now, even multiple stores lockVar=0;but that is not what you intended, is it ? :) -- modified at 15:10 Monday 8th January, 2007
Luc Pattyn
//
-
Well, yes and no: Yes, if you have a single-linked list and a _last reference, then you can append a node to it correctly with your code, but that's about it. If there is no _head, and no backward link (prev), then you can not reach any other node. A single-linked list with a head only typically uses the following logic (I use a dummy head node to simplify code: when head.next is the first node (or null), then head itself never changes and never is null):
void addNode(Node newNode) { // unsafe version
newNode.next=head.next;
head.next=newNode;
}
Node removeFirstNode() { // unsafe version
Node firstNode=head.next;
head.next=firstNode.next; // <<--- modified
return firstNode;
}the safe versions would be:
void addNode(Node newNode) { // safe version
do {
Node firstNode=head.next;
newNode.next=firstNode;
} while (firstNode!=Interlocked.ExchangeCompare(head.next,newNode,firstNode));
}Node removeFirstNode() { // safe version
do {
Node firstNode=head.next;
} while (firstNode!=Interlocked.ExchangeCompare(head.next, firstNode.next, firstNode));
return firstNode;
}But now there are a lot of functional limitations: there is no access to any other node 1) we do not maintain a tail 2) we do not maintain a backward link so we have what is known as a stack, certainly not a queue. If we want more than stack functionality, we'd better have head+tail+nextlinks+prevlinks; but we must perform multiple stores atomically, and you cannot achieve that with a single Interlocked method. You can of course synthesize a lock yourself, something like:
while (0!=Interlocked.ExchangeCompare(lockVar, 1, 0)) Thread.Sleep(1); // do whatever you want now, even multiple stores lockVar=0;but that is not what you intended, is it ? :) -- modified at 15:10 Monday 8th January, 2007
Luc Pattyn
//
yes i see using a dummy node makes things a heck of a lot easier with the interlocked stuff and i had considered it but i didnt think it would make it that easy. the queue does have a head btw, from which items are removed (added to the tail). at first thought i would need to look into whether a circular reference of the head would introduce some other issue. but for simplicity's sake (sister of felicity i believe) im gonna use a good old LinkedList and the sleeplock thing. i usually just lock () { } things but for this i certianly want to keep it lightweight. with a little modification to make it adaptive for an actual multi-processor system (ie. not relinquishing time slice) i think itll be quite scalable. thanks for your input
I worship his divine shadow. ^
-
yes i see using a dummy node makes things a heck of a lot easier with the interlocked stuff and i had considered it but i didnt think it would make it that easy. the queue does have a head btw, from which items are removed (added to the tail). at first thought i would need to look into whether a circular reference of the head would introduce some other issue. but for simplicity's sake (sister of felicity i believe) im gonna use a good old LinkedList and the sleeplock thing. i usually just lock () { } things but for this i certianly want to keep it lightweight. with a little modification to make it adaptive for an actual multi-processor system (ie. not relinquishing time slice) i think itll be quite scalable. thanks for your input
I worship his divine shadow. ^
FYI, I tend to avoid circular linked lists; I typically use either a single-linked list with a dummy head node, or a double-linked list with a dummy head node and a dummy tail node (different from head); reason is you can then walk the list forwards/backwards (without removing nodes) until next/prev equals null. Combining the head and tail dummies would save a node, but that is typically not worth the hassle (unless nodes are really big of course). :)
Luc Pattyn
-
FYI, I tend to avoid circular linked lists; I typically use either a single-linked list with a dummy head node, or a double-linked list with a dummy head node and a dummy tail node (different from head); reason is you can then walk the list forwards/backwards (without removing nodes) until next/prev equals null. Combining the head and tail dummies would save a node, but that is typically not worth the hassle (unless nodes are really big of course). :)
Luc Pattyn
-
Well, yes and no: Yes, if you have a single-linked list and a _last reference, then you can append a node to it correctly with your code, but that's about it. If there is no _head, and no backward link (prev), then you can not reach any other node. A single-linked list with a head only typically uses the following logic (I use a dummy head node to simplify code: when head.next is the first node (or null), then head itself never changes and never is null):
void addNode(Node newNode) { // unsafe version
newNode.next=head.next;
head.next=newNode;
}
Node removeFirstNode() { // unsafe version
Node firstNode=head.next;
head.next=firstNode.next; // <<--- modified
return firstNode;
}the safe versions would be:
void addNode(Node newNode) { // safe version
do {
Node firstNode=head.next;
newNode.next=firstNode;
} while (firstNode!=Interlocked.ExchangeCompare(head.next,newNode,firstNode));
}Node removeFirstNode() { // safe version
do {
Node firstNode=head.next;
} while (firstNode!=Interlocked.ExchangeCompare(head.next, firstNode.next, firstNode));
return firstNode;
}But now there are a lot of functional limitations: there is no access to any other node 1) we do not maintain a tail 2) we do not maintain a backward link so we have what is known as a stack, certainly not a queue. If we want more than stack functionality, we'd better have head+tail+nextlinks+prevlinks; but we must perform multiple stores atomically, and you cannot achieve that with a single Interlocked method. You can of course synthesize a lock yourself, something like:
while (0!=Interlocked.ExchangeCompare(lockVar, 1, 0)) Thread.Sleep(1); // do whatever you want now, even multiple stores lockVar=0;but that is not what you intended, is it ? :) -- modified at 15:10 Monday 8th January, 2007
Luc Pattyn
//