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() 中，我们“可能”计算了一些额外的计数。但大多数情况下可能是正确的值，有时还有一个额外的计数。但我只是想让它更精确。

这是诀窍：

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();
  }
}

我的问题是，我能做得更好吗？

Salt：我知道 (cast) 问题，并且可以避免多次调用 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+ 的讨论）。

一种优化思路是使用 AtomicLong 将 value 和 count 都存储在 Long 的不同位置，从而解决了在计算平均值时确保 count 和 value 匹配的问题。

另一个（更大的）优化是使用线程特定的度量（如前面所建议的那样）。它具有以下优点。

  • 它避免了写入时的任何类型的争用。因此，写入时的 CAS 会很快，因为没有其他线程正在写入相同的指标。
  • 读取不需要任何锁。
  • 最重要的是，它将更好地利用 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 个任务，循环，每个任务中有 10000 次更新，值为 0 到 9999。结果是：

(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

就正确性而言，我认为您的计划是一个非常狡猾的计划。您已经进行了设置，以便多个更新线程独立地增加计数和总数，因此可以安全地允许通过读锁。

您的平均计算是在写锁定下进行的，因此可以保证没有更新的“阅读器”可以处于活动状态，从而使计数和总数暂时失步。

对我来说最大的问题是你的方案是否真的比简单的同步行为提供更好的性能？尽管您已经通过避免代码中的同步部分消除了读者之间的表面争论点，但在幕后，阅读器/编写器代码可能会在同步块中做一些聪明的事情。请参阅读写锁文档。这还警告说，根据实现的细节，您的作者可能会遭受饥饿。

只有仔细测量才能告诉我们答案。

于 2012-10-23T02:52:44.277 回答