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

[Kim Barrett]

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

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?

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