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

[Zhengyu Gu]

On 07/05/2018 03:26 PM, Kim Barrett wrote:
>> 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.

Ah, I thought _elems is from additional allocation, it is not a concern, 
but I guess there is still a chance.

Thanks,

-Zhengyu


>