Wait-free queue implementation in JAVA

Question

I've been trying to use already written Wait-free queue by Alex Kogan and Erez Petrank taken from here, but faced the problem. I can't understand that exactly thread ID need to be used in que() and deque() methods on page 5 and 7:

void enq(int value) {
    long phase = maxPhase() + 1; // cf. Figure 3b
    state.set(TID, new
        OpDesc(phase, true, true, new Node(value, TID)));
    help(phase);
    help finish enq();
}

And

int deq() throws EmptyException {
    long phase = maxPhase() + 1; // cf. Figure 5a
    state.set(TID, new OpDesc(phase, true, false, null));
    help(phase);
    help finish deq();
    Node node = state.get(TID).node;
    if (node == null) {
        throw new EmptyException();
    }
    return node.next.get().value;
}

What thread id should used?

Answer 1

In the paper they says that TID is an int in the range [0, . . . , NUM THRDS−1]., so it looks like it is a manually assigned number.

I've not read the paper, so I don't know if there is a strict requirement only to use an identifier meeting this specification. There is a long getId() method on java.lang.Thread. See the Javadoc for Thread.getId():

Returns the identifier of this Thread. The thread ID is a positive long number generated when this thread was created. The thread ID is unique and remains unchanged during its lifetime. When a thread is terminated, this thread ID may be reused.

You may be able to use this instead of assigning the TIDs yourself.

Answer 2

I have to say I am not convinced by your choosing such a non-standard queue implementation given all the queue choices concurrency package in JDK.

Firstly, from the method you posted, the worst performance of the deq() method is poor. It throws exception upon queue empty which is utterly expensive for any application which needs such a wait free queue.

Secondly the performance measurement in the paper is based on dynamically allocated queue; where memory allocation fragmentation and page fault would be the major performance penalty here. In reality, one can easily estimate the normal case maximum queue length by peak arrival rate * peak lasting period and set the queue to be statically allocated with that capacity. Any case the producer is trying to put with queue full can simply be suspended (and is very unlikely to happen). Even if such scenario happens, the performance penalty of thread parking is usually in terms of 1 millisecond.

In case you are looking for delay of less than 1 millisecond in a real-world production system, Java is probably not the right tool for you. Without fine-turned memory alignment, it's very difficult if any possible to achieve so. Yes LMAX did it with Disruptor but IMHO only by adding some custom memory management packages to JVM.

So from all practice perspective, you should either use standard queues in JDK, or turn to Disruptor, or use C/C++. This data structure itself with a unproven implementation is just no a right choice.