CODEWITHSUNDEEP
javamultithreadingdata-structuresconcurrency
Jon Peterson
Jon Peterson

Reputation: 2996

Concurrency help on a custom queue-like data structure

I am trying to implement an insertion-performance-focused, queue-like data structure that must meet the following requirements:

  1. Must be thread-safe
  2. Must be able to add to queue without synchronizing
  3. Must be able to get a "snapshot" view of the queue

My issue is getting the 'snapshot' view in a way that doesn't require synchronization of the insert. Since I can block the removal and elements can only be added to the end, getting the elements shouldn't be an issue. The problem I keep running into is that the LinkedList's iterator has an unsupressable concurrent modification fast-fail baked in and 'LinkedList.get(int)' is O(n).

Below is a pared-down example of where I am with what should be a fairly simple task.

public class SnapshotableQueue<T> {
    private final LinkedList<T> queue = new LinkedList<>();
    private final Object removeLock = new Object();

    public void add(T element) {
        queue.add(element);
    }

    public T remove() {
        synchronized(removeLock) {
            return queue.remove();
        }
    }

    public List<T> getSnapshot() {
        synchronized(removeLock) {
            int length = queue.size();
            List<T> snapshot = new ArrayList<>(length);

            ???

            return snapshot;
        }
    }
}

Unacceptable Solution #1

for(int i = 0; i < length; i++)
    snapshot.add(snapshot.get(i));

'LinkedList.get(int)' is O(n)

Unacceptable Solution #2

Iterator<T> iterator = queue.iterator();
for(int i = 0; i < length; i++)
    snapshot.add(iterator.next());

Isn't thread-safe (throws ConcurrentModificationException)

Unacceptable Solution #3

Change queue to ArrayList

'ArrayList.remove(0)' is O(n)

Upvotes: 1

Views: 104

Answers (2)

Nicolas Filotto
Nicolas Filotto

Reputation: 44965

Don't reinvent the wheel, use ConcurrentLinkedQueue instead of LinkedList then use the iterator() to build your snapshot which is natively thread safe.

Your method getSnapshot will then be simply

public List<T> getSnapshot() {
    return new ArrayList<>(queue);
}

Upvotes: 3

byt3
byt3

Reputation: 115

There is this one in Java CopyOnWriteArrayList it's part of the concurrent package and seems to do exactly what you want.

But mind that it creates a copy of the list every time you insert something, so it should only be used in scenarios were you read a lot more than you write.

Upvotes: 0

Related Questions