5

巨大なTroveマップと、複数のスレッドから頻繁に呼び出す必要のあるメソッドがあります。ほとんどの場合、このメソッドはtrueを返します。スレッドは大量の処理を行っており、次の方法が原因で競合が発生していることに気付きました（これは単なる例であり、実際のコードは少し異なります）。

synchronized boolean containsSpecial() {
   return troveMap.contains(key);
}

これは「追加のみ」のマップであることに注意してください。キーが追加されると、そこに永久に残ります（これは次に来るものにとって重要だと思います）。

上記を次のように変更することで気づきました。

boolean containsSpecial() {
    if ( troveMap.contains(key) ) {
        // most of the time (>90%) we shall pass here, dodging lock-acquisition
        return true;
    }
    synchronized (this) {
        return troveMap.contains(key);
    }
}

数の計算が20％高速化されます（多くの実行、長時間の実行などで確認されています）。

この最適化は正しいように見えますか（キーが存在すると、それは永久にそこにとどまるということを知っています）？

このテクニックの名前は何ですか？

編集

マップを更新するコードは、 containsSpecial（）メソッドよりも呼び出される頻度が低く、次のようになります（メソッド全体を同期しました）。

synchronized void addSpecialKeyValue( key, value ) {
    ....
}
4

6 に答える 6

7

このコードは正しくありません。

Troveは同時使用自体を処理しません。java.util.HashMapその点でそうです。したがって、のようHashMapに、一見無害に見える場合でも、のような読み取り専用メソッドcontainsKey()は、ランタイム例外をスローしたり、さらに悪いことに、別のスレッドがマップを同時に変更した場合に無限ループに入る可能性があります。Troveの内部はわかりませんが、を使用するとHashMap、負荷率を超えたときに再ハッシュしたり、エントリを削除したりすると、読み取りのみを行っている他のスレッドで障害が発生する可能性があります。

ロック管理と比較して操作にかなりの時間がかかる場合は、読み取り/書き込みロックを使用してシリアル化のボトルネックを解消すると、パフォーマンスが大幅に向上します。のクラスドキュメントにはReentrantReadWriteLock、「サンプルの使用法」があります。RWDictionaryの2番目の例をガイドとして使用できます。

この場合、マップ操作が非常に高速であるため、ロックのオーバーヘッドが支配的である可能性があります。その場合は、ターゲットシステムでプロファイルを作成して、synchronizedブロックまたは読み取り/書き込みロックのどちらが高速かを確認する必要があります。

いずれにせよ、重要な点は、すべての同期を安全に削除できないことです。そうしないと、一貫性と可視性の問題が発生します。

于 2011-12-07T18:23:50.737 に答える
6

それは間違ったロックと呼ばれます;-)実際には、それはダブルチェックされたロックアプローチのいくつかの変形です。そして、そのアプローチの元のバージョンは、Javaではまったく間違っています。

Javaスレッドは、変数のプライベートコピーをローカルメモリに保持できます（マルチコアマシンのコアローカルキャッシュを考えてみてください）。Java実装では、同期が行われない限り、変更をグローバルメモリに書き戻すことはできません。

したがって、スレッドの1つににtroveMap.contains(key)評価されるローカルメモリがある可能性が非常に高くなりますtrue。したがって、同期したり、更新されたメモリを取得したりすることはありません。

さらに、contains()troveMapデータ構造のメモリに一貫性がない場合はどうなりますか？

詳細については、Javaメモリモデルを検索してください。または、この本をご覧ください：JavaConcurrencyinPractice。

于 2011-12-07T18:02:21.480 に答える
2

これは私には危険に見えます。具体的には、同期されていない呼び出しは、メモリの可視性（JMMに必要なことを伝えていないため、以前のプットが完全に公開されていない）または単純な古いレースのいずれかにより、部分的な更新を確認できます。TroveMap.containsの過程で変更されないと想定する内部変数がある場合を想像してみてくださいcontains。このコードは、その不変条件を壊します。

メモリの可視性に関しては、それに関する問題はフォールスネガティブではありませんが（同期されたダブルチェックを使用します）、そのトローブの不変条件に違反する可能性があります。たとえば、カウンターがあり、counter == someInternalArray.length常にカウンターが必要な場合、同期の欠如がそれに違反している可能性があります。

私の最初の考えは、troveMapの参照を作成volatileし、マップに追加するたびに参照を書き直すことでした。

synchronized (this) {
    troveMap.put(key, value);
    troveMap = troveMap;
}

このように、メモリバリアを設定して、を読んだ人は誰でもtroveMap、最新の割り当て、つまり最新の状態の前に発生したすべてのことを確認できるようにします。これはメモリの問題を解決しますが、競合状態は解決しません。

データの変化の速さにもよりますが、ブルームフィルターが役立つかもしれません。または、特定の高速パス用にさらに最適化された他の構造ですか？

于 2011-12-07T18:34:24.360 に答える
1

明示的なロックを必要とせず、同時読み取りを可能にするConcurrentHashMapを使用した方がよいと思います。

boolean containsSpecial() {
    return troveMap.contains(key);
}

void addSpecialKeyValue( key, value ) {
    troveMap.putIfAbsent(key,value);
}

別のオプションは、同時読み取りを許可するが同時書き込みを許可しないReadWriteLockを使用することです。

ReadWriteLock rwlock = new ReentrantReadWriteLock();
boolean containsSpecial() {
    rwlock.readLock().lock();
    try{
        return troveMap.contains(key);
    }finally{
        rwlock.readLock().release();
    }
}

void addSpecialKeyValue( key, value ) {
    rwlock.writeLock().lock();
    try{
        //...
        troveMap.put(key,value);
    }finally{
        rwlock.writeLock().release();
    }
}
于 2011-12-07T18:09:05.873 に答える
1

あなたが説明する条件下では、同期に失敗することでフォールスネガティブを取得できるマップの実装を想像するのは簡単です。誤検知を取得することを想像できる唯一の方法は、キーの挿入が非アトミックであり、部分的なキーの挿入がテスト対象の別のキーのように見える実装です。

実装したマップの種類はわかりませんが、ストックマップの実装では、参照を割り当てることでキーを保存します。J ava言語仕様によると：

参照への書き込みと参照の読み取りは、32ビット値と64ビット値のどちらとして実装されているかに関係なく、常にアトミックです。

マップの実装でオブジェクト参照をキーとして使用している場合、どのように問題が発生するかわかりません。

編集

上記はTrove自体を知らずに書かれたものです。少し調べてみたところ、 Troveマップが同時かどうかについてRob Eden（Troveの開発者の1人）による次の投稿が見つかりました。

Troveは、取得時に内部構造を変更しません。ただし、これは実装の詳細であり、保証ではないため、将来のバージョンで変更されないとは言えません。

したがって、このアプローチは今のところ機能するようですが、将来のバージョンではまったく安全ではない可能性があります。ペナルティにもかかわらず、Troveの同期マップクラスの1つを使用するのが最善かもしれません。

于 2011-12-07T18:19:53.613 に答える
0

なぜ車輪の再発明をするのですか？ConcurrentHashMap.putIfAbsentを使用するだけです

于 2011-12-07T18:07:54.997 に答える