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

[Kim Barrett]

> 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.