2

通常、読み取り中は読み取りロックでReadWriteLocksを使用し、書き込み中は書き込みロックを使用します。しかし、私が逆に使用すると思った派手なケースが役立つことがあります。しかし、うまくいけば、皆さんは私にもっと良い方法を教えてくれるでしょう。

これが私が欲しいものです。書き込みは多くなりますが、読み取りの量はわずかに少なくなります。たとえば、リクエストのレイテンシの平均計算機が例です。

ほとんど疑似コードとして扱います。

metric.addValue(latency); // Called a lot.

metric.getAverage(); // Called sparingly.

次のことができます。

addValue(value) {
  atomicCount.increment();
  atomicSum.increment(value);
}

getAverage() {
  return atomicCount.get() != 0 ? atomicSum.get() / atomicCount.get() : 0.0;
}

問題はgetAverage（）にあり、いくつかの余分なカウントを「カウントする可能性があります」。しかし、ほとんどの場合、おそらく正しい値であり、場合によっては1つの余分なカウントがあります。しかし、私はそれをもっと正確にしたいと思っています。

トリックは次のとおりです。

ReadWriteLock rw = /* write preference, or a fair lock. */;
Lock read = rw.readLock();
Lock write = rw.writeLock();

addValue(value) {
  read.lock(); // Using read lock when mutating. 
  try { 
    atomicCount.increment();
    atomicSum.increment(value);
  } finally {
    read.unlock();
  }
}

getAverage() {
  write.lock(); // Using write lock when reading.
  try {
    return atomicCount.get() != 0 ? atomicSum.get() / atomicCount.get() : 0.0;
  } finally {
    write.unlock();
  }
}

私の質問は、私はもっとうまくやれるでしょうか？

ソルト:(キャスト）の問題については知っています。count.get（）を複数回呼び出すなど、パフォーマンスを向上させるために回避できますが、コードをあまり乱雑にしたくありませんでした。

4

5 に答える 5

3

アトミック インクリメントを同時に実行しても意味がありません。いずれにせよ、それらは同時に存在することはできません。

最も単純な解決策 - 単純なロック、通常のカウント/合計変数 - は、はるかに優れたパフォーマンスを発揮します

lock
    count++;
    sum += value;
unlock

より並列化するには、「シャーディング」が必要です。各スレッドは独自の統計を維持します。読者はそれらすべてに全体像を問いかけます。(スレッドごとの統計は揮発性である必要があります。リーダーは Michael Burr のメソッドを使用して、スレッドごとの統計の安定したバージョンを取得します)

于 2012-10-23T04:06:48.857 に答える
2

次のような手法のパフォーマンスが向上するかどうかを確認することをお勧めします。基本的に、最初の値を追跡する別のカウンターを追加することで、カウントと合計が「安定」していることを保証しますが、他のすべての値の更新が完了した後にのみ更新されるため、ロックは含まれません。

addValue(value) {

  while (atomicFlag.get() != 0) {
      // spin
  }
  atomicCount.increment();
  atomicSum.increment(value);
  atomicCount2.increment();
}

getAverage() {
    int count;
    int sum;
    int count2;

    atomicFlag.increment();
    do {
        count = atomicCount.get();
        sum = atomicSum.get();
        count2 = atomicCount2.get();
    } while (count != count2);
    atomicFlag.decrement();

    return count != 0 ? (sum * 1.0) / count : 0.0;
}
于 2012-10-23T03:58:25.910 に答える
2

（ここに G+ からのディスカッションをコピーします）。

最適化のアイデアの 1 つは、値とカウントの両方を Long の別の場所に格納するために AtomicLong を使用することです。これにより、平均を計算する際にカウントと値が一致することを確認する問題を解決します。

もう 1 つの (より大きな) 最適化は、スレッド固有のメトリックを使用することです (評判の悪い人が以前に提案したように)。以下の利点があります。

  • 書き込み中のあらゆる種類の競合を回避します。したがって、他のスレッドが同じメトリックに書き込みを行っていないため、CAS on write は高速になります。
  • 読み取りにはロックは必要ありません。
  • そして最も重要なことは、L1 キャッシュをより有効に活用できることです。

最後のポイントの説明:

マルチコア CPU で、単一の共有メモリから多数の書き込みと読み取りを行う複数のスレッドがある場合、異なるコアで実行されているスレッドは、他のコアの L1 キャッシュを無効にし続けます。このため、最新の値は、キャッシュ整合性プロトコルを使用して他のコアから取得する必要があります。これらすべてが物事を大幅に遅くします。スレッド固有のメトリックを持つことで、この問題を回避できます。

参照: http://www.cs.washington.edu/education/courses/cse378/07au/lectures/L25-Atomic-Operations.pdf

それを念頭に置いて、このようなコードはうまく機能します。

private final AtomicLongMap<Long> metric = AtomicLongMap.create();

public void addValue(long value) {
    long threadId = Thread.currentThread().getId();
    metric.addAndGet(threadId, (value << 32) + 1);
}

public synchronized double getAverage() {
    long value = metric.sum();
    int count = (int)value;
    return (count == 0) ? 0 : ((double)(value >> 32))/count;
}

実際、テストでは、上記のロックなしのソリューションよりも優れたパフォーマンスを発揮することが示されています。そして桁違いに。

No thread safety: 3435ms, Average: 1.3532233016178474
(irreputable) Just synchronized {}  4665ms, Average: 4.0
(atuls) reverse read-write lock:    19703ms, Average: 4.0
(michael burr)  17150ms, Average: 4.0
(therealsachin) 1106ms, Average: 4.0
于 2012-10-25T17:53:41.423 に答える
1

私自身のソリューションを含め、各ソリューションのベンチマークを実行しました。

100 個のスレッドからの addValue のみ、それぞれ 100 個のタスクでループし、ループし、各タスクで値 0 から 9999 の 10000 回の更新を行います。結果は次のとおりです。

(irreputable) Just synchronized {}: 7756 ms  Average: 4999.5
(atuls) My reverse read-write lock: 16523 ms Average: 4999.5
(michael burr) Double counter trick: 10698 Average: 4999.5
No thread safety: 4115 ms Average: 4685.0
(atuls) Not thread safe v1. 11189 ms Average: 4999.5

評判が悪いのは正しいようです:)

于 2012-10-23T11:04:32.867 に答える
1

正確さという点では、あなたの計画はかなり狡猾だと思います。複数の更新スレッドがカウントと合計を個別にインクリメントし、読み取りロックを安全に通過できるように設定しました。

平均計算は書き込みロックの下で行われるため、更新中の「リーダー」がアクティブにならず、カウントと合計が一時的にずれることが保証されます。

私にとって大きな問題は、あなたのスキームが本当に単純な同期動作よりも優れたパフォーマンスを提供するかどうかです。コード内の同期セクションを回避することで、リーダー間の表面的な競合点を取り除きましたが、カバーの下では、リーダー/ライター コードが同期ブロックで巧妙なことを行っている可能性があります。ReadWrite Lock のドキュメントを参照してください。また、実装の詳細によっては、ライターが飢餓に苦しむ可能性があることも警告しています。

その答えは、注意深く測定することによってのみわかります。

于 2012-10-23T02:52:44.277 に答える