[07/20] alpha: deepen memchr prefetch distance for EV7

  The alpha memchr already issues a read prefetch ahead of the scan, but only
three cache lines out -- tuned for the 21264 (EV6/67/68) and its external
Bcache.  On the 21364 (EV7), whose on-chip memory controller has a much longer
memory latency, three lines is too close to hide the miss.

Issue the prefetch eight cache lines ahead instead (both the priming prefetches
before the cacheline loop and the one inside it).  This is a read hint, so on
the 21264 a deeper distance is at worst dropped; no IMPLVER dispatch is needed.

Measured on an AlphaServer ES47 (EV7, 1.3GHz), cold cyc/call (full scan):
  size       before    after
  4096         3898     3268  1.19x
  65536       61359    52271  1.17x
  262144     246666   208148  1.19x

The 21264 side of that claim has since been measured rather than assumed: on
an EV68CB the read-prefetch distance curve for a streaming scan is flat from
four cache lines out to eight, so moving from three to eight neither helps nor
hurts there.

An assembly rewrite was prototyped but, with the deeper prefetch, a read-hint
loop measured no faster than this C.  The only further gain came from a
modify-intent (LDS/LDT) prefetch, which is not safe to issue on the read-only
operand of a general-purpose memchr: it requests the line for ownership, which
is wrong for a buffer the caller may share.  It is also not the win it looks
like.  On an EV68CB, modify intent on a pure read stream measures 2x slower
than a plain read prefetch -- for memcmp, 756446 cycles against 368989 on a
cold 256KB compare -- because ReadBlkMod provokes about twice the Mbox replay
traps.  Bcache misses are unchanged, so the cost is not the extra coherence
traffic one might expect; it is the replays.
---
 sysdeps/alpha/memchr.c | 15 ++++++++++-----
 1 file changed, 10 insertions(+), 5 deletions(-)
  

On 11/08/26 22:19, Matt Turner wrote:
> The alpha memchr already issues a read prefetch ahead of the scan, but only
> three cache lines out -- tuned for the 21264 (EV6/67/68) and its external
> Bcache.  On the 21364 (EV7), whose on-chip memory controller has a much longer
> memory latency, three lines is too close to hide the miss.
> 
> Issue the prefetch eight cache lines ahead instead (both the priming prefetches
> before the cacheline loop and the one inside it).  This is a read hint, so on
> the 21264 a deeper distance is at worst dropped; no IMPLVER dispatch is needed.
> 
> Measured on an AlphaServer ES47 (EV7, 1.3GHz), cold cyc/call (full scan):
>   size       before    after
>   4096         3898     3268  1.19x
>   65536       61359    52271  1.17x
>   262144     246666   208148  1.19x
> 
> The 21264 side of that claim has since been measured rather than assumed: on
> an EV68CB the read-prefetch distance curve for a streaming scan is flat from
> four cache lines out to eight, so moving from three to eight neither helps nor
> hurts there.
> 
> An assembly rewrite was prototyped but, with the deeper prefetch, a read-hint
> loop measured no faster than this C.  The only further gain came from a
> modify-intent (LDS/LDT) prefetch, which is not safe to issue on the read-only
> operand of a general-purpose memchr: it requests the line for ownership, which
> is wrong for a buffer the caller may share.  It is also not the win it looks
> like.  On an EV68CB, modify intent on a pure read stream measures 2x slower
> than a plain read prefetch -- for memcmp, 756446 cycles against 368989 on a
> cold 256KB compare -- because ReadBlkMod provokes about twice the Mbox replay
> traps.  Bcache misses are unchanged, so the cost is not the extra coherence
> traffic one might expect; it is the replays.

It would be good if we could *remove* the alpha implementation instead. I am
really not sure if comments:

 97         /* Within each cacheline, advance the load for the next word
 98            before the test for the previous word is complete.  This
 99            allows us to hide the 3 cycle L1 cache load latency.  We
100            only perform this advance load within a cacheline to prevent
101            reading across page boundary.  */

still holds for recent gcc.  These kind of hand-rolled pipelining were usually
done to overcome old compiler limitations.

I think the only major difference is that alpha implementation relies heavily
on software prefetch. And I recall from old arm/powerpc chips this is usually
a hit or miss, and can be a performance loss when uses without care.

So I wonder if can't do something like this instead:

--
diff --git a/string/memchr.c b/string/memchr.c
index 96afaa6f5e2..bdf2074974c 100644
--- a/string/memchr.c
+++ b/string/memchr.c
@@ -20,6 +20,7 @@
 #include <string-fzb.h>
 #include <string-fzc.h>
 #include <string-fzi.h>
+#include <string-prefetch.h>
 #include <string-shift.h>
 #include <string.h>

@@ -64,9 +65,13 @@ __memchr (void const *s, int c_in, size_t n)
   if (word_ptr == lword)
     return NULL;

+  string_prefetch_initial (word_ptr,
+                          (const char *) lword - (const char *) word_ptr);
+
   word = *++word_ptr;
   while (word_ptr != lword)
     {
+      string_prefetch (word_ptr);
       if (has_eq (word, repeated_c))
        return (char *) word_ptr + index_first_eq (word, repeated_c);
       word = *++word_ptr;
--

With a generic implementation being no-ops and alpha being something like:

  #define STRING_PREFETCH_AHEAD   192
  #define STRING_PREFETCH_STRIDE  64

  static __always_inline void
  string_prefetch_initial (const void *s, size_t len)
  {
    if (len >= STRING_PREFETCH_AHEAD)
      for (unsigned int i = STRING_PREFETCH_STRIDE;
           i < STRING_PREFETCH_AHEAD; i += STRING_PREFETCH_STRIDE)
        __builtin_prefetch ((const char *) s + i, 0, 3);
  }

  static __always_inline void
  string_prefetch (const void *s)
  {
    __builtin_prefetch ((const char *) s + STRING_PREFETCH_AHEAD, 0, 3);
  }

And might want to play with some -funroll-loops.


> ---
>  sysdeps/alpha/memchr.c | 15 ++++++++++-----
>  1 file changed, 10 insertions(+), 5 deletions(-)
> 
> diff --git ./sysdeps/alpha/memchr.c ./sysdeps/alpha/memchr.c
> index d9115923d2..663cd08454 100644
> --- ./sysdeps/alpha/memchr.c
> +++ ./sysdeps/alpha/memchr.c
> @@ -79,10 +79,15 @@ __memchr (const void *s, int xc, size_t n)
>    /* If the block is sufficiently large, align to cacheline and prefetch.  */
>    if (unlikely (n >= 256))
>      {
> -      /* Prefetch 3 cache lines beyond the one we're working on.  */
> -      prefetch (s_align + 8);
> -      prefetch (s_align + 16);
> +      /* Prefetch several cache lines beyond the one we're working on.
> +	 The 21364 (EV7), with its on-chip memory controller and much longer
> +	 memory latency than the 21264's external Bcache, needs the read
> +	 prefetch issued considerably further ahead to hide the miss; eight
> +	 lines beats the three that suit the 21264, and on the 21264 a deeper
> +	 read hint is at worst dropped.  */
>        prefetch (s_align + 24);
> +      prefetch (s_align + 40);
> +      prefetch (s_align + 56);
>  
>        while ((word)s_align & 63)
>  	{
> @@ -120,10 +125,10 @@ __memchr (const void *s, int xc, size_t n)
>  	} while (0)
>  
>        /* While there's still lots more data to potentially be read,
> -	 continue issuing prefetches for the 4th cacheline out.  */
> +	 continue issuing prefetches for the 8th cacheline out.  */
>        while (n >= 256)
>  	{
> -	  prefetch (s_align + 24);
> +	  prefetch (s_align + 64);
>  	  CACHELINE_LOOP;
>  	}
>