[1/2] powerpc: Add 64bit optimised memcmp

I noticed ksm spending quite a lot of time in memcmp on a large
KVM box. The current memcmp loop is very unoptimised - byte at a
time compares with no loop unrolling. We can do much much better.

Optimise the loop in a few ways:

- Unroll the byte at a time loop

- For large (at least 32 byte) comparisons that are also 8 byte
  aligned, use an unrolled modulo scheduled loop using 8 byte
  loads. This is similar to our glibc memcmp.

A simple microbenchmark testing 10000000 iterations of an 8192 byte
memcmp was used to measure the performance:

baseline:	29.93 s

modified:	 1.70 s

Just over 17x faster.

Signed-off-by: Anton Blanchard <anton@samba.org>
---
 arch/powerpc/lib/Makefile    |   3 +-
 arch/powerpc/lib/memcmp_64.S | 233 +++++++++++++++++++++++++++++++++++++++++++
 arch/powerpc/lib/string.S    |   2 +
 3 files changed, 237 insertions(+), 1 deletion(-)
 create mode 100644 arch/powerpc/lib/memcmp_64.S

From: Anton Blanchard

> I noticed ksm spending quite a lot of time in memcmp on a large

> KVM box. The current memcmp loop is very unoptimised - byte at a

> time compares with no loop unrolling. We can do much much better.

> 

> Optimise the loop in a few ways:

> 

> - Unroll the byte at a time loop

> 

> - For large (at least 32 byte) comparisons that are also 8 byte

>   aligned, use an unrolled modulo scheduled loop using 8 byte

>   loads. This is similar to our glibc memcmp.

> 

> A simple microbenchmark testing 10000000 iterations of an 8192 byte

> memcmp was used to measure the performance:

> 

> baseline:	29.93 s

> 

> modified:	 1.70 s

> 

> Just over 17x faster.


The unrolled loop (deleted) looks excessive.
On a modern cpu with multiple execution units you can usually
manage to get the loop overhead to execute in parallel to the
actual 'work'.
So I suspect that a much simpler 'word at a time' loop will be
almost as fast - especially in the case where the code isn't
already in the cache and the compare is relatively short.
Try something based on:
	a1 = *a++;
	b1 = *b++;
	while {
		a2 = *a++;
		b2 = *b++;
		if (a1 != a2)
			break;
		a1 = *a++;
		b1 = *b++;
	} while (a2 != a1);

	David

On 08-01-2015 23:56, Anton Blanchard wrote:
> I noticed ksm spending quite a lot of time in memcmp on a large
> KVM box. The current memcmp loop is very unoptimised - byte at a
> time compares with no loop unrolling. We can do much much better.
>
> Optimise the loop in a few ways:
>
> - Unroll the byte at a time loop
>
> - For large (at least 32 byte) comparisons that are also 8 byte
>   aligned, use an unrolled modulo scheduled loop using 8 byte
>   loads. This is similar to our glibc memcmp.
>
> A simple microbenchmark testing 10000000 iterations of an 8192 byte
> memcmp was used to measure the performance:
>
> baseline:	29.93 s
>
> modified:	 1.70 s
>
> Just over 17x faster.
>
> Signed-off-by: Anton Blanchard <anton@samba.org>
>
Why not use glibc implementations instead? All of them (ppc64, power4, and
power7) avoids use byte at time compares for unaligned cases inputs; while
showing the same performance for aligned one than this new implementation.
To give you an example, a 8192 bytes compare with input alignment of 63/18
shows:

__memcmp_power7:  320 cycles
__memcmp_power4:  320 cycles
__memcmp_ppc64:   340 cycles
this memcmp:     3185 cycles

Hi David,

> The unrolled loop (deleted) looks excessive.
> On a modern cpu with multiple execution units you can usually
> manage to get the loop overhead to execute in parallel to the
> actual 'work'.
> So I suspect that a much simpler 'word at a time' loop will be
> almost as fast - especially in the case where the code isn't
> already in the cache and the compare is relatively short.

I'm always keen to keep things as simple as possible, but your loop is
over 50% slower. Once the loop hits a steady state you are going to run
into front end issues with instruction fetch on POWER8.

Anton

> Try something based on:
> 	a1 = *a++;
> 	b1 = *b++;
> 	while {
> 		a2 = *a++;
> 		b2 = *b++;
> 		if (a1 != a2)
> 			break;
> 		a1 = *a++;
> 		b1 = *b++;
> 	} while (a2 != a1);
> 
> 	David
>

On Mon, 2015-01-12 at 11:55 +1100, Anton Blanchard wrote:
> Hi David,
> 
> > The unrolled loop (deleted) looks excessive.
> > On a modern cpu with multiple execution units you can usually
> > manage to get the loop overhead to execute in parallel to the
> > actual 'work'.
> > So I suspect that a much simpler 'word at a time' loop will be almost as fast - especially in the case where the code isn't
> > already in the cache and the compare is relatively short.
> 
> I'm always keen to keep things as simple as possible, but your loop is over 50% slower. Once the loop hits a steady state you are going to run into front end issues with instruction fetch on POWER8.
> 

Out of curiosity, does preincrement make any difference(or can gcc do that for you nowadays)?

         a1 = *a;
         b1 = *b;
         while {
                 a2 = *++a;
                 b2 = *++b;
                 if (a1 != a2)
                 break;
                 a1 = *++a;
                 b1 = *++b;
         } while (a2 != a1);

 Jocke

> Anton
> 
> > Try something based on:
> >         a1 = *a++;
> >         b1 = *b++;
> >         while {
> >                 a2 = *a++;
> >                 b2 = *b++;
> >                 if (a1 != a2)
> >                 break;
> >                 a1 = *a++;
> >                 b1 = *b++;
> >         } while (a2 != a1);
> > 
> >         David
> > 
> 
> _______________________________________________
> Linuxppc-dev mailing list Linuxppc-dev@lists.ozlabs.org https://lists.ozlabs.org/listinfo/linuxppc-dev

From: Joakim Tjernlund 
> On Mon, 2015-01-12 at 11:55 +1100, Anton Blanchard wrote:
> > Hi David,
> >
> > > The unrolled loop (deleted) looks excessive.
> > > On a modern cpu with multiple execution units you can usually
> > > manage to get the loop overhead to execute in parallel to the
> > > actual 'work'.
> > > So I suspect that a much simpler 'word at a time' loop will be almost as fast - especially in the
> case where the code isn't
> > > already in the cache and the compare is relatively short.
> >
> > I'm always keen to keep things as simple as possible, but your loop is over 50% slower. Once the
> loop hits a steady state you are going to run into front end issues with instruction fetch on POWER8.

Interesting, I'm not an expert on ppc scheduling, but on my old x86 Athon 700 (I think
it was that one) a similar loop ran as fast as 'rep movsw'.

> Out of curiosity, does preincrement make any difference(or can gcc do that for you nowadays)?

It will only change register pressure slightly, and might allow any execution
delays be filled - but that is very processor dependant.
Actually you probably want to do 'a += 2' somewhere to reduce the instruction count.
Similarly the end condition needs to compare one of the pointers.

Elsewhere (not ppc) I've used (++p)[-1] instead of *p++ to move the increment
before the load to get better scheduling.

>          a1 = *a;
>          b1 = *b;
>          while {
>                  a2 = *++a;
>                  b2 = *++b;
>                  if (a1 != a2)
     That should have been a1 != b1
>                  	break;
>                  a1 = *++a;
>                  b1 = *++b;
>          } while (a2 != a1);
     and a2 != b2

	David