java - 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