[RFC] Optimize memset with conditional moves.

Hi,

I got idea that I mentioned on aarch thread to improve memset and memcpy
performance by using conditional moves to avoid branch misprediction
penalty. Previously setting one byte was very slow as we needed decision
tree to determine implementation for each size and for some range it
needed to be slow so we selected this one as unlikely.

A trick that I use could be done in C to handle n less than 16

char stack[64];
uint64_t *p1 = (uint64_t *) s;
uint32_t *p2 = (uint32_t *) (s + (n & 8));
uint16_t *p3 = (uint16_t *) (s + (n & 12));
char *p4 = s + n - 1;
if (n & 8 == 0) p1 = stack;
if (n & 4 == 0) p2 = stack;
if (n & 2 == 0) p3 = stack;
if (n & 1 == 0) p4 = stack;
*p1 = vc;
*p2 = vc;
*p3 = vc;
*p4 = vc;

and for 32-128 byte range its same as what in 16-64 range you could do
with 8 byte moves

char stack[64];
int add = n > 32 ? 16 : 0;
int sub = n > 32 ? -16 : 0;
*((uint64_t *)(s)) = vc;
*((uint64_t *)(s + 8)) = vc;
*((uint64_t *)(s + add)) = vc;
*((uint64_t *)(s + 8 + add)) = vc;
*((uint64_t *)(s + n - 16)) = vc;
*((uint64_t *)(s + 8 + n - 16)) = vc;
*((uint64_t *)(s + n - 16 + sub)) = vc;
*((uint64_t *)(s + 8 + n - 16 + sub)) = vc;

This could be used generically, I believe that on arm it could give
considerable speedup but would need access to machine for testing.

This gives on average 5% over current implementation, see profile
results here, I will resend alternate rep stosq implementation later,
see following:

http://kam.mff.cuni.cz/~ondra/benchmark_string/memset_profile_cmov.html
http://kam.mff.cuni.cz/~ondra/benchmark_string/memset_profile_cmov270815.tar.bz2

That as I recall was where I left memset as I didn't know on which sizes
to select it as it needs to be set empirically and is different for each
architecture. Problem is that on most architectures its faster when data
are in L3 cache or main memory and I dont know since what sizes it
usually happens as it may be case in lot smaller size than cache size
limit.

I also included optimization of counted loop, which helps processor to
correctly predict end until 512 bytes.

Second one is that I extended header to sizes upto 256 bytes which gives
additional one percent or so.


There is additional microoptimization possible that I could save few
cycles with ssse3 pshufb so should I add another variant there
surrounded by standard #ifdef USE_SSSE3 pattern?

I didn't do more performance testing yet as I plan to use this pattern
also for memcpy and strcpy.

So comments?

	* sysdeps/x86_64/memset.S: Use conditional moves to improve
	performance.

On Thu, Aug 27, 2015 at 9:28 AM, Ondřej Bílka <neleai@seznam.cz> wrote:
> Hi,
>
> I got idea that I mentioned on aarch thread to improve memset and memcpy
> performance by using conditional moves to avoid branch misprediction
> penalty. Previously setting one byte was very slow as we needed decision
> tree to determine implementation for each size and for some range it
> needed to be slow so we selected this one as unlikely.
>
> A trick that I use could be done in C to handle n less than 16
>
> char stack[64];
> uint64_t *p1 = (uint64_t *) s;
> uint32_t *p2 = (uint32_t *) (s + (n & 8));
> uint16_t *p3 = (uint16_t *) (s + (n & 12));
> char *p4 = s + n - 1;
> if (n & 8 == 0) p1 = stack;
> if (n & 4 == 0) p2 = stack;
> if (n & 2 == 0) p3 = stack;
> if (n & 1 == 0) p4 = stack;
> *p1 = vc;
> *p2 = vc;
> *p3 = vc;
> *p4 = vc;
>
> and for 32-128 byte range its same as what in 16-64 range you could do
> with 8 byte moves
>
> char stack[64];
> int add = n > 32 ? 16 : 0;
> int sub = n > 32 ? -16 : 0;
> *((uint64_t *)(s)) = vc;
> *((uint64_t *)(s + 8)) = vc;
> *((uint64_t *)(s + add)) = vc;
> *((uint64_t *)(s + 8 + add)) = vc;
> *((uint64_t *)(s + n - 16)) = vc;
> *((uint64_t *)(s + 8 + n - 16)) = vc;
> *((uint64_t *)(s + n - 16 + sub)) = vc;
> *((uint64_t *)(s + 8 + n - 16 + sub)) = vc;
>
> This could be used generically, I believe that on arm it could give
> considerable speedup but would need access to machine for testing.
>
> This gives on average 5% over current implementation, see profile
> results here, I will resend alternate rep stosq implementation later,
> see following:
>
> http://kam.mff.cuni.cz/~ondra/benchmark_string/memset_profile_cmov.html
> http://kam.mff.cuni.cz/~ondra/benchmark_string/memset_profile_cmov270815.tar.bz2
>
> That as I recall was where I left memset as I didn't know on which sizes
> to select it as it needs to be set empirically and is different for each
> architecture. Problem is that on most architectures its faster when data
> are in L3 cache or main memory and I dont know since what sizes it
> usually happens as it may be case in lot smaller size than cache size
> limit.
>
> I also included optimization of counted loop, which helps processor to
> correctly predict end until 512 bytes.
>
> Second one is that I extended header to sizes upto 256 bytes which gives
> additional one percent or so.
>
>
> There is additional microoptimization possible that I could save few
> cycles with ssse3 pshufb so should I add another variant there
> surrounded by standard #ifdef USE_SSSE3 pattern?
>
> I didn't do more performance testing yet as I plan to use this pattern
> also for memcpy and strcpy.
>
> So comments?
>
>         * sysdeps/x86_64/memset.S: Use conditional moves to improve
>         performance.
>
> diff --git a/sysdeps/x86_64/memset.S b/sysdeps/x86_64/memset.S
> index e496254..bea402d 100644
> --- a/sysdeps/x86_64/memset.S
> +++ b/sysdeps/x86_64/memset.S
> @@ -24,7 +24,7 @@
>  ENTRY(__bzero)
>         movq    %rdi, %rax /* Set return value.  */
>         movq    %rsi, %rdx /* Set n.  */
> -       pxor    %xmm8, %xmm8
> +       pxor    %xmm0, %xmm0

The  %xmm8->%xmm0 changes are in master branch now.

>         jmp     L(entry_from_bzero)
>  END(__bzero)
>  weak_alias (__bzero, bzero)
> @@ -33,10 +33,10 @@ weak_alias (__bzero, bzero)
>  ENTRY(__memset_tail)
>         movq    %rcx, %rax /* Set return value.  */
>
> -       movd    %esi, %xmm8
> -       punpcklbw       %xmm8, %xmm8
> -       punpcklwd       %xmm8, %xmm8
> -       pshufd  $0, %xmm8, %xmm8
> +       movd    %esi, %xmm0
> +       punpcklbw %xmm0, %xmm0
> +       punpcklwd %xmm0, %xmm0
> +       pshufd  $0, %xmm0, %xmm0
>
>         jmp     L(entry_from_bzero)
>  END(__memset_tail)
> @@ -50,78 +50,116 @@ END_CHK (__memset_chk)
>  #endif
>
>  ENTRY (memset)
> -       movd    %esi, %xmm8
> +       movd    %esi, %xmm0
>         movq    %rdi, %rax
> -       punpcklbw       %xmm8, %xmm8
> -       punpcklwd       %xmm8, %xmm8
> -       pshufd  $0, %xmm8, %xmm8
> +       punpcklbw %xmm0, %xmm0
> +       punpcklwd %xmm0, %xmm0
> +       pshufd  $0, %xmm0, %xmm0
>  L(entry_from_bzero):
> -       cmpq    $64, %rdx
> +       cmpq    $256, %rdx
>         ja      L(loop_start)
> -       cmpq    $16, %rdx
> -       jbe     L(less_16_bytes)
> -       cmpq    $32, %rdx
> -       movdqu  %xmm8, (%rdi)
> -       movdqu  %xmm8, -16(%rdi,%rdx)
> -       ja      L(between_32_64_bytes)
> -L(return):
> -       rep
> +       cmp     $128, %edx
> +       jae     L(between_128_256_bytes)
> +
> +       cmp     $32, %edx
> +       jb      L(less_32_bytes)
> +
> +       lea     -32(%rdi), %rcx
> +       lea     32(%rdi), %rsi
> +
> +       cmp     $64, %edx
> +       cmovb   %rdi, %rcx
> +       cmovb   %rdi, %rsi
> +
> +       movdqu  %xmm0, (%rdi)
> +       movdqu  %xmm0, 16(%rdi)
> +       movdqu  %xmm0, (%rsi)
> +       movdqu  %xmm0, 16(%rsi)
> +
> +       movdqu  %xmm0, -32(%rcx, %rdx)
> +       movdqu  %xmm0, -16(%rcx, %rdx)
> +       movdqu  %xmm0, -32(%rdi, %rdx)
> +       movdqu  %xmm0, -16(%rdi, %rdx)
>         ret
> +
>         .p2align 4
> -L(between_32_64_bytes):
> -       movdqu  %xmm8, 16(%rdi)
> -       movdqu  %xmm8, -32(%rdi,%rdx)
> +L(between_128_256_bytes):
> +       lea     (%rdi, %rdx), %rsi
> +       movdqu  %xmm0, (%rdi)
> +       movdqu  %xmm0, 16(%rdi)
> +       movdqu  %xmm0, 32(%rdi)
> +       movdqu  %xmm0, 48(%rdi)
> +       movdqu  %xmm0, 64(%rdi)
> +       movdqu  %xmm0, 80(%rdi)
> +       movdqu  %xmm0, 96(%rdi)
> +       movdqu  %xmm0, 112(%rdi)
> +       movdqu  %xmm0, -128(%rsi)
> +       movdqu  %xmm0, -112(%rsi)
> +       movdqu  %xmm0, -96(%rsi)
> +       movdqu  %xmm0, -80(%rsi)
> +       movdqu  %xmm0, -64(%rsi)
> +       movdqu  %xmm0, -48(%rsi)
> +       movdqu  %xmm0, -32(%rsi)
> +       movdqu  %xmm0, -16(%rsi)
>         ret
> +
>         .p2align 4
>  L(loop_start):
> -       leaq    64(%rdi), %rcx
> -       movdqu  %xmm8, (%rdi)
> -       andq    $-64, %rcx
> -       movdqu  %xmm8, -16(%rdi,%rdx)
> -       movdqu  %xmm8, 16(%rdi)
> -       movdqu  %xmm8, -32(%rdi,%rdx)
> -       movdqu  %xmm8, 32(%rdi)
> -       movdqu  %xmm8, -48(%rdi,%rdx)
> -       movdqu  %xmm8, 48(%rdi)
> -       movdqu  %xmm8, -64(%rdi,%rdx)
> -       addq    %rdi, %rdx
> -       andq    $-64, %rdx
> -       cmpq    %rdx, %rcx
> -       je      L(return)
> -       .p2align 4
> +       lea     (%rdi, %rdx), %rsi
> +       leaq    16(%rdi), %rcx
> +       andq    $-16, %rcx
> +       movdqu  %xmm0, -16(%rsi)
> +       movdqu  %xmm0, -32(%rsi)
> +       movdqu  %xmm0, -48(%rsi)
> +       movdqu  %xmm0, -64(%rsi)
> +       movdqu  %xmm0, (%rdi)
> +       subq    %rcx, %rsi
> +       shrq    $6, %rsi
>  L(loop):
> -       movdqa  %xmm8, (%rcx)
> -       movdqa  %xmm8, 16(%rcx)
> -       movdqa  %xmm8, 32(%rcx)
> -       movdqa  %xmm8, 48(%rcx)
> +       movdqa  %xmm0, (%rcx)
> +       movdqa  %xmm0, 16(%rcx)
> +       movdqa  %xmm0, 32(%rcx)
> +       movdqa  %xmm0, 48(%rcx)
>         addq    $64, %rcx
> -       cmpq    %rcx, %rdx
> +       subq    $1, %rsi
>         jne     L(loop)
> -       rep
> -       ret
> -L(less_16_bytes):
> -       movq %xmm8, %rcx
> -       testb   $24, %dl
> -       jne     L(between8_16bytes)
> -       testb   $4, %dl
> -       jne     L(between4_7bytes)
> -       testb   $1, %dl
> -       je      L(odd_byte)
> -       movb    %cl, (%rdi)
> -L(odd_byte):
> -       testb   $2, %dl
> -       je      L(return)
> -       movw    %cx, -2(%rax,%rdx)
> -       ret
> -L(between4_7bytes):
> -       movl    %ecx, (%rdi)
> -       movl    %ecx, -4(%rdi,%rdx)
> -       ret
> -L(between8_16bytes):
> -       movq    %rcx, (%rdi)
> -       movq    %rcx, -8(%rdi,%rdx)
>         ret
>
> +L(less_32_bytes):
> +       movq    %xmm0, %rcx
> +       lea     -64(%rsp), %r10
> +       sub     %rax, %r10
> +       lea     64(%rdi), %r9
> +       lea     63(%rdi, %rdx), %rsi
> +       mov     %rdx, %r8
> +       mov     %rdx, %r11
> +       mov     %rdx, %rdi
> +       and     $16, %r8
> +       and     $24, %rdi
> +       and     $28, %r11
> +
> +       test    $16, %edx
> +       cmove   %rsp, %r9
> +
> +       test    $8, %edx
> +       cmove   %r10, %r8
> +
> +       test    $4, %edx
> +       cmove   %r10, %rdi
> +
> +       test    $2, %edx
> +       cmove   %r10, %r11
> +
> +       test    $1, %edx
> +       cmove   %rsp, %rsi
> +
> +       movdqu  %xmm0, -64(%r9)
> +       movq    %rcx, (%rax, %r8)
> +       movl    %ecx, (%rax, %rdi)
> +       movw    %cx, (%rax, %r11)
> +       movb    %cl, -64(%rsi)
> +
> +       ret
>  END (memset)
>  libc_hidden_builtin_def (memset)
>

They look OK to me.

Thanks.