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

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;
>  	}
>