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，有“示例用法”；您可以使用第二个示例 for 来RWDictionary作为指导。

在这种情况下，映射操作可能非常快，以至于锁定开销占主导地位。如果是这种情况，您需要在目标系统上进行分析以查看synchronized块或读写锁是否更快。

无论哪种方式，重要的一点是您不能安全地删除所有同步，否则您将遇到一致性和可见性问题。

于 2011-12-07T18:23:50.737 回答
6

它被称为错误锁定；-) 实际上，它是双重检查锁定方法的一些变体。这种方法的原始版本在 Java 中是完全错误的。

Java 线程被允许在其本地内存中保留变量的私有副本（想想：多核机器的核心本地缓存）。除非发生某些同步，否则任何 Java 实现都不允许将更改写回全局内存。

因此，您的一个线程很可能有一个本地内存，其中troveMap.contains(key)评估为true. 因此，它永远不会同步，也永远不会获得更新的内存。

此外，当contains()看到 troveMap 数据结构的内存不一致时会发生什么？

查找 Java 内存模型以获取详细信息。或者看看这本书：Java Concurrency in Practice。

于 2011-12-07T18:02:21.480 回答
2

这对我来说看起来不安全。具体来说，非同步调用将能够看到部分更新，这可能是由于内存可见性（先前的 put 没有完全发布，因为您没有告诉 JMM 它需要如此）或由于普通的旧比赛。想象一下，如果TroveMap.contains有一些内部变量假设在contains. 这段代码让这个不变量中断。

关于内存可见性，问题不是误报（您使用同步的双重检查），但可能违反了 trove 的不变量。例如，如果他们有一个计数器，并且他们一直要求它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

在您描述的条件下，很容易想象一个地图实现，您可能会因为同步失败而得到假阴性。我可以想象获得误报的唯一方法是密钥插入是非原子的并且部分密钥插入恰好看起来像您正在测试的另一个密钥的实现。

你没有说你实现了什么样的地图，但股票地图实现通过分配引用来存储键。根据Java 语言规范：

对引用的写入和读取始终是原子的，无论它们是作为 32 位还是 64 位值实现的。

如果您的地图实现使用对象引用作为键，那么我看不出您会遇到什么麻烦。

编辑

以上是在对 Trove 本身一无所知的情况下编写的。经过一番研究，我发现了Rob Eden（Trove 的开发者之一）关于 Trove 地图是否并发的以下帖子：

Trove 不会修改检索的内部结构。然而，这是一个实现细节而不是保证，所以我不能说它在未来的版本中不会改变。

所以看起来这种方法现在可以工作，但在未来的版本中可能根本不安全。尽管会受到惩罚，但最好使用 Trove 的同步地图类之一。

于 2011-12-07T18:19:53.613 回答
0

为什么要重新发明轮子？只需使用ConcurrentHashMap.putIfAbsent

于 2011-12-07T18:07:54.997 回答