Implement intrusive linked queue MPSC

[nitsanw]

This was found to be a useful usecase in Netty for internal uses where long/medium lived events are passed between threads and we wish to avoid the allocation of nodes by having the entity extend a node. The API changes to the following:

Queue<N extends Node> {
   boolean offer(N n);
   N poll();
...
}

It would be good if @normanmaurer could comment on usage pattern or any further detail relating to the usecase.

[nitsanw]

see related discussion in https://github.com/netty/netty/pull/5051

[sirthias]

I'd like to voice strong support for this ticket! The intrusive sibling of the already implemented MpscLinkedQueue would be a very attractive addition for sure. I'd definitely prefer it over the non-intrusive variant in all cases where the universe of queue inhabitant types is closed and under my control, which is (for me) the majority.

Outline: http://www.1024cores.net/home/lock-free-algorithms/queues/intrusive-mpsc-node-based-queue

[normanmaurer]

@nitsanw sorry I totally missed this 😢

So the use-case for us was basically that we had full control over the queue and just wanted to add "one-time-events", which for example is a Runnable that is only needed one time. For this to be able to have this also be the node itself reduce the GC dramatically. So yes, please :)

[nitsanw]

@sirthias @normanmaurer OK, will get to it. This is not a blocking issue for JCTools dependency is it?

[normanmaurer]

@nitsanw not for me atm... Just running final tests here before doing the cherry-pick FTW :)

[sirthias]

@nitsanw for me neither, but it would definitely sweeten the pie... :)

[nitsanw]

@sirthias I live to sweeten :)

[sirthias]

@nitsanw This is not to say that the pie isn't already attractively sweet! But the top still sports some space for a few cherries... :)

[normanmaurer]

+1

Am 10.06.2016 um 12:22 schrieb Mathias [email protected]:

@nitsanw This is not to say that the pie isn't already attractively sweet! But the top still sports some space for a few cherries... :)

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or mute the thread.

[pcholakov]

Has anyone started work on this yet? Would you like to maintain the existing MpscLinkedQueue interface exactly as is, and introduce a new (say) MpscIntrusiveLinkedQueue alongside it that would implement Queue<E extends Node>? What will be the strategy for dealing with node objects? Currently LinkedQueueNode contains some of the read/write logic. As a first pass, should we just ask users of the new MpscIntrusiveLinkedQueue to extend the existing LinkedQueueNode themselves?

[nitsanw]

I gave this some thought:

1. Implementing a mixed queue is more complex, and not the use case.
2. We can't take care of the case where the user enqueues the same element twice, or to 2 queues.
3. We therefore need a minimal interface implementation here.

We need to review the Netty usecase and see if the intrusive queue is assumed to be a java.util.Queue.

[nitsanw]

@pcholakov please throw what you got into a PR and we can close this?

[pcholakov]

GitHub noob - I tried to link it to this issue but ended up creating a separate #131. Comments? (Tips how to merge the two?)

[nitsanw]

OK, so first cut is in, I'll follow up with some refactoring and we can look at a review from Netty guys. This will not be in 2.0 release.