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

[Zhengyu Gu]

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.


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

Thanks,

-Zhengyu

> 
>> One other option I discussed is instead of this array of PaddedQueueId
>> (which I would rename as TaskQueueThreadLocal or
>> TaskQueueStealLocals/Context because I can see adding more in the
>> future) would be passing this around like the seed parameter to
>> steal_best_of_2 (and actually put the seed parameter in there too).
>>
>> It's a bit weird to me to pass two different kinds of thread locals
>> related to work stealing two different ways.
>>
>> The padding is to avoid potential false sharing issues as otherwise
>> last_stolen_id's of different threads end up on the same cache line.
>> And the writes of different threads to disjoint locations would likely
>> invalidate the cache line all the time. Just to avoid a potential
>> performance issue here.
>