Remove prefetch during mark

[Per Liden]

Hi Hugh,

On 03/01/2018 10:38 PM, Wilkinson, Hugh wrote:
> The construct that we are pursuing is outlined by the pseudocode in my next posting.  It is based upon earlier work done for network packet processing.
> 
> Intermediate FIFOs are used to prefetch ahead by 1 to N entries.  The size of the FIFOs would correspond to memory latencies and can be configured at runtime.
> The cost of this construct is the store and restore context operations.
> 
> The pseudocode implements a 3 stage pipeline:
> 1.	 Get an entry, prefetch the ZLiveMap and ZBitMap.

Wouldn't it not be a good idea to split the above stage in two? I'm 
thinking you can't prefetch the ZBitMap without first completing a load 
in the ZLiveMap (ZPage). So basically:

1. Get entry, prefetch ZLiveMap (ZPage)
2. Prefetch ZBitMap
3 ...

Also, have you considered having a stage for prefetching the page table? 
Maybe that's already hot enough and wouldn't help, but something like:

1. Get entry, prefetch ZPage address in ZPageTable
2. Prefetch ZLiveMap (ZPage)
3. Prefetch ZBitMap
4 ...

> 2.	Update the ZLiveMap and ZBitMap and if not already marked, prefetch the object.
> 3.	Update the live bytes and follow the object.
> 
> We find that prefetching the object for already marked objects degrades performance.
> 
> The looping constructs allow filling the FIFOs incrementally, allowing for up to 2 stores for every restore while the FIFOs are filling.
> 
> When the FIFOs are full, each stage of the pipeline executes once each in sequence.
> 
> The use of “do {…;if () continue;…; break; } while(UNLIKELY(true));” eliminates loop overhead and optimizes the code for single iteration execution.

Maybe it's way to early to tell, but I'm of course curious if you've got 
some early indication of what level of improvement (in terms of overall 
mark time reduction) this scheme can offer on some known benchmark?

cheers,
Per

> 
> Hugh
> 
> -----Original Message-----
> From: zgc-dev [mailto:zgc-dev-bounces at openjdk.java.net] On Behalf Of Steve Blackburn
> Sent: Thursday, March 1, 2018 6:24 AM
> To: Per Liden <per.liden at oracle.com>; zgc-dev at openjdk.java.net
> Subject: Re: Remove prefetch during mark
> 
> A surprising amount of blood, sweat and tears went into that work before we saw the nice result --- we could not get any performance out of the previously published prefetching work.
> 
> On the face of it, you're really well positioned to get some value given that you're already enqueuing edges.
> 
> I'll be interested to hear how things go.
> 
> Cheers,
> 
> --Steve
> 
> On 1/3/18, 10:18 pm, "Per Liden" <per.liden at oracle.com> wrote:
> 
>      On 03/01/2018 12:12 PM, Per Liden wrote:
>      > Hi,
>      >
>      > On 03/01/2018 01:52 AM, Steve Blackburn wrote:
>      >> Hi all,
>      >>
>      >> I just stumbled upon this thread, and thought I ought to chime in.
>      >>
>      >> You may find our prefetch paper from 10 years ago useful.   Or not! :-).
>      >>
>      >> http://users.cecs.anu.edu.au/~steveb/downloads/pdf/pf-ismm-2007.pdf
>      >
>      > Thanks for the pointer. Link above doesn't seem to work for me, but I
>      > found the paper through ACM.
>      >
>      >>
>      >> The short version is that there were a number of efforts to get
>      >> prefetching working well in the past, but none were effective.  We did
>      >> a pretty detailed study and managed to get some very nice results,
>      >> with two important changes:
>      >>
>      >>    *   FIFO front end to mark queue (without the FIFO the prefetch
>      >> distance is unpredictable)
>      >>    *   Enqueue edges rather than nodes
>      >> Obviously, the situation is different here (concurrent, big change in
>      >> uarch, etc), but still there are some core ideas that you probably
>      >> ought to know.
>      >>
>      >> The impatient may want to jump to section 7.2 and 7.3.    Note the
>      >> last para of 7.3: just adding the FIFO, with no software prefetch may
>      >> bring a win on some architectures.
>      >
>      > We do enqueue edges in ZGC (to enable "striped marking"), so we're
>      > fairly good positioned for prefetching to work, one would think. I
>      > recently did some quick tests with a FIFO in front of the mark stack
>      > (which would match "EdgeSide" in the paper) with varying prefetch
>      > distance, but wasn't able to observe any real improvements. More
>      > measurements and analysis would be needed to understand why.
>      
>      Here's the FIFO prefetch patch I did, in case anyone is interested in
>      doing more work/analysis in this area:
>      
>      http://cr.openjdk.java.net/~pliden/zgc/mark_prefetch/webrev.0/
>      
>      cheers,
>      Per
>      
>      >
>      > cheers,
>      > Per
>      >
>      >>
>      >> Cheers,
>      >>
>      >> --Steve
>      >>
>      >> On 02/14/2018 05:23 PM, Wilkinson, Hugh wrote:
>      >>> I have been looking at this also.
>      >>>
>      >>> I find that if the prefetching occurs 3 popped entries ahead of the
>      >>> processing, then there is a worthwhile benefit.
>      >>>
>      >>> A bit of re-structuring is required to make this easy and efficient.
>      >>>
>      >>> I am prefetching 2 cache lines from the referenced object and also
>      >>> doing a PREFETCHW of the mark bitmap.  (Prefetch::write() requires
>      >>> modification for x86.)
>      >>>
>      >>> With the current code structure, removal of the Prefetch::read()
>      >>> probably makes sense; however, I would like to highlight that marking
>      >>> performance can be improved with sufficiently early software cache
>      >>> prefetches.
>      >>>
>      >>> I expect to share more details later.
>      >>
>      >> Looking forward to that!
>      >>
>      >> cheers,
>      >> Per
>      >>
>      
>