O(1) insertion, fully non-blocking data structure

[jwaterson]

O(1) insertion, fully non-blocking data structure

[franz1981]

Most data structures provide a fail fast variant that do not block while performing insertion (not even compare and set retries). It is what you mean?

See

JCTools/jctools-core/src/main/java/org/jctools/queues/MpscArrayQueue.java

Line 330 in 66e6cbc

public final int failFastOffer(final E e)

While others still provide waitFree (bounded to population) alternatives (but still to be demonstrated), see xadd mpmc/mpsc xadd q offers.

[jwaterson]

Just a couple of questions if you don't mind @franz1981 :

1. Instead of blocking, a write might fail and optionally be reattempted? Can potential failure be avoided somehow?
2. Would MpscArrayQueue for example achieve O(1) insertions and never block write access?

I'm not familiar at all with JCTools, so thank you for your patience :)

[franz1981]

1. Yep, by using the mentioned fail fast variant
2. Same as 1

[jwaterson]

@franz1981, how is failure avoided entirely, sorry? Do you mean that with retries, failure can eventually be avoided?