英文:
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
是一样的吗?(我认为不是)
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<<29,而 n 的最大值是 1<<29。
- 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
- int overflow: impossible. because max resizing threshold is 1<<29,the maximum value of n is 1<<29
- 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 >= bound || finishing)
advance = false;
else if ((nextIndex = transferIndex) <= 0) { //here is the only chance to update nextIndex
i = -1;
advance = false;
}
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > 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 << 1) - (n >>> 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
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论