Enhancement request: lparallel.queue:poll-queue

[lhope]

I am using concurrent queues for some simple inter-thread communication, and I couldn't find a way to poll a queue with a timeout.

I don't know the codebase well enough to make an addition, but it'd be nice if there was a (lparallel.queue:poll-queue timeout-in-millis) or an enhancement to try-pop-queue to tale an optional timeout-in-millis argument.

I'd really rather not do busy-waiting or some other workaround.

[PuercoPop]

I may be mistaken but it looks to me that right such a function on top of try-pop-queue would be straightforward.

(defun poll-queue (queue timeout)
  (let ((initial-time (get-universal-time)))
    (labels (iter ()
                  (let ((result (try-pop-queue queue)))
                    (if (or result 
                            (< timeout (- (get-universal-time) initial-time)))
                        result
                        (iter))))
      (iter))))

It should be even shorter and clearer with a loop, but I'm still not comfortable writing them without a repl to test them.

[lhope]

@PuercoPop You're right, that sort of implementation is straightforward, especially with loop. However it has a couple of issues:

1. Major: It uses busy waiting, which is no good.
2. Minor: It only has 1 second resolution for the timeout. Something like milliseconds is much better.

[lhope]

I just realised there's a bordeaux-threads macro with-timeout which should have the desired effect.

[lmj]

A safe try-pop-queue with :timeout would require implementation-dependent constructs not provided by bordeaux-threads.

One of the reasons lparallel.queue is orphaned from the lparallel package is to maintain the distinction (at least conceptually) between a replaceable utility and lparallel proper. In SBCL, lparallel.queue may be replaced with sb-concurrency:mailbox which has sb-concurrency:receive-message that accepts a :timeout. Well, SBCL mailboxes are unbounded so it's not quite a drop-in replacement (lparallel.queue can be bounded or unbounded depending on :fixed-capacity).

I believe a portable queue with timeout would require (at least) with-interrupts/without-interrupts from the implementation and more interrupt-safety inside bordeaux-threads itself. There are trade-offs as well; lparallel.queue is faster than SBCL's mailbox presumably due to lack of this feature.

[lmj]

@lhope, be careful using with-timeout. Most lisp code is not interrupt-safe, and not expected to be. After each line of code you have to ask yourself, "What if there is an interrupt here?" For example binding a variable with cleanup requires a construct like unwind-protect/safe-bind.

[lhope]

@lmj Thanks for the analysis. For my use case, this is a one-off. I normally do this sort of thing with ZeroMQ. For various reasons I wanted to cut ZeroMQ out of the equation in this application. I like message queue based concurrency because a lot of the dramas with shared state etc go away (or are hidden by the framework).

A question on with-timeout: is pop-queue interrupt safe?

I did a workaround in this case which pushes to a separate concurrent queue which is listened to by a separate thread. This thread then does the sleeping and 'wakes' the main thread by pushing a wake command onto the queue after that time.

Thanks for your input!

[lmj]

Hi, bordeaux-threads is not interrupt-safe, so neither is pop-queue. But note that even if pop-queue were interrupt-safe, one would still have the nearly-forlorn task of guaranteeing that everything surrounding the pop-queue call is interrupt-safe.

This emphasizes the need for pop-queue with :timeout, and hence for bordeaux-threads to be safer. Bordeaux-threads isn't too bad really, the main issue is Clozure with its lack of condition variables. I once posted an interrupt-safe condition-wait to the bordeaux-threads mailing list, but I wasn't confident I understood the implications of suspending/resuming interrupts on CCL.

Also note that code can still be safe despite interrupt-unsafety. If you know that you're already inside the implementation's equivalent of condition-wait, then it's OK. And the kind of miniscule-probability failures that interrupt-safety solves have existed inside Lisp implementations for years without anyone noticing. Scary but true.

[lhope]

I was thinking that my workaround above could be useful in a general way. I can create a pollable-queue that spawns a separate wait thread which pushes wake commands to the queue. The wake command could be an internal gensym, which means the wake command would never be confused with a real item in the queue.

The downside is that we spawn an additional thread per pollable-queue, and so the queue needs a destructor to clean up this thread (by issuing a die command to the thread).

The upside is a pollable queue that does not use interrupts.

Is this sort of thing something you'd accept into lparallel? If I do this, I would first put it in a separate project, but I'd have no problem with it being merged it into the lparallel codebase.

[lmj]

I recently posted an interrupt-safe bordeaux-threads:condition-wait to the CCL mailing list, and it appears to be acceptable. Placing with-timeout around condition-wait is basically all that is needed (along with a check for spurious wakeups). It's best to take advantage of native timeouts if the Lisp implementation provides them. So barring unforeseen circumstances this will eventually get into lparallel.

The downside comes when there is no native timeout or for some reason bordeaux-threads doesn't use it, in which case bordeaux-threads defaults to creating a new thread on each with-timeout (CCL falls into this category). Your proposal is essentially an optimization for that. That may conceivably be sometimes needed, but the long-run aim would be to fix either bordeaux-threads or the Lisp implementation.

[lhope]

Thanks for the feedback. It's why I asked here, since you have much more knowledge of the domain than I do. I'll get to studying bordeaux-threads in more detail.

[lhope]

Here's a very simple implementation: https://gist.github.com/lhope/6547835 What do you think? Is it safe?

I looked in the queue code and you use condition-wait and condition-notify within the pop-queue and push-queue. Do I need to worry any further than that?

Also, do I need to loop and re-check the elapsed time to ensure no 'spurious wakeups' as you called them?

[lmj]

The with-timeout has to go directly around the condition-wait. In your example, an interrupt can happen immediately after popping the raw data structure, causing a return of (values nil nil) with the popped element being lost. I've pushed a rough prototype to q-timeout which adds a :timeout option to try-pop-queue.

This is all in interest of making things airtight, on the assumption that the least probable failure will occur at the worst possible time. I haven't considered what circumstances cause what probability of failure; in typical cases it may be very rare indeed.

[lmj]

I've sent a patch to the bordeaux-threads mailing list that adds a :timeout option to condition-wait. Since the patch avoids with-timeout there will be no downsides even for CCL (if the patch is accepted).

[lhope]

I had a look at the patch. I hope it gets accepted! :-) I agree the problem is best solved at the root, which seems to be first Bordeaux-Threads, and then your library. Application-level code is not the right place.

[lmj]

lparallel-2.5.0 adds a :timeout option to try-pop-queue.

[lhope]

Thanks very much for adding this feature! :)