From: <pv...@pv...> - 2005-12-19 18:23:06
|
> A thread-safe fifo seems to be a semi-standard extension to > multi-threaded Lisps, and I find them quite handy. Since sbcl is my > favorite lisp, I thought I'd take a stab at it. It's a bit rough, but > I'd like feedback on it since it's something I would eventually like to > see in sbcl. > > The linked list is overkill: it probably should be an array, but I > wanted to submit something before I chickened out. As suggested by Xof on #lisp, you probably want to use a (singly) linked list with a pointer to the tail to implement your queue (since it gives an efficient TCONC). Arrays are probably a bad idea because they're so hard to grow, and don't seem particularly more time-efficient than the previously described scheme to implement queues. I don't know if/how SBCL exposes compare-and-swap and other primitives, but there are relatively simple lock-free or wait-free algorithms for queues. A quick google gives http://www.boyet.com/Articles/LockfreeQueue.html for a lock-free (it looks wait-free too) queue in C++. Paul Khuong |