Synchronized vs ReentrantLock on performance

Question

I have been through a set of few surprises when it comes to Queue implementation for a Multithreading system. Here is:-

The Scenario:- 1 producer, 1 consumer:- A producer puts an integer into a queue. A consumer simply removes it from the queue.

The underlying data structure of the queue:- TreeSet (which I never thought I will use), LinkedList, LinkedBlockingQueue(with indefinite size)

The code:- of TreeSet as a queue:-

while (i < 2000000) {
        synchronized (objQueue) {

            if (!(objQueue.size() > 0)) {
                try {
                    objQueue.wait();
                } catch (InterruptedException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
            }
            Integer x = objQueue.first();
            if (x != null) {
                objQueue.remove(x);
                ++i;
            }
        }
    }

EDIT:-

      while (i < 2000000) {
        synchronized (objQueue) {
            objQueue.add(i);
            ++i;
            objQueue.notify();
        }
    }

For LinkedBlockingQueue:-

     while (i < 2000000){
        try {
            objQueue.put(i);
            ++i;
        } catch (InterruptedException e) {
            // TODO Auto-generated catch block
            Thread.currentThread().interrupt();
        }
    }

      while (i < 2000000) {
        try {
            objQueue.take();
            ++i;

        } catch (InterruptedException e) {
            // TODO Auto-generated catch block
            Thread.currentThread().interrupt();
        }
    }

For LinkedList :- similar code with synchronized.

The Questions:-

1) When I measured the performance via Visual VM, I observed that the for the producer code, TreeSet performs better than LinkedBlockingQueue and LinkedList, even though it takes O(log n) time, the creation of objects in Linked structures is a significant overhead. Why is the theory quite different to the practice ? Why do we prefer Linked, Array structures over Tree structures in queue implementations ?

2) The synchronized comes out as a clear winner vs the ReeentrantLock because TreeSet performed better than LinkedList which performed better than LinkedBlockingQueue. I wish I could attach the Visual VM results. It is not in votes with the article, http://www.ibm.com/developerworks/java/library/j-jtp10264/index.html

The operations are performed on

Dell Vostro 1015, core 2 duo 2.10, 2GB Ram with 32 bit operating system and with

JVM: Java HotSpot(TM) Client VM (20.1-b02, mixed mode) Java: version 1.6.0_26, vendor Sun Microsystems Inc.

Answer 1

1. ReentrantLock might be more apt to use if you need to implement a thread that traverses a linked list, locking the next node and then unlocking the current node.

2. Synchronized keyword is apt in situation such as lock coarsening, provides adaptive spinning,biased locking and the potential for lock elision via escape analysis. Those optimizations aren't currently implemented for ReentrantLock.

For a proper performance comparison see this:

https://blogs.oracle.com/dave/javautilconcurrent-reentrantlock-vs-synchronized-which-should-you-use

Answer 2

1. Because your benchmark is flawed: in a real use-case, the time taken to produce and consume elements from the queue is much more important than the time it takes to add and remove an element to/from the queue. So the raw performance of the queue is not so important. BTW, the code only shows how you take elements from the first queue implementation, and not how you add them. Moreover, the choice of the appropriate structure is not made based on performance, but on behavior. If you want something concurrent, you choose a blocking queue, because it's implemented for you and doesn't have bugs like your code has. If you want FIFO (which is often what you want), you won't choose a TreeSet.

2. If you want to compare synchronized vs. ReentrantLock, you shouldn't use one data structure for one, and another data structure for the other. ReentrantLock used to be faster, but they are on the same level, nowadays (if I believe what Brian Goetz says in JCIP). Anyway, I would choose one over the other for safety/capability reasons. Not for performance reasons.