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

[Kim Barrett]

> On Jul 5, 2018, at 2:44 PM, Zhengyu Gu <zgu at redhat.com> wrote:
> 
> Hi Kim,
> 
> On 07/05/2018 01:33 PM, Kim Barrett wrote:
>>> On Jul 5, 2018, at 3:54 AM, Thomas Schatzl <thomas.schatzl at oracle.com> 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:
>>>>> 
>>>>> […]
>>>>> 
>>>>> Bug: https://bugs.openjdk.java.net/browse/JDK-8205921
>>>>> Webrev: http://cr.openjdk.java.net/~zgu/8205921/webrev.00/index.htm
>>>>> l
>>>>> […]
>>>> Why do the last_queue array entries need to be padded? Why not just
>>>> add a _last_stolen_queue member to TaskQueueSuper?
>>> 
>>> The _last_stolen_queue is associated to a (stealing) thread, not the
>>> queue. Multiple threads might have the same queue as current steal
>>> target.
>> The stealing thread should use its own queue to obtain and record this
>> value, e.g.
>>   _queues[queue_num]->_last_stolen_queue
>> It seems to me the random seed could also be there, addressing your
>> other complaint (below).
> Is it a bit weird to have these two fields in queue? given they have nothing to do with queue itself?
> 
> I intended to use thread local for last_stolen_queue in Shenandoah, since we do have extra spaces in GCThreadLocalData.

I don't think it's weird.  Both the last steal queue and the random
seed are 1:1 associated with a specific queue, and are part of the
implementation of operations on the queue.  This is a common problem
when there is a cooperating pair of class X and class "collection of
X".  Maybe if steal_best_of_2 were a member function of the queue,
rather than implemented by the queue set operating on the data in a
selected queue, it might seem more apparent that this information
belongs with the queue.

>> That might have false sharing issues with the volatile members of the
>> queue, but the existing _elems member have similar issues.  Maybe the
>> volatile queue members ought to be padded?
> 
> I can see we might need to pad Age and bottom. But I don't understand why _elems member has similar issues, could you explain?

Unshared _elems may be in the same cache line as shared _age or
_bottom, so reads of the _elems member may be impacted by writes to
those shared members by other threads.  The same is true for any new
unshared members we might add.