CODEWITHSUNDEEP
javamultithreadingarraylistqueue
steve
steve

Reputation: 625

Which is the more efficient threadsafe queue in java

There is a simple task: many threads call MyClass.add() function, and a thread tries to serve them.
My question: which is the better or more efficient solution?

1st approach: with CopyOnWriteArrayList

@Singleton
public class myClass {

    List<myType> list = new CopyOnWriteArrayList<myType>();
    boolean isRunning = false;

    //this is called from many threads
    public void add(myType x){
        list.add(x);
    }


    //this is called from 1 thread
    public void start(){
        if (isRunning) return;
        isRunning = true;

        while (!list.isEmpty()) {
            myType curr = list.remove(0);

            //do something with curr...
        }
        isRunning = false;
    }
}



2nd approach with simple locks:

@Singleton
public class myClass {

    List<myType> list = new ArrayList<myType>();
    boolean isRunning = false;
    private final Lock _mutex = new ReentrantLock(true);

    //this is called from many threads
    public void add(myType x){
        _mutex.lock();
        list.add(x);
        _mutex.unlock();
    }


    //this is called from 1 thread
    public void start(){
        if (isRunning) return;
        isRunning = true;

        while (!list.isEmpty()) {
            _mutex.lock();
            myType curr = list.remove(0);
            _mutex.unlock();

            //do something with curr...
        }
        isRunning = false;
    }
}



3rd approach: with ConcurrentLinkedQueue

@Singleton
public class myClass {

    ConcurrentLinkedQueue<myType> list = new ConcurrentLinkedQueue<myType>();
    boolean isRunning = false;

    //this is called from many threads
    public void add(myType x){
        list.add(x);
    }


    //this is called from 1 thread
    public void start(){
        if (isRunning) return;
        isRunning = true;

        while (!list.isEmpty()) {
            //list cannot be empty at this point: other threads can't remove any items 
            myType curr = list.poll();

            //do something with curr...
        }
        isRunning = false;
    }
}



And this was the original wrong solution. I don't know why it gave sometimes (>100 threads) ConcurrentModificationException (despite of iterator and "synchronized"):

@Singleton
public class myClass {

    List<myType> list = Collections.synchronizedList(new ArrayList<myType>());
    boolean isRunning = false;

    //this is called from many threads
    public void add(myType x){
        synchronized(list) {
            list.add(x);
        }
    }


    //this is called from 1 thread
    public void start(){
        if (isRunning) return;
        isRunning = true;

        for (ListIterator<myType> iter = list.listIterator(); iter.hasNext();){
            myType curr = iter.next();

            //do something with curr...

            synchronized(list) {
                iter.remove(); //sometime it gives ConcurrentModificationException!
            }
        }
        isRunning = false;
    }
}

Upvotes: 3

Views: 1603

Answers (1)

TwoThe
TwoThe

Reputation: 14269

The general rule is: the one that fits your problem best.

The lock variant is slowing everything down a lot, because all threads a put on hold if they enter the lock part, even though there is no need for it (if there are 5 elements, 5 threads can poll them simultaneously, only the 6th has to wait). This solution however is good, if you have a singular resource that can never be shared, like a network connection or a file.

The CopyOnWriteArrayList is the best solution, if your thread rarely writes but very often reads. There is a much higher cost associated with the write, which is compensated with the much faster read (compared to a ConcurrentLinkedQueue). But your code primarily writes, so this isn't a good solution for you.

The ConcurrentLinkedQueue is the best solution, if the amount of reads and writes are about equal, hence the name Queue. So it should fit your case the best.

In addition you have a serious error in your code:

while (!list.isEmpty()) {
  myType curr = list.poll();

The list just guarantees that each call is done atomically, but your code is not automatically thread-safe just because you use it. In this example the list could have already been modified between the isEmpty() and the poll(), so it could have 1 element on the isEmpty() call, but then none once you poll. This is handled gracefully by the ConcurrentLinkedQueue by returning null, but not by your code. So the correct form would be:

myType curr;
while ((curr = list.poll()) != null) {

As the poll is an atomic - and therefore thread-safe - call, it will either return an element or not. What happens before and what happens afterwards is undefined thanks to threading, but you can be sure that this single call (which does a lot more in the background) will always work perfectly.

The same is true for your remove(0) call, it can throw an IndexOutOfBoundsException if the last element has been removed by another thread in between.

Upvotes: 2

Related Questions