高性能,无锁Java集合,具有非常特殊的要求

Question

什么是适合具有以下要求的高性能并发集合的候选者:

1. 集合中的元素数量很少(少数元素,通常少于10个)并且很少发生变化.
2. 主要用例是迭代元素.这种情况发生了很多,并且必须超快(即应该是无锁的).
3. 偶尔会使用迭代器remove()方法删除一个元素.这应该最好也能很快地工作(但它不如迭代器next()方法重要).
4. 元素的顺序是无关紧要的,因此元素如何插入集合并不重要.
5. 最好来自标准Java库的东西.

我考虑过使用ConcurrentLinkedQueue <>,但是如果你从不调用poll()方法,我会发现它会泄漏内存(按设计).我不确定是否仍然如此(提到这些的帖子来自〜2011年,我发现有人提到这可能已经解决了).

我也考虑过ConcurrentSkipListSet <>,但我不确定排序对性能的影响是什么(因为我不关心顺序).

Answer 1

如果您正在寻找"足够快"的解决方案,可以使用ConcurrentLinkedQueue.其Iterator.remove()中众所周知的内存泄漏问题已修复为http://bugs.java.com/view_bug.do?bug_id=6785442的一部分.现在删除了ConcurrentLinkedQueue $ Node应该已成功GC.但如果您正在寻找性能最佳的解决方案,那么......

1. 因为Collection.iterator()准备Iterator的新实例,并且btw,它的next()方法不是免费的:)每次迭代时都不要使用迭代器(以及for-each over Collection)使用Iterator的集合,至少花费CPU时间:大约10条指令为新对象分配内存+一些构造函数的指令(参见ConcurrentLinkedQueue $ Itr的源代码)+ ConcurrentLinkedQueue $ Itr.next()+删除对象来自伊甸园的小型GC.

2. 普通数组+直接索引是最快的迭代技术.因此,使用CopyOnWriteArrayList或实现您自己的集合来使用普通数组迭代许多项.例如,如果您很少添加/删除项目,并且您希望在迭代时删除它们而不是按索引删除它们,则可以尝试类似以下内容:

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

用法:

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

这与CopyOnWriteArrayList非常相似.顺便说一句,如果你只有一个修改集合的线程(单个编写器)和许多读者,你可以摆脱锁定,因为volatile这足以保证作者和所有读者之间所有变化的可见性.此外,如果延迟对您很重要,您可以通过忙等待替换经典锁定以获得无锁定收集.

您应该理解的主要事情是,在许多情况下,针对特定要求的最高性能解决方案是编写一段您自己的微调代码.这是不付你没用的东西的方法.这就是为什么高性能/低延迟应用程序通常不会在其主要路径中使用常见的第三方库