高性能、无锁 Java 具有非常具体要求的集合

Question

满足以下要求的高性能并发集合的合适候选对象是什么：

集合中的元素数量很少（很少的元素，通常少于10个）并且很少变化。
主要用例是遍历元素。这种情况经常发生并且必须非常快（即应该是无锁的）。
有时会使用迭代器 remove() 方法删除元素。这最好也能非常快地工作（但它不如迭代器 next() 方法重要）。
元素的顺序无关紧要，因此元素如何插入到集合中并不重要。
最好是来自标准 Java 库的内容。

我考虑过为此使用 ConcurrentLinkedQueue<>，但发现如果您从不调用 poll() 方法，它会泄漏内存（按设计）。我不确定情况是否仍然如此（提到这个的帖子是从 ~ 2011 年开始的，我发现一些提到这可能已经被解决）。

我也考虑过 ConcurrentSkipListSet<>，但我不确定排序对性能有什么影响（因为我不关心顺序）。

Answer 1

如果您正在寻找 "fast enough" 解决方案，您可以使用 ConcurrentLinkedQueue。 Iterator.remove() 中众所周知的内存泄漏问题已作为 http://bugs.java.com/view_bug.do?bug_id=6785442 的一部分得到修复。现在已删除的 ConcurrentLinkedQueue$Node 应该可以成功进行 GC。但是，如果您正在寻找性能最高的解决方案，那么...

根本不要使用迭代器（因此 for-each over Collection），因为 Collection.iterator() 准备 Iterator 的新实例，顺便说一句，它的 next() 方法不是免费的 :) 每次使用 Iterator 迭代集合时，您至少花费 CPU 时间：大约 10 条指令为新对象分配内存 + 构造函数的一些指令（参见 ConcurrentLinkedQueue 的来源$Itr) + ConcurrentLinkedQueue$Itr.next() + 在次要 GC 上从伊甸园中移除对象。

普通数组+直接索引是最快的迭代技术。因此，使用 CopyOnWriteArrayList 或实现您自己的集合以使用普通数组迭代多个项目。例如，如果您很少 add/remove 项目并且您更愿意在迭代时删除它们而不是按索引删除，您可以尝试如下操作：

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 足以保证作者和所有读者之间的所有更改的可见性。此外，如果延迟对您很重要，您可以用忙等待替换经典锁以获得无锁收集。

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

Answer 2

我运行一些测试。这不是一个完美的测试，但它给出了性能差异的概念。

程序：

import java.util.*;
import java.util.concurrent.*;

public class Main {

    public static void main(String[] args) {

        testCollection(new ArrayList<Integer>());
        testCollection(Collections.synchronizedList(new ArrayList<Integer>()));
        testCollection(new CopyOnWriteArrayList<Integer>());
        testCollection(new LinkedList<Integer>());
        testCollection(Collections.synchronizedList(new LinkedList<Integer>()));
        testCollection(Collections.newSetFromMap(new ConcurrentHashMap<Integer, Boolean>()));
        testCollection(new ConcurrentLinkedQueue<Integer>());
        testCollection(new ConcurrentSkipListSet<Integer>());
    }

    static void testCollection(Collection<Integer> collection) {
        testCollection(collection, 3);
    }

    static void testCollection(Collection<Integer> collection, int count) {

        Test t = new Test(collection);

        for (int i = 0; i < 10; i++)
            System.gc();

        while (count > 0) {
            long time = 0, iterationTime;

            for (int x = 0; x < 1010; x++) {
                iterationTime = t.timeIteration();
                if (x >= 10) { // skip first 10 runs results to reduce the effect of runtime optimizations 
                    time += iterationTime;
                }
            }

            System.out.println(collection.getClass() + ": " + time / 1000000.0 + " milliseconds");
            count--;
        }
    }

    static class Test {

        private Collection<Integer> list;

        public Test(Collection<Integer> list) {
            list.addAll(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10));
            this.list = list;
        }

        long timeIteration() {
            Iterator<Integer> iterator;
            long start = System.nanoTime();
            for (int i = 0; i < 10000; i++) {
                for (iterator = list.iterator(); iterator.hasNext(); ) {
                    Integer x = iterator.next();
                    if (x > 20)
                        System.out.println("this doesn't happen");
                }
            }

            return System.nanoTime() - start;
        }
    }
}

结果：（为清楚起见格式化）

╔══════════════════════════════════════════╦══════════════╗
║            class (java.util.)            ║ milliseconds ║
╠══════════════════════════════════════════╬══════════════╣
║ ArrayList                                ║ 138.242208   ║
║------------------------------------------║--------------║
║ ArrayList                                ║ 135.795334   ║
║------------------------------------------║--------------║
║ ArrayList                                ║ 160.516023   ║
║------------------------------------------║--------------║
║ Collections$SynchronizedRandomAccessList ║ 371.29873    ║
║------------------------------------------║--------------║
║ Collections$SynchronizedRandomAccessList ║ 318.442416   ║
║------------------------------------------║--------------║
║ Collections$SynchronizedRandomAccessList ║ 335.079316   ║
║------------------------------------------║--------------║
║ concurrent.CopyOnWriteArrayList          ║ 299.203427   ║
║------------------------------------------║--------------║
║ concurrent.CopyOnWriteArrayList          ║ 361.800762   ║
║------------------------------------------║--------------║
║ concurrent.CopyOnWriteArrayList          ║ 316.672923   ║
║------------------------------------------║--------------║
║ LinkedList                               ║ 776.843317   ║
║------------------------------------------║--------------║
║ LinkedList                               ║ 807.458514   ║
║------------------------------------------║--------------║
║ LinkedList                               ║ 793.940155   ║
║------------------------------------------║--------------║
║ Collections$SynchronizedList             ║ 793.125156   ║
║------------------------------------------║--------------║
║ Collections$SynchronizedList             ║ 782.003326   ║
║------------------------------------------║--------------║
║ Collections$SynchronizedList             ║ 790.937425   ║
║------------------------------------------║--------------║
║ Collections$SetFromMap                   ║ 1452.049046  ║
║------------------------------------------║--------------║
║ Collections$SetFromMap                   ║ 1457.275127  ║
║------------------------------------------║--------------║
║ Collections$SetFromMap                   ║ 1450.322531  ║
║------------------------------------------║--------------║
║ concurrent.ConcurrentLinkedQueue         ║ 976.803439   ║
║------------------------------------------║--------------║
║ concurrent.ConcurrentLinkedQueue         ║ 855.64423    ║
║------------------------------------------║--------------║
║ concurrent.ConcurrentLinkedQueue         ║ 845.05258    ║
║------------------------------------------║--------------║
║ concurrent.ConcurrentSkipListSet         ║ 926.423234   ║
║------------------------------------------║--------------║
║ concurrent.ConcurrentSkipListSet         ║ 924.370203   ║
║------------------------------------------║--------------║
║ concurrent.ConcurrentSkipListSet         ║ 933.504106   ║
╚══════════════════════════════════════════╩══════════════╝

欢迎评论。

高性能、无锁 Java 具有非常具体要求的集合

High performance, lock free Java collection with very specific requirements

java

collections

concurrency

performance

data-structures