From: Nikodemus S. <nik...@ra...> - 2008-05-26 09:23:59
Attachments:
sb-queue.lisp
|
Attached is an implementation of "An Optimistic Approach to Lock-Free FIFO Queues" by Edya Ladan-Mozes and Nir Shavit for SBCL, that I finished on the flight home from ELS. I am thinking of putting this in SB-EXT, and using it as a basis for a mailbox implementation in SB-THREAD -- and wherever else we turn out to need queues. Light testing makes me think I have it right... but I would greatly appreciate it someone finds the time to check my implementation of the algorithm. Cheers, -- Nikodemus |
From: Larry V. <re...@us...> - 2008-05-29 15:34:49
|
> > Attached is an implementation of "An Optimistic Approach to Lock-Free > FIFO Queues" by Edya Ladan-Mozes and Nir Shavit for SBCL, that I > finished on the flight home from ELS. I am thinking of putting this in > SB-EXT, and using it as a basis for a mailbox implementation in > SB-THREAD -- and wherever else we turn out to need queues. > > Light testing makes me think I have it right... but I would greatly > appreciate it someone finds the time to check my implementation of the > algorithm. > > Cheers, > > -- Nikodemus > In the included file, the RECEIVE function needs to loop and sleep if it wants to wait for an message. How would such function be written to not poll, but instead be "suspended" until queue got an message ? regards, /larry |
From: Nikodemus S. <nik...@ra...> - 2008-05-30 18:23:43
Attachments:
sb-mailbox.lisp
|
On Thu, May 29, 2008 at 6:34 PM, Larry Valkama <re...@us...> wrote: > In the included file, the RECEIVE function needs to loop and sleep if it > wants to wait for an message. How would such function be written to not > poll, but instead be "suspended" until queue got an message ? I confess I did not read your code, but it sounds like you want mailboxes, which are basically a a queue + a semaphore. ...as it happens, I have a tentative mailbox implementation on top of the aforementioned queue. Attached -- comments welcome. I am planning to stick it in SB-THREAD sooner or later. Cheers, -- Nikodemus |
From: Matthew S. <ako...@gm...> - 2008-07-29 17:35:58
|
Nikodemus Siivola <nikodemus <at> random-state.net> writes: > I have a tentative mailbox implementation on top of the > aforementioned queue. Attached -- comments welcome. I am planning to > stick it in SB-THREAD sooner or later. > > Cheers, > > -- Nikodemus > > Attachment (sb-mailbox.lisp): application/octet-stream, 1818 bytes > Are either of these patches making it into sbcl? Matt |
From: Nikodemus S. <nik...@ra...> - 2008-07-31 06:24:45
|
On Tue, Jul 29, 2008 at 8:35 PM, Matthew Swank <ako...@gm...> wrote: > Are either of these patches making it into sbcl? Yes, I'm mostly just still thinking about where to put them: in SB-THREAD, or elsewhere. I'm coming round to SB-THREAD, now. Cheers, -- Nikodemus |
From: Nikodemus S. <nik...@ra...> - 2008-08-02 08:34:05
|
On Thu, Jul 31, 2008 at 9:24 AM, Nikodemus Siivola <nik...@ra...> wrote: > On Tue, Jul 29, 2008 at 8:35 PM, Matthew Swank > <ako...@gm...> wrote: > >> Are either of these patches making it into sbcl? > > Yes, I'm mostly just still thinking about where to put them: in > SB-THREAD, or elsewhere. I'm coming round to SB-THREAD, now. So... any objections to adding QUEUE and MAILBOX to SB-THREAD? Cheers, -- Nikodemus |
From: Tobias C. R. <tc...@fr...> - 2008-08-02 08:54:33
|
"Nikodemus Siivola" <nik...@ra...> writes: > So... any objections to adding QUEUE and MAILBOX to SB-THREAD? I personally don't. But if you want SB-THREAD to be a primitive package. how about a SB-THREAD-EXT package? -T. |
From: Nikodemus S. <nik...@ra...> - 2008-08-03 18:29:08
|
On Sat, Aug 2, 2008 at 11:54 AM, Tobias C. Rittweiler <tc...@fr...> wrote: > But if you want SB-THREAD to be a primitive package. how about a SB-THREAD-EXT package? I don't see any great necessity to retain the "(but low-level)" in the docstring for SB-THREAD. I'm not sure what the original motivation for it was. While I do think it is important for SB-THREAD to provide low-level bits and pieces as well -- so that alternative high-level APIs can be built on top of it -- I don't see any overwhelming reason to keep nice high-level interfaces out from SB-THREAD. Cheers, -- Nikodemus |
From: Nikodemus S. <nik...@ra...> - 2008-08-06 17:45:47
Attachments:
0001-Lock-free-queue-and-mailbox.patch
|
Attached is my current take, this time as a patch against SBCL. Tests are still missing (actually, I had some, but seem to have misplaced them.) Slight differences to the earlier versions: * MAKE-MAILBOX accepts :INITIAL-CONTENTS (faster then MAKE-MAILBOX + repeated SEND-MESSAGE.) * MAKE-QUEUE accepts :NAME, and returns length of :INITIAL-CONTENTS as secondary value. * QUEUEP is removed. Use (TYPEP X 'QUEUE) instead. * ENQUEUE returns the queue, not the value. * SEND-MESSAGE returns the mailbox. Comments welcome, -- Nikodemus |
From: Larry V. <re...@us...> - 2008-08-06 20:15:18
Attachments:
load2.lisp
lock2.lisp
|
> Attached is my current take, this time as a patch against SBCL. Tests > are still missing (actually, I had some, but seem to have misplaced > them.) > > Slight differences to the earlier versions: > > * MAKE-MAILBOX accepts :INITIAL-CONTENTS (faster then MAKE-MAILBOX + > repeated SEND-MESSAGE.) > > * MAKE-QUEUE accepts :NAME, and returns length of :INITIAL-CONTENTS > as secondary value. > > * QUEUEP is removed. Use (TYPEP X 'QUEUE) instead. > > * ENQUEUE returns the queue, not the value. > > * SEND-MESSAGE returns the mailbox. > > Comments welcome, > > -- Nikodemus > change: + (queue (%make-queue name dummy dummy)) I'll attach my test bench, but it fails sometimes, not sure why. regards, /larry |
From: Nikodemus S. <nik...@ra...> - 2009-06-22 11:54:04
|
2008/8/6 Nikodemus Siivola <nik...@ra...>: > Attached is my current take, this time as a patch against SBCL. Tests > are still missing (actually, I had some, but seem to have misplaced > them.) The lockless queue has been committed as 1.0.29.31, as contrib module SB-QUEUE. Cheers, -- Nikodemus |