同時に変更されたConcurrentSkipListSetからTreeSetを作成する例外

Question

一般的に、並行コレクションは反復するのが安全です。 Javadocによると、「イテレータは弱く一貫しており、イテレータの作成時以降のある時点でセットの状態を反映しています。彼らはConcurrentModificationExceptionを投げず、他の操作と並行して進めるかもしれません。 しかし、この検討してください：

import java.util.Random; 
import java.util.TreeSet; 
import java.util.concurrent.ConcurrentSkipListSet; 

public class ConcurrencyProblem { 
    private static volatile boolean modifierIsAlive = true; 

    public static void main(String[] args) { 
     final ConcurrentSkipListSet<Integer> concurrentSet = new ConcurrentSkipListSet<>(); 
     Thread modifier = new Thread() { 
      private final Random randomGenerator = new Random(); 

      public void run() { 

       while (modifierIsAlive) { 
        concurrentSet.add(randomGenerator.nextInt(1000)); 
        concurrentSet.remove(randomGenerator.nextInt(1000)); 
       } 
      }; 
     }; 
     modifier.start(); 
     int sum = 0; 
     while (modifierIsAlive) { 
      try { 
       TreeSet<Integer> sortedCopy = new TreeSet<>(concurrentSet); 
       // make sure the copy operation is not eliminated by the compiler 
       sum += sortedCopy.size(); 
      } catch (RuntimeException rte) { 
       modifierIsAlive = false; 
       rte.printStackTrace(); 
      } 
     } 
     System.out.println("Dummy output: " + sum); 
    } 
} 

出力は、これはバグや機能である場合、私は思ったんだけど

java.util.NoSuchElementException 
at java.util.concurrent.ConcurrentSkipListMap$Iter.advance(ConcurrentSkipListMap.java:2299) 
at java.util.concurrent.ConcurrentSkipListMap$KeyIterator.next(ConcurrentSkipListMap.java:2334) 
at java.util.TreeMap.buildFromSorted(TreeMap.java:2559) 
at java.util.TreeMap.buildFromSorted(TreeMap.java:2547) 
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579) 
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579) 
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579) 
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579) 
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579) 
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579) 
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579) 
at java.util.TreeMap.buildFromSorted(TreeMap.java:2504) 
at java.util.TreeMap.addAllForTreeSet(TreeMap.java:2462) 
at java.util.TreeSet.addAll(TreeSet.java:308) 
at java.util.TreeSet.<init>(TreeSet.java:172) 
at mtbug.ConcurrencyProblem.main(ConcurrencyProblem.java:27) 
Dummy output: 44910 

です。私たちはConcurrentModificationExceptionを取得しませんでしたが、反復処理（同期化されたブロックなどに戻って）を気にしなくても、ConcurrentSkipListSet/Mapの目的を無効にすることができます。私はこれをJava 7と8の両方で再現することができました（現在のところ、私のLinuxボックスの8u72です）。

Answer 1

TreeSetの問題は、ソースを参照して理解できる限り、反復処理を行う前にsize()を呼び出してから、hasNext()の代わりに使用します。これはバグかもしれませんが、赤黒の木が慎重なバランスを必要とする複雑な構造であることの結果だと思うので、作成中に線形時間に適切にバランスをとるためには事前にサイズを知る必要があります。

が手動で反復してTreeSetに要素を追加することによって、これを回避することがありますが、これはTreeSetのコンストラクタはそのように行っていない理由かもしれn log n複雑につながる（そのAPI仕様は、線形時間を保証します）。もちろん、ツリーを構築するときにはまだhasNext()と呼ぶことができますが、ツリーの再均衡をとるために構築が完了した後にいくつかの追加アクションが必要になることがあります。しかし、赤黒の木は、そのままでは混乱しています。この種のハックは、実装がより面倒なものになります。

まだ、私はそれが非常に混乱していると思うし、おそらくAPIドキュメントのどこかに文書化されるべきだと思いますが、正確にはどこにいるのかはわかりません。おそらく弱い一貫性のイテレータが何であるかを説明する部分であろう。具体的には、一部のライブラリクラスは返されるサイズに依存しているため、NoSuchElementExceptionをスローする可能性があります。特定のクラスを挙げることも助けになります。

Answer 2

私は実際にTreeSet/TreeMap（更新、it is）のバグであると考えています。 Sergeyが暗示しているように、この問題はTreeMapがその要素を読み取る前にConcurrentSkipListSet.size()の結果をキャッシュするという問題です。

• TreeSet.addAll()は
• TreeMap.addAllForTreeSet()を呼び出し、最終的にIterator.next()size回分を呼び出し
• TreeMap.buildFromSorted()にコレクションの現在のサイズと潜在的に同時Iteratorを渡します。

つまり、渡されたCollectionは、構築中に変更されないと仮定しています。これは誤った仮定です。

buildFromSorted()がIterator.hasNext()となった場合でも、バッキングデータ構造が途中で修正されているため、その時点で唯一のオプションが失敗することに注意してください。潜在ArrayList、LinkedList、およびCopyOnWriteArrayList（私は単にfor-each over the elementsを見て、他のほとんどのコレクション）を含む同時構造をコピーするいくつかの問題を持っている可能性が他のコレクションを見てみると

は、明示的に任意の実際の作業を行う前に、アレイに提供するコレクションをコピーしますこの正確な問題を避けるために私はTreeSetとTreeMapは同じことをする必要がありますと思う。

私は実際にこのバグのためにO（n log n）のパフォーマンスを受け入れる必要はありませんが、ハックになるでしょう。 TreeSetへの挿入は線形時間ではないので、配列やその他のデータ構造に値を単純にコピーすることはできません。しかし、コピーはSortedSetと主張してTreeSetに嘘をつくことができます。ごTreeSet作図線を変更する

public static class IterateOnlySortedSet<E> 
    extends AbstractSet<E> implements SortedSet<E> { 
    private final ArrayList<E> elements; 
    private final Comparator<? super E> comparator; 

    public IterateOnlySortedSet(SortedSet<E> source) { 
    elements = new ArrayList<>(source); 
    comparator = source.comparator(); 
    } 

    @Override 
    public Iterator<E> iterator() { 
    return elements.iterator(); 
    } 

    @Override 
    public int size() { 
    return elements.size(); 
    } 

    @Override 
    public Comparator<? super E> comparator() { 
    return comparator; 
    } 

    // remaining methods simply throw UnsupportedOperationException 
} 

：

TreeSet<Integer> sortedCopy = new TreeSet<>(new IterateOnlySortedSet<>(concurrentSet)); 

今成功しました。

ニースのfind :)のJavadocパー