java - 具有非常具体要求的高性能、无锁 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. 根本不要使用迭代器(因此 for-each 而不是 Collection)，因为 Collection.iterator() 会准备 Iterator 的新实例，顺便说一句，它的 next() 方法不是免费的: ) 每次使用 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 足以保证作者和所有读者之间的所有变化的可见性读者。此外，如果延迟对您来说很重要，您可以将经典锁替换为忙等待以获得无锁收集。

您应该了解的主要事情是，在许多情况下，针对非常具体的要求，最高效的解决方案是编写一段您自己的微调代码。这就是不为您并不真正使用的东西付费的方法。这就是高性能/低延迟应用程序通常不在其主要路径中使用常见的第 3 方库的原因