非重複並行ArrayListのパフォーマンスを向上

Question

データ構造（重複しない）並行ArrayList（またはConcurrentLinkedQueue）のデータ構造を実装すると、パフォーマンスの問題が発生しました。

public class NonDuplicateList implements Outputable { 
    private Map<Term, Integer> map; 
    private List<Term> terms; 

    public NonDuplicateList() { 
     this.map = new HashMap<>(); 
     this.terms = new ArrayList<>(); 
    } 

    public synchronized int addTerm(Term term) { //bad performance :(
     Integer index = map.get(term); 
     if (index == null) { 
      index = terms.size(); 
      terms.add(term); 
      map.put(term, index); 
     } 
     return index; 
    } 

    @Override 
    public void output(DataOutputStream out) throws IOException { 
     out.writeInt(terms.size()); 
     for (Term term : terms) { 
      term.output(out); 
     } 
    } 
} 

TermとNonDuplicateListが両方の出力へOutputableインタフェースを実装することに留意されたいです。

NonDuplicateListスレッドセーフに保つために、私はこの方法addTerm(Term)を守るため​​を使用すると、パフォーマンスは現在addTermを呼び出すときに、予想ほど悪くなります。

データ整合性が強くないため、ConcurrentHashMapはこのケースには適していないようです。スレッド安全性を失うことなくaddTermのパフォーマンスをどのように改善するか考えてみませんか？

EDIT：NonDuplicateListて

output方法、すなわち反復、一つだけのスレッドが同時にaddTermを起動した後に、このメソッドにアクセスするので、スレッドセーフではないかもしれませんが、addTermとすぐ用語として、直ちにインデックス値を返す必要がありますNonDuplicateListに追加されます。

Answer 1

戻りタイプをaddTerm犠牲にすることができる場合は、実装にConcurrentHashMapを再利用する可能性があります。実際のインデックスを返す代わりに、追加が成功したか重複したかを示すbooleanを返すことができます。これにより、メソッドの同期を取り除き、パフォーマンスを向上させることもできます：

private ConcurrentMap<Term, Boolean> map; 
private List<Term> terms; 

public boolean addTerm(Term term) { 
    Boolean previousValue = map.putIfAbsent(term, Boolean.TRUE); 
    if (previousValue == null) { 
     terms.add(term); 
     return true; 
    } 
    return false; 
} 

Answer 2

私は恐ろしいほど早い解決策を得ることはないでしょうか？要点は、必要がないときに同期を避けることです。弱い整合性を気にしない場合は、イテレータを作成するときに他のスレッドがアイテムを追加しないようにするか、イテレータを作成するときに一貫性のあるスナップショットをとるよりも、イテレータを大幅に安くすることができます。

一方、同期と一貫性のあるイテレータが必要な場合は、ConcurrentHashMapの代替手段が必要です。私の頭に浮かぶのはjava.util.Collections#synchronizedMapですが、オブジェクトレベルで同期を使用しているため、すべての読み取り/書き込み操作でロックを取得する必要があります。これはパフォーマンスのオーバーヘッドです。

ConcurrentSkipListMapをご覧ください。これは、さまざまな操作で平均O(log(n))の性能を保証します。 ConcurrentHashMapにはない多くの操作もあります：ceilingEntry/Key、floorEntry/Keyなどです。並行ハッシュマップを使用していた場合は、ソート順が維持されます。おそらく、list + mapを取り除き、代わりにConcurrentSkipListMapを使用することは可能でしょう。要素のインデックスは、ConcurrentSkipListMap apiを使用して計算されます。