Link Copied
Raf_Schietekat:
That's not even a challenge... :-)
Support can be had in the form of atomic operations beyond the size of a pointer as already indicated (how many of those early 64-bit x86 processors that don't provide that still exist, assuming that they're running 64-bit-pointer programs?)
I was thinking about this some time ago. I conclude that:
(1) There is a relatively small amount of such lagging processors. And this number constantly decreases over time.
(2) Those processors were not multicore, so it's not very disastrous to use lock on those.
So I decide that it's beneficial to use algorithms which relying on double word CAS anyway.
or ESA/390-z/Architecture PLO I suppose (I have not looked into it yet).
z/Arch PLO is capable of performing 6 types of operations:
- compare and load
- compare and swap
- double compare and swap
- compare and swap and store,
- compare and swap and double store
- or compare and swap and triple store
on 32, 64 and 128 (!) bit operands.
So maximum what you can get is 4 compares and 12 stores!
For stack you can use compare on 'version' field and stores to 'version' field and 'next' field.
One other consideration. If the container really is just a double-width compare-and-swap on moder hardware, then memory allocation/freeing overheads will dominate the overhead. Thus an intrusive container interface might be more appropriate. Here's what the interface might look like (adapted from old KAI C++ internals):
typedef implementation-defined concurrent_intrusive_stack_link;
template
concurrent_intrusive_stack; Intrusive queues and stacks is something I've wanted in TBB for a while, but we've never had time to implement/test/document them. Furthermore, having gone that far away from classic STL, we probably want to make them non-blocking too, at least if hardware permits.
I completely agree that (1) intrusive containers are the choice for high-performance software/libraries, and (2) "single-threaded interfaces" are not suitable for high-performance concurrent collections. Ok, some interfaces are suitable, but not in general case.
Btw, there are specialized memory allocators from some types of concurrent collections. For example, this one is very effective allocator for fifo-queues. Allocation and deallocation don't involve atomic RMW nor heavy memory fences.
http://groups.google.com/group/lock-free/browse_frm/thread/2c6f6250762385e1
If you have a multiple producers and a single consumer, it's simple to build a concurrent stack using a linked list and atomic operations on the root. Alas if there are multiple consumers, the ABA problem comes into play.
ABA is not serious problem here. Real problem in concurrent stack is safe memory reclamation.
Even if double-word CAS is used to solve ABA problem, access violation (SIGSEGV) is possible in pop() function.
That's not even a challenge... :-)
How are you going to solve safe memory reclamation problem in stack?
Even if double-word CAS is used to solve ABA problem, access violation (SIGSEGV) is possible in pop() function.
Do elaborate why a SIGSEGV would be so inexorable...
Consider following stack implementation:
T stack::pop()
{node_t* head = m_head;
for (;;)
{if (0 == head)
return T();
node_t* next = head->next; (***)
if (CAS(&m_head, &head, next))
{T val = head->value;
delete head;
return val;
}
}
}
ABA aside for a moment. In line (***) SIGSEGV is possible, if concurrent popper will pop node and delete it.
Do elaborate why a SIGSEGV would be so inexorable...
In pop(), for the stack implemented as single-linked list, the first operation would be to read the head and the second operation would be to read the head->next. There is a timing gap between two; if the thread execution is preempted at this exactly point, after the thread is back it might happen that the node pointed by head was popped by another thread, and destroyed. This is howyou get SIGSEGV, I believe.
I have a case that is much less restrictive than the usual semantics of the stack. In my case, it is guaranteed that objects (nodes) are alive all the time, and moreover the exact LIFO order is not important. Even in this "relaxed" problem, there seems no way to overcome ABA without DCAS.
Transactional memory would come handy,but I'm afraid it will be uselessly slow for a highly contended case like this one where all operations are done with the head.
Safe memory reclamation was the issue that we ran into when I had a summer intern, Prahabjan Kambadur, looking into lock-free algorithms for TBB back in 2005. Hazard pointers seemed like the way to go, though that would require that each thread using the container would have to register itself with a hazard-pointer overseer. The summer ended before we could get around to implementing hazard pointers. Also, at the time I thought that requiring registration was too much of a nuisance, but I've since changed my mind since no better alternative has come up.
Personally I consider SMR (Hazard Pointers) as worst GC technique for lock-free algorithms. SMR has very strong advantage, it has upper limit on number of pending (unreclaimed) objects. But it has very high price, store-load style fence for every acquisition. And it can't acquire more than one object at a time. So if you need to travese list, you have to acquire/release every node in the list (i.e. N store-load memory fences).
Oh! And don't forget that SMR is patented by Sun!
There is a couple of other GC techniques.
RCU. Has very low overheads. Some implementations are patented by IBM.
vZOOM. Has very low overheads. Also patented.
Proxy-collector algorithm. Really very good for lock-free collections. It seems that some implementations are patented. Here is one of my implementations of proxy-collector:
http://groups.google.com/group/lock-free/browse_frm/thread/18a9f43b93a6b3f0
And there is also Scalable Distributed Reference Counting. I hope that there are no patents on it:
http://groups.google.com/group/lock-free/browse_frm/thread/46d00a0f543a758e
Safe memory reclamation was the issue that we ran into when I had a summer intern, Prahabjan Kambadur, looking into lock-free algorithms for TBB back in 2005. Hazard pointers seemed like the way to go, though that would require that each thread using the container would have to register itself with a hazard-pointer overseer. The summer ended before we could get around to implementing hazard pointers. Also, at the time I thought that requiring registration was too much of a nuisance, but I've since changed my mind since no better alternative has come up.
As for registration. Yes, most GC techniques require some ugly things like thread registration/deregistration, or periodical activity from all registered threads, or some extremely OS-dependent code... or quite expensive.
Btw, oiginal non-amortized proxy-collector algorithm:
http://groups.google.com/group/comp.programming.threads/msg/d911c93ffa8db264
doesn't require any registration/deregistration, but is quite expensive - 2 atomic RMW operations to acquire/release a batch of nodes.
My amortized proxy-collector algorithm is extremely efficient, but do require periodic activity from all threads:
http://groups.google.com/group/lock-free/browse_frm/thread/18a9f43b93a6b3f0
For the ABA issue, we ended up using a tagged pointer and the following primitive, inspired by Itanium's cmp8xchg16:
If you use some form of safe memory reclamation, then ABA problem usually just doesn't exist.
If thread holds 'A', than another thread can change structure's anchor to 'B', but CANNOT change back to 'A', because first thread holds it, so 'A' can't be reclaimed.
And some form of safe memory reclamation is usually needed anyway, so in practice in most cases ABA is not a problem, and you do not need double-word CAS.
But I would be interested in a safe way to read arbitrary memory locations where no such guarantee exists, because I've been struggling with that question this week...
There is a number of techniques available. SMR, ROP, RCU, VZOOM, PC, DRC.
Almost all are patented. But one can use slightly modified versions of patented algorithms.
If you are interested in some technique I can provide links.
