Skip to contentSkip to conversation

x86_64: new and improved memset() + question

PATCH In review Alexey Dobriyan 2 participants 3 messages Jan 17, 2019 – Feb 11, 2019 x86

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 x86_64: new and improved memset() + question

Current memset() implementation does silly things:
* multiplication to get wide constant:
waste of cycles if filler is known at compile time,

* REP STOSQ followed by REP STOSB:
this code is used when REP STOSB is slow but still it is used for small length (< 8) when setup overhead is relatively big,

* suboptimal calling convention:
REP STOSB/STOSQ favours (rdi, rcx)

* memset_orig():
it is hard to even look at it :^)

New implementation is based on the following observations:
* c == 0 is the most common form,
filler can be done with "xor eax, eax" and pushed into memset() saving 2 bytes per call and multiplication

* len divisible by 8 is the most common form:
all it takes is one pointer or unsigned long inside structure, dispatch at compile time to code without those ugly "lets fill at most 7 bytes" tails,

* multiplication to get wider filler value can be done at compile time for "c != 0" with 1 insn/10 bytes at most saving multiplication.

* those leaner forms of memset can be done withing 3/4 registers (RDI, RCX, RAX, [RSI]) saving the rest from clobbering.

Note: "memset0" name is chosen because "bzero" is officially deprecated.
Note: memset(,0,) form is interleaved into memset(,c,) form to save space.

QUESTION: is it possible to tell gcc "this function is semantically equivalent to memset(3) so make high level optimizations but call it when it is necessary"? I suspect the answer is "no" :-\

TODO:
CONFIG_FORTIFY_SOURCE is enabled by distros benchmarks
testing
more comments
check with memset_io() so that no surprises pop up

---

lightly boot tested by you get the idea where it is going...

 arch/x86/boot/compressed/Makefile |    1 
 arch/x86/include/asm/string_64.h  |  101 ++++++++++++++++++++++++++++++++++++++
 arch/x86/lib/Makefile             |    1 
 arch/x86/lib/memset0_64.S         |   86 ++++++++++++++++++++++++++++++++
 4 files changed, 189 insertions(+)
arch/x86/boot/compressed/Makefile +1 -0
@@ -38,6 +38,7 @@ KBUILD_CFLAGS += $(call cc-option,-fno-stack-protector)
 KBUILD_CFLAGS += $(call cc-disable-warning, address-of-packed-member)
 KBUILD_CFLAGS += $(call cc-disable-warning, gnu)
 KBUILD_CFLAGS += -Wno-pointer-sign
+KBUILD_CFLAGS += -D_ARCH_X86_BOOT
 
 KBUILD_AFLAGS  := $(KBUILD_CFLAGS) -D__ASSEMBLY__
 GCOV_PROFILE := n
arch/x86/include/asm/string_64.h +101 -0

108 lines not on this page · raw message

arch/x86/lib/Makefile +1 -0
@@ -47,6 +47,7 @@ else
         lib-y += csum-partial_64.o csum-copy_64.o csum-wrappers_64.o
         lib-y += clear_page_64.o copy_page_64.o
         lib-y += memmove_64.o memset_64.o
+	lib-y += memset0_64.o
         lib-y += copy_user_64.o
 	lib-y += cmpxchg16b_emu.o
 endif

new file mode 100644

arch/x86/lib/memset0_64.S new file +86 -0

86 lines not on this page · raw message

#1 lore raw
Quoted 24 lines · Alexey Dobriyan

Current memset() implementation does silly things:
* multiplication to get wide constant:
waste of cycles if filler is known at compile time,

* REP STOSQ followed by REP STOSB:
this code is used when REP STOSB is slow but still it is used for small length (< 8) when setup overhead is relatively big,

* suboptimal calling convention:
REP STOSB/STOSQ favours (rdi, rcx)

* memset_orig():
it is hard to even look at it :^)

New implementation is based on the following observations:
* c == 0 is the most common form,
filler can be done with "xor eax, eax" and pushed into memset() saving 2 bytes per call and multiplication

* len divisible by 8 is the most common form:
all it takes is one pointer or unsigned long inside structure, dispatch at compile time to code without those ugly "lets fill at most 7 bytes" tails,

Quoted 5 lines

* multiplication to get wider filler value can be done at compile time for "c != 0" with 1 insn/10 bytes at most saving multiplication.

* those leaner forms of memset can be done withing 3/4 registers (RDI, RCX, RAX, [RSI]) saving the rest from clobbering.

Ok, sorry about the belated reply - all that sounds like very nice improvements!

Quoted 7 lines

Note: "memset0" name is chosen because "bzero" is officially deprecated.
Note: memset(,0,) form is interleaved into memset(,c,) form to save space.

QUESTION: is it possible to tell gcc "this function is semantically equivalent to memset(3) so make high level optimizations but call it when it is necessary"? I suspect the answer is "no" :-\

No idea ...

Quoted 6 lines

TODO:
CONFIG_FORTIFY_SOURCE is enabled by distros benchmarks
testing
more comments
check with memset_io() so that no surprises pop up

I'd only like to make happy noises here to make sure you continue with this work - it does look promising. :-)

Thanks,

Ingo

#2 lore raw
Quoted 15 lines · Ingo Molnar
Quoted 3 lines · Alexey Dobriyan

QUESTION: is it possible to tell gcc "this function is semantically equivalent to memset(3) so make high level optimizations but call it when it is necessary"? I suspect the answer is "no" :-\

No idea ...

Quoted 6 lines

TODO:
CONFIG_FORTIFY_SOURCE is enabled by distros benchmarks
testing
more comments
check with memset_io() so that no surprises pop up

Quoted 2 lines

I'd only like to make happy noises here to make sure you continue with this work - it does look promising. :-)

Thanks, Ingo.

This is really the core of the problem: once memset() becomes something other than

	static inline void *memset(void *p, int c, size_t len)
	{
		return __builtin_memset(p, c, len);
	}

GCC starts pretending that it doesn't know what memset() is and all those advertised space savings go to hell.