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

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

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 >= n 和 i + n >= nextn。

i >= n 是否考虑了数据溢出？（-2147483648 - 1 = 2147483647）；

i + n >= nextn 和 i >= n 是一样的吗？（我认为不是）

  1. private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
  2.     int n = tab.length, stride;
  3.     //...
  4.     int nextn = nextTab.length;
  5.     ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
  6.     boolean advance = true;
  7.     boolean finishing = false; // 确保在提交 nextTab 之前进行扫描
  8.     for (int i = 0, bound = 0;;) {
  9.         Node<K,V> f; int fh;
  10.         while (advance) {
  11.             int nextIndex, nextBound;
  12.             if (--i >= bound || finishing)
  13.                 advance = false;
  14.             else if ((nextIndex = transferIndex) <= 0) {
  15.                 i = -1;
  16.                 advance = false;
  17.             }
  18.             else if (U.compareAndSwapInt
  19.                      (this, TRANSFERINDEX, nextIndex,
  20.                       nextBound = (nextIndex > stride ?
  21.                                    nextIndex - stride : 0))) {
  22.                 bound = nextBound;
  23.                 i = nextIndex - 1;
  24.                 advance = false;
  25.             }
  26.         }
  27.         if (i < 0 || i >= n || i + n >= nextn) {
  28.             int sc;
  29.             if (finishing) {
  30.                 nextTable = null;
  31.                 table = nextTab;
  32.                 sizeCtl = (n << 1) - (n >>> 1);
  33.                 return;
  34.             }
  35.             if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
  36.                 if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
  37.                     return;
  38.                 finishing = advance = true;
  39.                 i = n; // 在提交之前重新检查
  40.             }
  41.         }
  42.         //...
  43. }
英文:

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)

  1. private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
  2. int n = tab.length, stride;
  3. //...
  4. int nextn = nextTab.length;
  5. ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
  6. boolean advance = true;
  7. boolean finishing = false; // to ensure sweep before committing nextTab
  8. for (int i = 0, bound = 0;;) {
  9. Node<K,V> f; int fh;
  10. while (advance) {
  11. int nextIndex, nextBound;
  12. if (--i >= bound || finishing)
  13. advance = false;
  14. else if ((nextIndex = transferIndex) <= 0) {
  15. i = -1;
  16. advance = false;
  17. }
  18. else if (U.compareAndSwapInt
  19. (this, TRANSFERINDEX, nextIndex,
  20. nextBound = (nextIndex > stride ?
  21. nextIndex - stride : 0))) {
  22. bound = nextBound;
  23. i = nextIndex - 1;
  24. advance = false;
  25. }
  26. }
  27. if (i < 0 || i >= n || i + n >= nextn) {
  28. int sc;
  29. if (finishing) {
  30. nextTable = null;
  31. table = nextTab;
  32. sizeCtl = (n << 1) - (n >>> 1);
  33. return;
  34. }
  35. if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
  36. if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
  37. return;
  38. finishing = advance = true;
  39. i = n; // recheck before commit
  40. }
  41. }
  42. //...
  43. }

答案1

得分: 1

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

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

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

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

  1. while (advance) {
  2.   int nextIndex, nextBound;
  3.   if (--i >= bound || finishing)
  4.       advance = false;
  5.   else if ((nextIndex = transferIndex) <= 0) {
  6.       i = -1;
  7.       advance = false;
  8.   }
  9.   else if (U.compareAndSwapInt
  10.            (this, TRANSFERINDEX, nextIndex,
  11.             nextBound = (nextIndex > stride ?
  12.                          nextIndex - stride : 0))) {
  13.       bound = nextBound;
  14.       i = nextIndex - 1;
  15.       advance = false;
  16.   }
  17. }

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

  1. // 见方法 transfer
  2. if (finishing) {
  3.    nextTable = null;
  4.    table = nextTab;
  5.    sizeCtl = (n << 1) - (n >>> 1);
  6.    return;
  7. }

而所有的转移入口严格检查 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
  1. while (advance) {
  2. int nextIndex, nextBound;
  3. if (--i &gt;= bound || finishing)
  4. advance = false;
  5. else if ((nextIndex = transferIndex) &lt;= 0) { //here is the only chance to update nextIndex
  6. i = -1;
  7. advance = false;
  8. }
  9. else if (U.compareAndSwapInt
  10. (this, TRANSFERINDEX, nextIndex,
  11. nextBound = (nextIndex &gt; stride ?
  12. nextIndex - stride : 0))) {
  13. bound = nextBound;
  14. i = nextIndex - 1;
  15. advance = false;
  16. }
  17. }

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:

  1. //see the method transfer
  2. if (finishing) {
  3.    nextTable = null;
  4.    table = nextTab;
  5.    sizeCtl = (n &lt;&lt; 1) - (n &gt;&gt;&gt; 1);
  6.    return;
  7. }

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
  • java
  • java.util.concurrent
匿名

发表评论

匿名网友

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

确定