Blocking peek/await in LBQ

[Cagatay Kavukcuoglu]

Hi,

I realize this was discussed before
(http://cs.oswego.edu/pipermail/concurrency-interest/2009-June/006229.html),
but I wanted to see if folks think whether there are other ways to get
equivalent functionality. My particular use case is implementing a
concurrent data structure that would allow the usual tuple space
operations like read (blocks until a matching element exists and
returns without removing), take (like read, except the element is
removed) and put, where multiple values can be "queued" while being
associated with a key. An "await" operation on LinkedBlockingQueue
would have simplified the implementation significantly; in fact, I'm
duplicating LBQ code and adding this myself at the moment. Is there a
way to do this idiomatically in j.u.c that does not involve having to
resort to code duplication?

CK.
_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Doug Lea]

Cagatay Kavukcuoglu wrote:

> Hi,
>
> I realize this was discussed before
> (http://cs.oswego.edu/pipermail/concurrency-interest/2009-June/006229.html),
> but I wanted to see if folks think whether there are other ways to get
> equivalent functionality. My particular use case is implementing a
> concurrent data structure that would allow the usual tuple space
> operations like read (blocks until a matching element exists and
> returns without removing), take (like read, except the element is
> removed) and put, where multiple values can be "queued" while being
> associated with a key. An "await" operation on LinkedBlockingQueue
> would have simplified the implementation significantly; in fact, I'm
> duplicating LBQ code and adding this myself at the moment. Is there a
> way to do this idiomatically in j.u.c that does not involve having to
> resort to code duplication?
>

Basically, this amounts to supporting a change notification
scheme for the particular event of a collection (here, a queue)
becoming non-empty.

Our resistance to supplying such things stems from not wanting
to get into the business of adding to each concurrent collection
all the different state-change mechanics (listeners? callbacks?
blocking waits?) that you could apply to all their possible events
(non-empty? empty? too big? insertion or removal of particular
elements?)  (Other library folks are less stubborn about this.
I think some Apache and Google collections have some support
for some of these options.)

But the easy cases of doing this yourself are pretty
easy. For example you could use a synchronized wrapper class
around nearly any collection or queue, adding
a notifyAll on any insertion, along with an await
method along the lines of:
   while (q.isEmpty() == null) wait();
Although, if the single lock you'd need here for the wait/notify
becomes a serious scalability problem, you'd need a more
complicated solution.


-Doug
_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Cagatay Kavukcuoglu]

On Sat, Oct 31, 2009 at 8:34 AM, Doug Lea <dl@...> wrote:

> Cagatay Kavukcuoglu wrote:
>>
>> Hi,
>>
>> I realize this was discussed before
>>
>> (http://cs.oswego.edu/pipermail/concurrency-interest/2009-June/006229.html),
>> but I wanted to see if folks think whether there are other ways to get
>> equivalent functionality. My particular use case is implementing a
>> concurrent data structure that would allow the usual tuple space
>> operations like read (blocks until a matching element exists and
>> returns without removing), take (like read, except the element is
>> removed) and put, where multiple values can be "queued" while being
>> associated with a key. An "await" operation on LinkedBlockingQueue
>> would have simplified the implementation significantly; in fact, I'm
>> duplicating LBQ code and adding this myself at the moment. Is there a
>> way to do this idiomatically in j.u.c that does not involve having to
>> resort to code duplication?
>>
>
> Basically, this amounts to supporting a change notification
> scheme for the particular event of a collection (here, a queue)
> becoming non-empty.
>
> Our resistance to supplying such things stems from not wanting
> to get into the business of adding to each concurrent collection
> all the different state-change mechanics (listeners? callbacks?
> blocking waits?) that you could apply to all their possible events
> (non-empty? empty? too big? insertion or removal of particular
> elements?)  (Other library folks are less stubborn about this.
> I think some Apache and Google collections have some support
> for some of these options.)
>

My personal opinion is that this is a niche feature that only becomes
useful for a small minority and it's okay if that minority has to jump
through hoops as long as *some* solution is feasible. I do appreciate
the simplicity of the concurrent collections in j.u.c.

> But the easy cases of doing this yourself are pretty
> easy. For example you could use a synchronized wrapper class
> around nearly any collection or queue, adding
> a notifyAll on any insertion, along with an await
> method along the lines of:
>  while (q.isEmpty() == null) wait();

Thanks, this makes more sense than duplicating code for the blocking queue.

> Although, if the single lock you'd need here for the wait/notify
> becomes a serious scalability problem, you'd need a more
> complicated solution.

This probably will be a problem later on but I can live with the
limitations at the moment. I was experimenting with something along
the lines of a new synchronizer based on AQS that blocks readers until
a value is provided (this part is easy - a bit like data
flow/FutureTask) and can be reset (this part turns out to be hard) to
represent the queue head. This was my first attempt at using AQS and
lock-free primitives for coordination; it's fun to work on, but hard
to write and test for.

>
>
> -Doug
>

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest