[concurrency-interest] Quest for the optimal queue

√iktor Ҡlang viktor.klang at gmail.com
Wed Jun 6 08:17:50 EDT 2012

On Mon, May 14, 2012 at 9:19 AM, Michael Barker <mikeb01 at gmail.com> wrote:

> > The problem with batch dequeues is that if one of the messages fail we
> need
> > to be at a stable state, and doing that would mean store away the
> remaining
> > batch, which would bump the processors size by atleast a reference, which
> > can be expensive if you have millions of them.
> If you are will to stay away from the standard Java collections API,
> then I was thinking of a call with a more functional style.  E.g.
> (pseudo code)
>    public void foreach(Callback callback) {
>        Node current = head;
>        if (current.next == null) {
>            return;
>        }
>        try {
>            do {
>                Object value = current.value;
>                callback.onEvent(value);
>                current = current.next;
>            } while (current.next != null);
>        } finally {
>            updateHead(current);  // Do the appropriate thread-safe
>                                            // update to head
>        }
>    }
>    private static interface Callback
>    {
>        void onMessage(Object o);
>    }
> In the above case, if an exception thrown when handling the message,
> then the message that caused the exception is redelivered.  The
> collection is then responsible for maintaining a stable state in the
> case of an exception and the definition of that behaviour is part of
> the contract for the collection.
> I think there is also an interesting optimisation here.  The reason
> I've added the short circuit check at the top of the method is that I
> think it removes the only possible case where you could have write
> contention with producers and consumers.  The only time a consumer and
> a producer would contend on a write would be if the queue was empty.
> I.e. head == tail.  If we remove that case from the consumer then
> producers and consumers should never have a write conflict.  The
> updateHead() method used by the consumer may not need a CAS, it is
> possible that you could get away with a lazySet, which would certainly
> improve performance.  Someone should check my reasoning though.

Sorry for coming back to this after all this time,
you've got a very interesting idea here, I hope I'll find some time so see
if it may work out.
Unfortunately, this will break out APIs so it might not be feasible from
that point of view,
but if it is significantly more efficient then that's I price I'd be
willing to pay!



> > It's an interesting problem though. I've been thinking about how to
> handle
> > producer conflicts as cheap as possible, as there are no consumer
> conflicts.
> That's a tough one.  The most complicated code in the Disruptor is
> dealing with this case and we've ended up with 2 strategies based on
> the ratio of producer threads to available cores. With an array-backed
> queue this is easier, but I think for your use case you need something
> list-backed.
> Mike.

Viktor Klang

Akka Tech Lead
Typesafe <http://www.typesafe.com/> - The software stack for applications
that scale

Twitter: @viktorklang
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20120606/5a5e2610/attachment.html>

More information about the Concurrency-interest mailing list