[PATCH 1/2] x86_64/memset: avoid multiply insn if possible

[PATCH 1/2] x86_64/memset: avoid multiply insn if possible

[Denys Vlasenko]

memset is very, very often called with fill=0,
and 64-bit imul is expensive on many CPUs.
Avoid it if fill=0.

Also avoid multiply on "short memset" codepath if possible,
and when we do need it, use 32-bit one, which is cheaper on many CPUs.

Signed-off-by: Denys Vlasenko <vda.linux@googlemail.com>
---
 src/string/x86_64/memset.s | 34 +++++++++++++++++++++-------------
 1 file changed, 21 insertions(+), 13 deletions(-)

diff --git a/src/string/x86_64/memset.s b/src/string/x86_64/memset.s
index 3cc8fcf..523caa0 100644
--- a/src/string/x86_64/memset.s
+++ b/src/string/x86_64/memset.s
@@ -1,13 +1,12 @@
 .global memset
 .type memset,@function
 memset:
-	movzbl %sil,%esi
-	mov $0x101010101010101,%rax
-	# 64-bit imul has 3-7 cycles latency, launch early
-	imul %rsi,%rax
-
+	movzbq %sil,%rax
 	cmp $16,%rdx
-	jb 1f
+	jb .Less_than_16
+	test %esi,%esi
+	jnz .L_widen_rax  # unlikely
+.L_widened:
 
 	lea -1(%rdx),%rcx
 	mov %rdi,%r8
@@ -18,26 +17,35 @@ memset:
 	mov %r8,%rax
 	ret
 
-1:	test %edx,%edx
-	jz 1f
+.L_widen_rax:
+	# 64-bit imul has 3-7 cycles latency
+	mov $0x101010101010101,%rsi
+	imul %rsi,%rax
+	jmp .L_widened
+
+.Less_than_16:
+	test %edx,%edx
+	jz .L_ret
 
 	mov %al,(%rdi)
 	mov %al,-1(%rdi,%rdx)
 	cmp $2,%edx
-	jbe 1f
+	jbe .L_ret
 
 	mov %al,1(%rdi)
 	mov %al,-2(%rdi,%rdx)
+	# 32-bit imul has 3-4 cycles latency
+	imul $0x1010101,%eax
 	cmp $4,%edx
-	jbe 1f
+	jbe .L_ret
 
 	mov %eax,(%rdi)
 	mov %eax,-4(%rdi,%rdx)
 	cmp $8,%edx
-	jbe 1f
+	jbe .L_ret
 
 	mov %eax,4(%rdi)
 	mov %eax,-8(%rdi,%rdx)
-
-1:	mov %rdi,%rax
+.L_ret:
+	mov %rdi,%rax
 	ret
-- 
1.8.1.4

[PATCH 2/2] x86_64/memset: align destination to 8 byte boundary

[Denys Vlasenko]

8-byte alignment gives ~25% speedup on "rep stosq" memsets
to L1 cache, compared to intentionally misaligned ones.
It is a smaller win of ~15% on larger memsets to L2 too.
Measured on Intel Sandy Bridge CPU (i7-2620M, 2.70GHz)

Signed-off-by: Denys Vlasenko <vda.linux@googlemail.com>
---
 src/string/x86_64/memset.s | 22 +++++++++++++++++++++-
 1 file changed, 21 insertions(+), 1 deletion(-)

diff --git a/src/string/x86_64/memset.s b/src/string/x86_64/memset.s
index 523caa0..5c9e333 100644
--- a/src/string/x86_64/memset.s
+++ b/src/string/x86_64/memset.s
@@ -4,16 +4,23 @@ memset:
 	movzbq %sil,%rax
 	cmp $16,%rdx
 	jb .Less_than_16
+
 	test %esi,%esi
 	jnz .L_widen_rax  # unlikely
 .L_widened:
 
-	lea -1(%rdx),%rcx
 	mov %rdi,%r8
+
+	test $7,%dil
+	jnz .L_align  # unlikely
+.L_aligned:
+
+	lea -1(%rdx),%rcx
 	shr $3,%rcx
 	mov %rax,-8(%rdi,%rdx)
 	rep
 	stosq
+
 	mov %r8,%rax
 	ret
 
@@ -23,6 +30,19 @@ memset:
 	imul %rsi,%rax
 	jmp .L_widened
 
+# 8-byte alignment gives ~25% speedup on "rep stosq" memsets
+# to L1 cache, compared to intentionally misaligned ones.
+# It is a smaller win of ~15% on larger memsets to L2 too.
+# Measured on Intel Sandy Bridge CPU (i7-2620M, 2.70GHz)
+.L_align:
+	mov %rax,(%rdi)
+1:	inc %rdi
+	dec %rdx
+	test $7,%dil
+	jnz 1b
+	jmp .L_aligned
+
+
 .Less_than_16:
 	test %edx,%edx
 	jz .L_ret
-- 
1.8.1.4

Re: [PATCH 1/2] x86_64/memset: avoid multiply insn if possible

[Rich Felker]

On Thu, Feb 12, 2015 at 06:17:02PM +0100, Denys Vlasenko wrote:
> memset is very, very often called with fill=0,
> and 64-bit imul is expensive on many CPUs.
> Avoid it if fill=0.
> 
> Also avoid multiply on "short memset" codepath if possible,
> and when we do need it, use 32-bit one, which is cheaper on many CPUs.

I'd actually like to extend the "short" range up to at least 32 bytes
using two 8-byte writes for the middle, unless the savings from using
32-bit imul instead of 64-bit are sufficient to justify 4 4-byte
writes for the middle. On the cpu I tested on, the difference is 11
cycles vs 32 cycles for non-rep path versus rep path at size 32.

> Signed-off-by: Denys Vlasenko <vda.linux@googlemail.com>
> ---
>  src/string/x86_64/memset.s | 34 +++++++++++++++++++++-------------
>  1 file changed, 21 insertions(+), 13 deletions(-)
> 
> diff --git a/src/string/x86_64/memset.s b/src/string/x86_64/memset.s
> index 3cc8fcf..523caa0 100644
> --- a/src/string/x86_64/memset.s
> +++ b/src/string/x86_64/memset.s
> @@ -1,13 +1,12 @@
>  .global memset
>  .type memset,@function
>  memset:
> -	movzbl %sil,%esi
> -	mov $0x101010101010101,%rax
> -	# 64-bit imul has 3-7 cycles latency, launch early
> -	imul %rsi,%rax
> -
> +	movzbq %sil,%rax
>  	cmp $16,%rdx
> -	jb 1f
> +	jb .Less_than_16
> +	test %esi,%esi
> +	jnz .L_widen_rax  # unlikely
> +.L_widened:

Generally I prefer unnamed labels, but I think you've reached the
level where the code is getting confusing without names, so I'm fine
with having them here.

Once you're done with improvements to the 64-bit version, do you plan
to adapt the same principles to the 32-bit version? Or should I or
someone else work on that later?

Rich

Re: [PATCH 1/2] x86_64/memset: avoid multiply insn if possible

[Denys Vlasenko]

On Thu, Feb 12, 2015 at 6:27 PM, Rich Felker <dalias@libc.org> wrote:
> On Thu, Feb 12, 2015 at 06:17:02PM +0100, Denys Vlasenko wrote:
>> memset is very, very often called with fill=0,
>> and 64-bit imul is expensive on many CPUs.
>> Avoid it if fill=0.
>>
>> Also avoid multiply on "short memset" codepath if possible,
>> and when we do need it, use 32-bit one, which is cheaper on many CPUs.
>
> I'd actually like to extend the "short" range up to at least 32 bytes
> using two 8-byte writes for the middle, unless the savings from using
> 32-bit imul instead of 64-bit are sufficient to justify 4 4-byte
> writes for the middle. On the cpu I tested on, the difference is 11
> cycles vs 32 cycles for non-rep path versus rep path at size 32.

The short path causes mixed feelings in me.

On one hand, it's elegant in a contrived way.

On the other hand, multiple
overlaying stores must be causing hell in store unit.
I'm thinking, maybe there's a faster way to do that.

Can you post your memset testsuite?

Re: [PATCH 1/2] x86_64/memset: avoid multiply insn if possible

[Denys Vlasenko]

[-- Attachment #1: Type: text/plain, Size: 811 bytes --]

On Thu, Feb 12, 2015 at 8:26 PM, Denys Vlasenko
<vda.linux@googlemail.com> wrote:
>> I'd actually like to extend the "short" range up to at least 32 bytes
>> using two 8-byte writes for the middle, unless the savings from using
>> 32-bit imul instead of 64-bit are sufficient to justify 4 4-byte
>> writes for the middle. On the cpu I tested on, the difference is 11
>> cycles vs 32 cycles for non-rep path versus rep path at size 32.
>
> The short path causes mixed feelings in me.
>
> On one hand, it's elegant in a contrived way.
>
> On the other hand, multiple
> overlaying stores must be causing hell in store unit.
> I'm thinking, maybe there's a faster way to do that.

For example, like in the attached implementation.

This one will not perform eight stores to memory
to fill 15 byte area... only two.

[-- Attachment #2: memset.s --]
[-- Type: application/octet-stream, Size: 1136 bytes --]

.global memset
.type memset,@function
memset:
	movzbq %sil,%rax
	test %esi,%esi
	jnz .L_widen_rax  # unlikely
.L_widened:

	mov %rdi,%r8

	cmp $16,%rdx
	jbe .Less_than_or_equal_16

	test $7,%dil
	jnz .L_align  # unlikely
.L_aligned:

	lea -1(%rdx),%rcx
	shr $3,%rcx
	mov %rax,-8(%rdi,%rdx)
	rep
	stosq

	mov %r8,%rax
	ret

.L_widen_rax:
	# 64-bit imul has 3-7 cycles latency
	mov $0x101010101010101,%rsi
	imul %rsi,%rax
	jmp .L_widened

# 8-byte alignment gives ~25% speedup on "rep stosq" memsets
# to L1 cache, compared to intentionally misaligned ones.
# It is a smaller win of ~15% on larger memsets to L2 too.
# Measured on Intel Sandy Bridge CPU (i7-2620M, 2.70GHz)
.L_align:
	mov %rax,(%rdi)
1:	inc %rdi
	dec %rdx
	test $7,%dil
	jnz 1b
	jmp .L_aligned


.Less_than_or_equal_16:
	jb 1f
    # fill 8-16 bytes:
0:	mov %rax,(%rdi)
	mov %rax,-8(%rdi,%rdx)
	mov %r8,%rax
	ret
1:	test $8,%dl
	jnz 0b

	test $4,%dl
	jz 1f
    # fill 4-7 bytes:
	mov %eax,(%rdi)
	mov %eax,-4(%rdi,%rdx)
	mov %r8,%rax
	ret

    # fill 0-3 bytes:
1:	test $2,%dl
	jz 1f
	mov %ax,(%rdi)
	add $2,%rdi
1:	test $1,%dl
	jz 1f
	mov %al,(%rdi)
1:	mov %r8,%rax
	ret

Re: [PATCH 1/2] x86_64/memset: avoid multiply insn if possible

[Rich Felker]

On Thu, Feb 12, 2015 at 09:36:26PM +0100, Denys Vlasenko wrote:
> On Thu, Feb 12, 2015 at 8:26 PM, Denys Vlasenko
> <vda.linux@googlemail.com> wrote:
> >> I'd actually like to extend the "short" range up to at least 32 bytes
> >> using two 8-byte writes for the middle, unless the savings from using
> >> 32-bit imul instead of 64-bit are sufficient to justify 4 4-byte
> >> writes for the middle. On the cpu I tested on, the difference is 11
> >> cycles vs 32 cycles for non-rep path versus rep path at size 32.
> >
> > The short path causes mixed feelings in me.
> >
> > On one hand, it's elegant in a contrived way.
> >
> > On the other hand, multiple
> > overlaying stores must be causing hell in store unit.
> > I'm thinking, maybe there's a faster way to do that.

In practice it performs quite well. x86's are good at this. The
generic C code in memset.c does not do any overlapping writes of
different sizes for the short buffer code path -- all writes there are
single-byte, and multiple-write only happens for some of the inner
bytes depending on the value of n.

> For example, like in the attached implementation.
> 
> This one will not perform eight stores to memory
> to fill 15 byte area... only two.

I could try comparing its performance, but I expect branches to cost a
lot more than redundant stores to cached memory. My approach in the C
code seems to be the absolute minimum possible number of branches for
short memsets, and it pays off -- it's even faster than the current
asm for these small sizes.

Rich

Re: [PATCH 1/2] x86_64/memset: avoid multiply insn if possible

[Denys Vlasenko]

On Fri, Feb 13, 2015 at 8:24 AM, Rich Felker <dalias@libc.org> wrote:
> On Thu, Feb 12, 2015 at 09:36:26PM +0100, Denys Vlasenko wrote:
> In practice it performs quite well. x86's are good at this. The
> generic C code in memset.c does not do any overlapping writes of
> different sizes for the short buffer code path -- all writes there are
> single-byte, and multiple-write only happens for some of the inner
> bytes depending on the value of n.

Measurements agree: I was not able to make it faster by doing it
differently.
I did find it possible to extend your trick to be usable for up to 30
byte blocks.
Sending the patch...