ConcurrentHashMap - Can we get rid of i >= n from transfer()?

Question

Related to : In ConcurrentHashMap's transfer method, I don't understand the meaning of these two conditions "i >= n" and "i + n >= nextn"

I am looking into the transfer() method in j.u.c.ConcurrentHashMap.

Doesn't it make sense to just get rid of i >= n || i + n >= nextn from the transfer() method ?

  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

Given that i is a local variable I see no mathematical way it can exceed n (old table len).

Also, the question linked above also says that its dead code.

Am I missing something about the JMM that needs to check this weird condition?

Answer 1

It can, though:

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) {

This code is highly non-idiomatic; it is written in a style somewhat common in older kernel/low-level C code style and not at all in java style. No wonder; this stuff is the domain of low-level stuff.

Line 1 as marked in the snippet I copy/pasted directly from the source of CHM (other than that remark) looks like a check but it is not. It sets nextIndex to transferIndex, and then checks if that value is below or equal to 0 in which case it enters the else if's block.

So, here's the flow to get to i >= n triggering:

• This code loops once or a few times.

• It gets to that if check. transferIndex is a field. Another thread can change it (and given that we're talking about CHM, the code is obviously written to take into account that may have occurred).

• Because of this, nextIndex is now quite high. Higher than n. That's because another thread has been growing this map in the middle of this transfer() operation.

• Nevertheless, whilst nextIndex has been updated to the value of nextTransfer, the if fails. The next elseif (a CAS (Compare-and-set, a CPU primitive that is incredibly useful to write lock-free code that operates correctly in concurrent situations) op to ensure that in the few cycles we just spent going through these hoops, transferIndex is still the value we read a cycle or two ago), we have now 'claimed' the job and set i to nextIndex - 1 which could be higher than n!.

• Then we get to the i >= n check you are asking about, and it could therefore indeed be true. I think the situation where that occurs is if, halfway through a transfer, some other thread has added some data to the CHM, but that's already been added to the post-transfer intended table so there is no need to act, thus, start the 'finishing' job which requires another CAS check and one more loop with finishing = true on.

NB: You may be thinking: Wait, transferIndex is being read but there is absolutely nothing establishing Happens-Before on transferIndex here, so whatever it reads, it's by definition a JMM violation and could be (and is in fact likely to be on modern CPUs) unaffected by other thread writes. But not so fast: Before a likely stale value of transferIndex is actually used, the code does a CAS check on TRANSFERINDEX (it's in the snippet I just pasted, in the final else if) and CAS checks also establish HB. It's not documented, because Unsafe isn't officially part of the spec, more or less. (It's sort of part of JVM spec and sort of not, bit of an oddball). For stale reads on this, the loop more or less just reloops.

As a general rule, to be truly fast in the face of likely concurrent operations, you want to be lock-free. To be lock-free, you need lots of CAS, and you use the CAS generally in a 'retry' style: You check current state, you act on current state, you then use CAS to confirm that the state you checked before is still the state, and if so, update and move on. If not, just.. do it again. Over and over until you 'win' ('win' = the CAS call succeeds because the thing you are CASing does have the expected value, expected = the thing it was when you started the calculation). Eventually you 'win'. Hence, it's best to read such code as having looped a few times, having done absolutely nothing, because CAS calls failed.

DBs work the same way: If you're familiar with MVCC style dbs and how you can use them to do lock-free ops with nevertheless the very highest concurrency guarantees (namely, TransactionIsolationLevel.SERIALIBLE, the 'toughest' level) - same principle at work. Retry-on-conflict - same thing happening here.