[concurrency-interest] ConcurrentLinkedBlockingQueue vs LinkedBlockingQueue

Szabolcs Ferenczi szabolcs.ferenczi at gmail.com
Mon Apr 2 08:11:08 EDT 2007


On 02/04/07, Hanson Char <hanson.char at gmail.com> wrote:

> Based on a recent test on Windows XP Professional with 1 CPU,
> ConcurrentLinkedBlockingQueue performs 83% faster than
> LinkedBlockingQueue.  Unfortunately I don't have access to a more
> powerful box (with multi-processors) to do more testings.

Hi Hanson,

I have run your performance test on a dual core XP version. Here is
the summary of the averages:

CLBQ  748+791+752+743+743+730+732+752+737+705=7433
LBQ   1271+1230+1258+1258+1221+1201+1194+1178+1206+1206=12223
LBQ/CLBQ = 0.61

However, as I have indicated earlier, your CLBQ offer/take combination
implements a busy waiting loop with some optimalization. With a simple
busy waiting loop the figures are like this:

CLBQ  776+688+739+688+702+684+675+715+708+715=7090
LBQ   1243+1243+1197+1207+1265+1265+1259+1256+1253+1261=12449
LBQ/CLBQ = 0.57

    public boolean offer(E e) {
        return q.offer(e);
    }
    public E take() throws InterruptedException
    {
        for (;;) {
            E e = q.poll();

            if (e != null)
                return e;
            if (Thread.interrupted())
            {
                throw new InterruptedException();
            }
        }
    }

I have also checked a variant with the standard conditional variable:

CLBQ  3072+2437+1967+1918+2828+1925+1930+1904+1882+1933=21796
LBQ   1261+1298+1196+1215+1212+1182+1185+1210+1198+1197=12154
LBQ/CLBQ = 1.79

    public boolean offer(E e) {
	boolean b;
	synchronized(takeLock) {
	    b = q.offer(e);
	    takeLock.notify();
	}
	return b;
    }
    public E take() throws InterruptedException
    {
	E e;
	synchronized(takeLock) {
	    while (q.isEmpty()) {
		takeLock.wait();
	    }
	    e = q.poll();
	}
	return e;
    }

Finally, I have checked the same performance test with semaphore
scheduling:

With fair semaphore:
CLBQ  3248+2637+2676+2690+2024+2197+2181+2134+2142+2139=24068
LBQ   1185+1256+1169+1201+1210+1159+1151+1162+1170+1172=11835
LBQ/CLBQ = 2.03

With unfair semaphore:
CLBQ  2473+2133+2249+2267+2226+2277+2155+2244+2284+2269=22577
LBQ   1238+1222+1200+1176+1183+1183+1293+1207+1201+1186=12089
LBQ/CLBQ = 1.87

    private final Semaphore availableItems = new Semaphore(0, true);
    public synchronized boolean offer(E e) {
        boolean b = q.offer(e);
	availableItems.release();
	return b;
    }
    public E take() throws InterruptedException
    {
	availableItems.acquire();
	synchronized(this) {
	    E e = q.poll();
	    return e;
	}
    }

My final note is that the N producer 1 consumer performance test is
not a good choice in this case. The reason is that you have added
some synchronization (lock free one) to schedule the consumers. On the
other hand the performance test omits consumer scheduling since the
N consumers make sure that the consumer should not be scheduled at the take
method since there will always be some items in the queue for the consumer.

Best Regards,
Szabolcs


More information about the Concurrency-interest mailing list