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

huangapple go评论82阅读模式
英文:

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

问题

在转移方法中,判断扩展终止的条件(或帮助传输线程完成)是 if (i < 0 || i >= n || i + n >= nextn) {。我知道 i < 0 这个条件表示所有的存储桶都已经分配,但我不理解另外两个条件的意思:i >= ni + n >= nextn

i >= n 是否考虑了数据溢出?(-2147483648 - 1 = 2147483647);

i + n >= nextni >= n 是一样的吗?(我认为不是)

private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
    int n = tab.length, stride;
    //...
    int nextn = nextTab.length;
    ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
    boolean advance = true;
    boolean finishing = false; // 确保在提交 nextTab 之前进行扫描
    for (int i = 0, bound = 0;;) {
        Node<K,V> f; int fh;
        while (advance) {
            int nextIndex, nextBound;
            if (--i >= bound || finishing)
                advance = false;
            else if ((nextIndex = transferIndex) <= 0) {
                i = -1;
                advance = false;
            }
            else if (U.compareAndSwapInt
                     (this, TRANSFERINDEX, nextIndex,
                      nextBound = (nextIndex > stride ?
                                   nextIndex - stride : 0))) {
                bound = nextBound;
                i = nextIndex - 1;
                advance = false;
            }
        }
        if (i < 0 || i >= n || i + n >= nextn) {
            int sc;
            if (finishing) {
                nextTable = null;
                table = nextTab;
                sizeCtl = (n << 1) - (n >>> 1);
                return;
            }
            if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
                if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
                    return;
                finishing = advance = true;
                i = n; // 在提交之前重新检查
            }
        }
        //...
}
英文:

In the transfer method,the condition for judging the termination of the expansion (or the helping transfer threads finish) is if (i < 0 || i >= n || i + n >= nextn) {. I know i < 0 this condition means that all bins have been allocated, but I don't understand the meaning of other two conditions: i >= n and i + n >= nextn

Is i >= n considering a data overflow?(-2147483648 - 1 = 2147483647);

Is i + n >= nextn the same as i >= n?(I don't think so)

private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
//...
int nextn = nextTab.length;
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
boolean advance = true;
boolean finishing = false; // to ensure sweep before committing nextTab
for (int i = 0, bound = 0;;) {
Node<K,V> f; int fh;
while (advance) {
int nextIndex, nextBound;
if (--i >= bound || finishing)
advance = false;
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) {
nextTable = null;
table = nextTab;
sizeCtl = (n << 1) - (n >>> 1);
return;
}
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
finishing = advance = true;
i = n; // recheck before commit
}
}
//...
}

答案1

得分: 1

逻辑上来说,这是一段无效的代码,我认为它可能在编码/调试期间用于边界检测。

从数学的角度来看,如果 i >= n,那么:

  1. 整数溢出:不可能,因为最大调整阈值是 1<<29,而 n 的最大值是 1<<29。
  2. i 变大于 n:不可能,因为 i = nextIndex-1,而 nextIndex = transferIndex,且 transferIndex = nextIndex-stride。

如果 i >= n,那么 transferIndex 需要被另一个线程更新为更大的值(加倍)。
这意味着在当前调整尚未完成时发生了新的调整!
这绝对不可能。

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

有人可能会质疑 volatile 变量的更新顺序,比如 nextTable/table/sizeCtl,也是不可能的。
因为在调整结束时,它们会被更新如下:

// 见方法 transfer
if (finishing) {
   nextTable = null;
   table = nextTab;
   sizeCtl = (n << 1) - (n >>> 1);
   return;
}

而所有的转移入口严格检查 table/nextTable/sizeCtl 和 transferIndex。
同样,无法泄漏部分更新到 transfer 中。

所以,我有 i + n >= nextn 的疑虑。

英文:

logically, it's a piece of dead code, i think it might be boundary dection during coding/deubging.

From the view of math, if i >= n, then

  1. int overflow: impossible. because max resizing threshold is 1<<29,the maximum value of n is 1<<29
  2. i become larger than n: impossible. beacuse i = nextIndex-1, while nextIndex = transferIndex, and transferIndex=nextIndex-stride
    <br/>
    if i>=n, then transferIndex need to be updated to larger value(doubled) by another thread.
    which means a new resizing happens while current resizing has not completed!
    <br/>
    it's definitely impossible
while (advance) {
int nextIndex, nextBound;
if (--i &gt;= bound || finishing)
advance = false;
else if ((nextIndex = transferIndex) &lt;= 0) { //here is the only chance to update nextIndex
i = -1;
advance = false;
}
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex &gt; stride ?
nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}

one might doubt the updated sequence of volatile variables, such as nextTable/table/sizeCtl, also impossible.
<br>
because at the end of resizing, they got updated as belows:

//see the method transfer
if (finishing) {
   nextTable = null;
   table = nextTab;
   sizeCtl = (n &lt;&lt; 1) - (n &gt;&gt;&gt; 1);
   return;
}

And all the entering of transfer strictly check table/nextTable/sizeCtl and transferIndex.
<br>
again, no way to leak partially updates to transfer.

and so i+n >= nextn

huangapple
  • 本文由 发表于 2020年8月26日 19:52:47
  • 转载请务必保留本文链接:https://go.coder-hub.com/63597067.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定