Concurrency help on a custom queue-like data structure

Question

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

Must be thread-safe
Must be able to add to queue without synchronizing
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)

NB: your code is not thread safe, you need a synchronized block for the method add too — Nicolas Filotto
– Nicolas Filotto, Commented May 30, 2016 at 16:02
this is probably the reason why you get the ConcurrentModificationException in solution #2 — Nicolas Filotto
– Nicolas Filotto, Commented May 30, 2016 at 16:04
It actually is thread safe since I am only adding to the end and am synchronizing the remove. Unfortunately, the LinkedList iterator has a "dumb" check for seeing if anything changes. It would have been nice for the designers to provide a way to specify your own iterator that could have left off the training wheels. — Jon Peterson
– Jon Peterson, Commented May 30, 2016 at 22:18

Nicolas Filotto · Accepted Answer · 2016-05-30 16:27:32Z

3

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);
}

edited May 30, 2016 at 16:27

answered May 30, 2016 at 16:09

Nicolas Filotto

45.3k11 gold badges97 silver badges129 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Gandalf Over a year ago

I'd recommend that too. It uses an algorithm with separate write and read locks based on cs.rochester.edu/~scott/papers/1996_PODC_queues.pdf The link in the javadoc to that document on michaels user space is outdated X) It should provide thread safe and concurrent read and write access with high performance.

Jon Peterson Over a year ago

Awesome. I had looked briefly at this when scanning the "java.util.concurrent" package, but for some reason I ended up passing over it. Looked closer at the JavaDocs and a benchmarking blog javacodegeeks.com/2010/09/… Looks great. Thanks for pointing me back the right way.

Nicolas Filotto Over a year ago

@doge this is a different story but if T is not thread safe and it is read and modify by several threads concurrently you will face indeed issues

Abylay Sabirgaliyev Over a year ago

This is what I am talking about. If class is not completely thread-safe it is not thread-safe. This issue must be considered too. Sharing not-thread-safe state can be achieved by deep-copy.

byt3 · Accepted Answer · 2016-05-30 16:04:49Z

0

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.

answered May 30, 2016 at 16:04

byt3

1157 bronze badges

2 Comments

Jon Peterson Over a year ago

I will be writing way more than reading, so this will not work for me. Thanks anyway.

Nicolas Filotto Over a year ago

yes that's right CopyOnWriteArrayList is only interesting when you mostly read and rarely write otherwise it is a perf killer

Collectives™ on Stack Overflow

Concurrency help on a custom queue-like data structure

2 Answers 2

4 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related