vitpro2213

Will have a look at it, thanks

Hi jauntywundrkind, just to make sure we have the same understanding:

The smaller arrays are not "left behind" in the garbage sense - the queue will use them again and again in the next rounds. See simulator. Re-use, not Re-cycle - the Garbage-Free Mantra.

If the Queue re-cycles the smaller arrays, it would not be garbage-free anymore.

If you still believe that the smaller arrays should be re-cycled (would be curious why), then comes the technical problem:

Let's imagine a reader stands immediately before reading the array (e.g. to check if the writer has already written). Now the OS preempts him. For how long: We don't know. In the meantime all things in the queue move forward and the program code in some other thread (writer probably) decides to de-allocate the array (and indeed does it).

Now the preempted reader wakes up and the first thing it does is to read from that (deallocated) array ...

With ConcurrentMultiArrayQueue, there can be N threads INSIDE of the program code of the Queue, running or preempted (for a not predictable time) and you cannot control it.

Removing anything in non-blocking structures is problematic, see e.g. the referenced lecture of Professor Scott.

You never know how many concurrent threads still "are" on the place you wish to remove.

You would have to deal with stuff like hazard pointers, limbo lists and the like.

Better to keep the small arrays there.

Implementing Queue would mean also implementing Collection and Iterable, and this would bring pains and ugliness, especially with the concurrent code.

Look e.g. at the disclaimers at the size method of java.util.concurrent.ConcurrentLinkedQueue.

Thanks, will look at it.

I actually thought the same: Given e.g. the complex structures published in ACM papers, it would be a surprise if MultiArrayQueue would be a completely new discovery.

We are not in the pioneer years of 1960's anymore (unfortunately :-))

If you discard the old array (and allocate a bigger one before), you must also copy all enqueued material.

Also this one enqueue will be mega expensive - a clear "fat tail" in the latency histogram.

In MultiArrayQueue you keep all already enqueued material in-place, "just" allocate the bigger array, register the new diversion, enqueue the one new element - and done.

Thanks