高性能，无锁的Java集合，具有非常特定的要求 [英] High performance, lock free Java collection with very specific requirements
问题描述
对于具有以下要求的高性能并发集合，什么样的候选人才是合适的？
What would be a suitable candidate for a high-performance concurrent collection with the following requirements:
- 集合中元素的数量很小（几个元素，通常少于10个），很少更改。
- 主要用例是遍历元素。这种情况经常发生，而且必须超级快（即应该是无锁的）。
- 有时，会使用迭代器remove（）方法删除一个元素。优选地，这也应该非常快地工作（但它的作用不如迭代器的next（）方法重要。）
- 元素的顺序无关紧要，因此元素插入的方式无关紧要
- 最好是标准Java库中的内容。
- The number of elements in the collection is small (a few elements, usually less than 10) and rarely changes.
- The main use case is iterating through the elements. This happens a lot and must be super fast (i.e. should be lock free).
- Occasionally an element will be removed by use of the iterator remove() method. This should preferably also work very fast (but it's less significant than the iterator next() method).
- The order of the elements is insignificant so it doesn't matter how elements are inserted to the collection.
- Preferably something from the standard Java library.
我考虑过使用ConcurrentLinkedQueue< >，但如果您从不调用poll（）方法，则会发现有提到它泄漏内存（通过设计）。我不确定情况是否仍然如此（提到此问题的帖子来自〜2011，我发现有些提及可能已解决）。
I considered using ConcurrentLinkedQueue<> for this, but found mentions of it leaking memory (by design) if you never call the poll() method. I'm not sure if this is still the case (the posts mentioning this are from ~ 2011 and I found some mentions that this may have been addressed).
我也考虑了ConcurrentSkipListSet<>，但是我不确定排序对性能有什么影响（因为我不在乎顺序）。
I also considered ConcurrentSkipListSet<>, but I'm not sure what is the effect of the sorting on the performance (since I don't care about the order).
推荐答案
如果您正在寻找足够快的解决方案，则可以使用ConcurrentLinkedQueue。在Itaer.remove（）中众所周知的内存泄漏问题已作为 http://bugs.java.com/view_bug.do?bug_id=6785442 。现在已删除的ConcurrentLinkedQueue $ Node应该已成功通过GC。但是，如果您正在寻找性能最高的解决方案，那么...
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...
-
根本不要使用迭代器（并且对于-因此，对Collection进行每个操作），因为Collection.iterator（）准备Iterator的新实例，顺便说一句，它的next（）方法不是免费的:)每次使用Iterator迭代一个collection时，都会花费CPU时间至少：大约10条指令为新对象分配内存+大量构造函数指令（请参见ConcurrentLinkedQueue $ Itr的源代码）+ ConcurrentLinkedQueue $ Itr.next（）+在次要GC上从Eden移除对象。
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.
普通数组+直接索引是最快的迭代技术。因此，请使用CopyOnWriteArrayList或实现您自己的集合以使用普通数组来迭代多个项目。例如，如果您很少添加/删除项目，并且希望在迭代时将其删除而不是按索引删除，则可以尝试以下操作：
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--;
}
}
}
用法：
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 足以保证所有对象的可见性在作者和所有读者之间进行更改。另外，如果延迟对您很重要，您可以用忙碌的等待来替换经典锁，以获取无锁集合。
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
这篇关于高性能，无锁的Java集合，具有非常特定的要求的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
