High performance, lock free Java collection with very specific requirements

If you are looking for a "fast enough" solution, you can use ConcurrentLinkedQueue. The well-known problem of memory leak in its Iterator.remove() was fixed as a part of http://bugs.java.com/view_bug.do?bug_id=6785442. Now removed ConcurrentLinkedQueue$Node's should be GC'ed successfully. But if you are looking for the most performant solution, then...

1. Don't use iterators at all (and for-each over Collection, therefore), since Collection.iterator() prepares new instance of Iterator and, btw, its next() method isn't for free :) Each time when you iterate a collection with Iterator, you spend CPU time for at least: about 10 instructions to allocate memory for new object + a number of instructions of constructor (see sources of ConcurrentLinkedQueue$Itr) + ConcurrentLinkedQueue$Itr.next() + removing of the object from Eden on minor GC.

2. Plain array+direct indexing is the fastest technique of iterating. So, use CopyOnWriteArrayList or implement your own collection to use a plain array to iterate over a number of items. For example, if you add/remove items very rarely and you'd prefer to remove them while iterating rather than to remove by index, you could try something like the following:

   public enum IterationResult { NEXT, REMOVE, BREAK; } public interface CollectionIterator<T> { IterationResult onObject(T object); } public interface CollectionModification<T> { CollectionModification<T> add(T item); CollectionModification<T> remove(T item); } public class MyCollection<T> { private volatile State state; private final ReentrantLock modificationLock = new ReentrantLock(); private State currentModification; public MyCollection() { this(10); } public MyCollection(int initialSize) { state = new State(initialSize); } public CollectionModification<T> startModification() { modificationLock.lock(); currentModification = new State(state); return currentModification; } public void finishModification() { state = currentModification; modificationLock.unlock(); } @SuppressWarnings("unchecked") public void iterate(CollectionIterator<T> it) { final State currentState = state; State modifiedState = null; try { out_: for (int i = 0; i < currentState.size; i++) { final T item = (T) currentState.items[i]; // unchecked final IterationResult result = it.onObject(item); switch (result) { case BREAK: break out_; case REMOVE: if (modifiedState == null) { modifiedState = (State) startModification(); } modifiedState.removeExactly(item); break; default: break; } } } finally { if (modifiedState != null) { finishModification(); } } } private class State implements CollectionModification<T> { private Object[] items; private int size; private State(int initialSize) { items = new Object[initialSize]; } private State(State from) { items = new Object[from.items.length]; size = from.size; System.arraycopy(from.items, 0, items, 0, size); } @Override public CollectionModification<T> add(T item) { if (size == items.length) { final Object[] newItems = new Object[size + size >>> 1]; System.arraycopy(items, 0, newItems, 0, size); items = newItems; } items[size] = item; size++; return this; } @Override public CollectionModification<T> remove(T item) { for (int i = 0; i < size; i++) { if (Objects.equals(item, items[i])) { removeItem(i); break; } } return this; } private void removeExactly(T item) { for (int i = 0; i < size; i++) { if (item == items[i]) { removeItem(i); break; } } } private void removeItem(int index) { if (index < items.length - 1) { System.arraycopy(items, index + 1, items, index, size - 1); } size--; } } } 

Usage:

 CollectionIterator<Integer> remove2 = new CollectionIterator<Integer>() { @Override public IterationResult onObject(Integer object) { return object == 2 ? IterationResult.REMOVE : IterationResult.NEXT; } }; MyCollection<Integer> col = new MyCollection<>(); CollectionModification<Integer> mod = col.startModification(); try { mod.add(new Integer(1)) .add(new Integer(2)) .add(new Integer(3)); } finally { col.finishModification(); } col.iterate(remove2); 

This is very similar to CopyOnWriteArrayList. BTW, if you have only one thread which modifies the collection (single writer) and many readers, you can get rid off the lock, since volatile is enough to guarantee visibility of all changes between the writer and all readers. Also, you could replace the classic lock by a busy-wait to get lock-free collection if latency is important for you.

The main thing you should understand is that in many cases the most performant solution for very specific requirements is to write a piece of your own fine tuned code. That's the way to don't pay for things you don't really use. That's why high performance/low-latency apps usually don't use common 3rd party libs in their main paths