Lock-free DoubleBufferedList

I posted this on SO and would appreciate any ideas on it's stability.

Much like the old double-buffering algorithm, this uses a List to which are added entries. You can also take the list at any time, it will be atomically replaced with a new empty one.

Both adding and removing is thread safe. You can add from many threads and remove from many threads.

Most of the code is test code - everything after the //TESTING comment. My test consists of creating a number of producer and consumer threads and passing a known number of Widgets through. If all sent items appear on the other side correctly without loss or duplication my test passes.

Can anyone think of more tests?

Has anyone any general thoughts on the code?

```
public class DoubleBufferedList {
// Atomic reference so I can atomically swap it through.
// Mark = true means I am adding to it so momentarily unavailable for iteration.
private AtomicMarkableReference> list = new AtomicMarkableReference<>(newList(), false);

// Factory method to create a new list - may be best to abstract this.
protected List newList() {
return new ArrayList<>();
}

// Get and replace the current list.
public List get() {
// Atomically grab and replace the list with an empty one.
List empty = newList();
List it;
// Replace an unmarked list with an empty one.
if (!list.compareAndSet(it = list.getReference(), empty, false, false)) {
// Failed to replace!
// It is probably marked as being appended to but may have been replaced by another thread.
// Return empty and come back again soon.
return Collections.emptyList();
}
// Successfully replaced an unmarked list with an empty list!
return it;
}

// Grab and lock the list in preparation for append.
private List grab() {
List it;
// We cannot fail so spin on get and mark.
while (!list.compareAndSet(it = list.getReference(), it, false, true)) {
// Spin on mark - waiting for another g

Old question, new review.... I think, in general, I don't believe you are actually building anything better than what can be done with regular locking..... let me rephrase that to: the risk of spin-looping during an add is a significant drawback over regularly locked systems.

So, while AtomicReferences may in fact be (marginally) faster than a ReentrantLock or a synchronization lock, the CPU cost of a spin while waiting for a 'slow' add(T....values) may in fact be significant.

Another problem is that you may in fact be over-supplying new List instances. For example, you have to create a new List() for every get(), but, if the current list is empty this is a waste. Also, it's a waste if the buffer is locked. This may add up to quite a lot of waste.

While talking about this area of code, to get around Generic warnings, you should stop using Collections.EMPTY_LIST and instead use the type-safe and generics-friendly Collections.emptyList() (See the Javadoc).

So, as an academic exercise, I think your code is reasonable, but unnecessarily cumbersome. I think a simpler lock will suffice, produce better looking code, and provides functionality that you may not even consider now (like a blocking get() that only returns when data is available)

Bottom line is that I don't believe your solution will have a noticable gain over something more simple/traditional. Certainly your solution has a number of complicated and esoteric concepts.... the Mark-flag is challenging, and the spin-lock-wait process is inefficient.

So consider this alternative:

private List mylist = newList();
private final ReentrantLock mylock = new ReentrantLock();

// Factory method to create a new list - may be best to abstract this.
protected List newList() {
    return new ArrayList<>();
}

// Get and replace the current list.
public List get() {
    // Atomically grab and replace the list with an empty one.
    mylock.lock();
    try {
        if (mylist.isEmpty()) {
            return Collections.emptyList();
        }
        final List ret = mylist;
        mylist = newList();
        return ret;
    } finally {
        mylock.unlock();
    }
}

// Add an entry to the list.
public void add(T entry) {
    mylock.lock();
    try {
        mylist.add(entry);
    } finally {
        mylock.unlock();
    }
}

// Add many entries to the list.
public void add(List entries) {
    // Atomically grab and replace the list with an empty one.
    mylock.lock();
    try {
        mylist.addAll(entries);
    } finally {
        mylock.unlock();
    }
}

// Add a number of entries.
public void add(T... entries) {
    // Make a list of them.
    add(Arrays.asList(entries));
}

The above solution can be extended easily (in ways the AtomicMarkedReference cannot), for example, creating a Condition on the Lock would allow you to have a blocking get(), and other neat tricks.

StackExchange Code Review Q#23275, answer score: 3