ConcurrentHashMap - 我们可以从 Transfer() 中删除 i >= n 吗？

Question

相关： ConcurrentHashMap的传递方法中，我不明白“i >= n”和“i + n >= nextn”这两个条件的含义

我正在研究j.u.c.ConcurrentHashMap中的transfer()方法。

去掉 i >= n || 没有意义吗？ i + n >= nextn 来自 transfer() 方法？

  for (int i = 0, bound = 0;;) {
        Node<K,V> f; int fh;
        while (advance) {
            int nextIndex, nextBound;
            if (--i >= bound || finishing) // always decreasing
                advance = false;
            else if ((nextIndex = transferIndex) <= 0) {
                i = -1; // obviously less than n
                advance = false;
            }
            else if (U.compareAndSetInt
                     (this, TRANSFERINDEX, nextIndex,
                      nextBound = (nextIndex > stride ?
                                   nextIndex - stride : 0))) {
                bound = nextBound;
                i = nextIndex - 1; // will be guaranteed to be less than n
                advance = false;
            }
        }
        if (i < 0 || i >= n || i + n >= nextn) { // why keep any thing other than i < 0

鉴于

i

是一个局部变量，我认为没有任何数学方法可以超过

n

（旧表长度）。

此外，上面链接的问题也说它是死代码。

我是否遗漏了一些关于 JMM 的信息，需要检查这个奇怪的情况？

Answer 1

但是可以：

while (advance) {
 int nextIndex, nextBound;
 if (--i >= bound || finishing)
   advance = false;
 else if ((nextIndex = transferIndex) <= 0) { // !!!! LINE 1
   i = -1;
   advance = false;
 }
 else if (U.compareAndSetInt
          (this, TRANSFERINDEX, nextIndex,
           nextBound = (nextIndex > stride ?
                        nextIndex - stride : 0))) {
    bound = nextBound;
    i = nextIndex - 1;
    advance = false;
  }
}

if (i < 0 || i >= n || i + n >= nextn) {

这段代码非常不惯用；它的编写风格在较旧的内核/低级 C 代码风格中有些常见，而根本不是 Java 风格。难怪;这个东西是低级东西的领域。

我直接从 CHM 源复制/粘贴的代码片段中标记的第 1 行（除了该注释）看起来像一个支票 但不是。它将

nextIndex

设置为transferIndex，然后检查该值是否低于或等于0，在这种情况下它进入

else if

的块。

因此，这是实现

i >= n

触发的流程：

• 此代码循环一次或几次。

• 到了

  if

  检查。

  transferIndex

  是一个字段。另一个线程可以更改它（鉴于我们正在讨论 CHM，显然编写代码是为了考虑可能发生的情况）。

• 因此，

  nextIndex

  现在相当高。高于

  n

  。这是因为另一个线程在此

  transfer()

  操作过程中一直在增长此地图。

• 尽管如此，当

  nextIndex

  已更新为

  nextTransfer

  的值时，if 失败。下一个 elseif（一个 CAS（比较和设置，一种 CPU 原语，对于编写在并发情况下正确运行的无锁代码非常有用）操作，以确保在我们刚刚花费的几个周期内完成这些循环，

   transferIndex

  是 still 我们在一两个周期前读取的值），我们现在已经“认领”了这项工作并将

  i

  设置为

  nextIndex - 1

  ，这可能高于

  n

  ！.

• 然后我们进行

  i >= n

  检查您所询问的问题，因此它可能确实是真的。我认为发生这种情况的情况是，如果在传输过程中，某个其他线程已将一些数据添加到 CHM，但这些数据已经添加到传输后的预期表中，因此无需执行操作，因此，开始“完成”工作，这需要另一次 CAS 检查和一次循环，且 finishing = true 打开。

NB：您可能会想：等等，

transferIndex

正在被读取，但是这里绝对没有在transferIndex 上建立 Happens-Before，所以无论它读取什么，根据定义，它都是 JMM 违规，并且可能（并且实际上很可能）在现代 CPU 上）不受其他线程写入的影响。但没那么快：在实际使用可能过时的 TransferIndex 值之前，代码会对

TRANSFERINDEX

进行 CAS 检查（它位于我刚刚粘贴的代码片段中，在最后的

else if

中），并且 CAS 检查还建立 HB。它没有记录在案，因为

Unsafe

或多或少不是规范的正式一部分。 （这有点像 JVM 规范的一部分，又有点不是，有点奇怪）。对于过时的读取，循环或多或少只是重新循环。作为一般规则，要在面对可能的并发操作时真正快速，您需要无锁。为了实现无锁，你需要大量的 CAS，并且通常以“重试”的方式使用 CAS：检查当前状态，对当前状态进行操作，然后使用 CAS 来确认之前检查的状态仍然是状态，如果是，则更新并继续。如果没有，就……再做一次。一遍又一遍，直到你“赢”（“赢”= CAS 调用成功，因为你正在 CAS 的东西确实具有预期值，预期=你开始计算时的东西）。最终你“赢了”。因此，最好将此类代码视为循环了几次、完全没有执行任何操作，因为 CAS 调用失败了。

数据库的工作方式相同：如果您熟悉 MVCC 风格的数据库以及如何使用它们执行无锁操作，同时保证最高的并发性保证（即

TransactionIsolationLevel.SERIALIBLE

，“最严格”级别） - 相同工作中的原则。冲突重试 - 同样的事情也发生在这里。