why the last thread must sweep to check every slot again?

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

why the last thread must sweep to check every slot again?

JSR166 Concurrency mailing list
hello concurrency-interest:
     In jdk1.8, ConcurrentHashMap's transfer function is used to resize, but there is a place I don’t understand. see below.
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
}
}
   From the code above, the last thread to restore sizeCtl must recheck every slot again. But in my opinion, when the last thread to restore sizeCtl, every slot have been transfer to the new table already. So why why the last thread must sweep to check every slot again?


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: why the last thread must sweep to check every slot again?

JSR166 Concurrency mailing list
On 7/16/20 8:01 AM, Liu via Concurrency-interest wrote:
     In jdk1.8, ConcurrentHashMap's transfer function is used to resize, but there is a place I don’t understand. see below.
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
    }
}
   From the code above, the last thread to restore sizeCtl must recheck every slot again. But in my opinion, when the last thread to restore sizeCtl, every slot have been transfer to the new table already. So why why the last thread must sweep to check every slot again?

Yes, this is a valid point; thanks. The post-scan was needed in a previous version, and could be removed. It does not trigger often enough to matter though, so is for now another minor tweak that might be included next time CHM is updated.

-Doug



_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: why the last thread must sweep to check every slot again?

JSR166 Concurrency mailing list
Thanks for answer! But I think in every resize process, the last thread will trigger to check every slot again surely, not just possibly. Even when only one thread to invoke the transfer func, this thread also do the recheck in the end. Am I wrong?

-Liu

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: why the last thread must sweep to check every slot again?

JSR166 Concurrency mailing list
You are right that the post-scan is non-optional. As I mentioned,
rechecking that it is never needed and possibly removing is on the todo
list for next update. (Because it only impacts one step of resize, the
performance impact is relatively low.)

On 7/17/20 12:11 PM, Liu wrote:
> Thanks for answer! But I think in every resize process, the last
> thread will trigger to check every slot again surely, not just
> possibly. Even when only one thread to invoke the transfer func, this
> thread also do the recheck in the end. Am I wrong?
>
> -Liu
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest