RFR(S) 8205921: Optimizing best-of-2 work stealing queue selection

[Zhengyu Gu]

On 07/05/2018 02:49 PM, Kim Barrett wrote:
>> On Jul 5, 2018, at 12:08 PM, Zhengyu Gu <zgu at redhat.com> wrote:
>>
>> Hi Kim and Thomas,
>>
>> Thanks for reviewing.
>>
>> On 07/05/2018 03:54 AM, Thomas Schatzl wrote:
>>> Hi,
>>> On Thu, 2018-07-05 at 01:15 -0400, Kim Barrett wrote:
>>>>> On Jun 27, 2018, at 2:39 PM, Zhengyu Gu <zgu at redhat.com> wrote:
>>>> […]
> 
>>>> An alternative that might be better is, whenever a pop_global fails,
>>>> reset the associated last_stolen id to invalid.  This will revert to
>>>> 2 random choices until we find (at least) one with something we can
>>>> steal. Actually, it seems the referenced paper does something
>>>> similar, and the webrev code doesn't match the referenced paper.
>>> That may explain why my perf results are different to the paper that I
>>> was planning to investigate :) Nice find.
>>
>> Sorry, my bad.
>>
>> […]
>> Updated webrev:
>>
>> http://cr.openjdk.java.net/~zgu/8205921/webrev.01/index.html
> 
> src/hotspot/share/gc/shared/taskqueue.inline.hpp
>   255     if (sz2 > sz1) {
>   256       sel_k = k2;
>   257       suc = _queues[k2]->pop_global(t);
>   258     } else {
>   259       sel_k = k1;
>   260       suc = _queues[k1]->pop_global(t);
>   261     }
> 
> The paper avoids the steal attempt when both potential victims have a
> size of zero, e.g. insert another clause:
> 
>    } else if (sz1 == 0) {
>      sel_k = k1;  // Might be needed to avoid uninitialized variable warnings?
>      suc = false;
>    } else {
>      ...
> 
> There is a race condition between obtaining the size and checking it
> here, but I don't think that's important.  The point is to avoid an
> expensive steal attempt when it is very likely to fail.

Yes, I missed this.

http://cr.openjdk.java.net/~zgu/8205921/webrev.02/index.html

Thanks,

-Zhengyu

>