Date: Thu, 9 Feb 2023 22:34:38 +0100 From: Mateusz Guzik <mjguzik@gmail.com> To: David Chisnall <theraven@freebsd.org> Cc: freebsd-hackers <freebsd-hackers@freebsd.org> Subject: Re: CFT: snmalloc as libc malloc Message-ID: <CAGudoHEvtNFs0%2BVoog4YcKoTQ026fj0MJdh2i5ZguzvGq1nWcQ@mail.gmail.com> In-Reply-To: <CAGudoHFeFm1K%2BJSBXaxt2SNTv-tGFgT0onyErOCmBdVjmHaxUg@mail.gmail.com> References: <2f3dcda0-5135-290a-2dff-683b2e9fe271@FreeBSD.org> <CAGudoHFYMLk6EDrSxLiWFNBoYyTKXfHLAUhZC%2BRF4eUE-rip8Q@mail.gmail.com> <E140A3A2-5C4A-4458-B365-AD693AB853E8@FreeBSD.org> <CAGudoHFeFm1K%2BJSBXaxt2SNTv-tGFgT0onyErOCmBdVjmHaxUg@mail.gmail.com>
next in thread | previous in thread | raw e-mail | index | archive | help
The memcpy debacle aside, I can confirm that single-threaded the new malloc does appear faster in naive tests from will-it-scale: $ cpuset -l 10,80,82 -- ./malloc2_threads -n -t 2 testcase:malloc/free of 1kB before: min:97812514 max:97849385 total:195661899 min:97819901 max:97857131 total:195677032 min:97789741 max:97833562 total:195623303 after: min:115613762 max:124855002 total:240468764 min:115636562 max:124807148 total:240443710 min:115778776 max:124784220 total:240562996 that said, if anyone is to performed a serious test, the stock memcpy needs to be used to rule it out as a factor. The one shipped with snmalloc will happen to be faster for certain sizes and that may skew whatever evaluation -- that speed increase (and in fact higher) is achievable without snmalloc. On 2/9/23, Mateusz Guzik <mjguzik@gmail.com> wrote: > On 2/9/23, David Chisnall <theraven@freebsd.org> wrote: >> On 9 Feb 2023, at 19:15, Mateusz Guzik <mjguzik@gmail.com> wrote: >>> >>> it fails to build for me: >>> >>> /usr/src/lib/libc/stdlib/snmalloc/malloc.cc:35:10: fatal error: >>> 'override/jemalloc_compat.cc' file not found >>> #include "override/jemalloc_compat.cc" >>> ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~ >>> 1 error generated. >>> --- malloc.o --- >>> *** [malloc.o] Error code 1 >>> >>> make[4]: stopped in /usr/src/lib/libc >>> /usr/src/lib/libc/stdlib/snmalloc/memcpy.cc:25:10: fatal error: >>> 'global/memcpy.h' file not found >>> #include <global/memcpy.h> >>> ^~~~~~~~~~~~~~~~~ >>> 1 error generated. >>> --- memcpy.o --- >>> *** [memcpy.o] Error code 1 >> >> This looks as if you haven=E2=80=99t got the submodule? Is there anythi= ng in >> contrib/snmalloc? >> > > indeed, a pilot error > >>> anyway, I wanted to say I find the memcpy thing incredibly suspicious. >>> I found one article in >>> https://github.com/microsoft/snmalloc/blob/main/docs/security/GuardedMe= mcpy.md >>> which benches it and that made it even more suspicious. How did the >>> benched memcpy look like inside? >> >> Perhaps you could share what you are suspicious about? I don=E2=80=99t = really >> know >> how to respond to something so vague. The document you linked to has th= e >> benchmark that we used (though the graphs in it appear to be based on an >> older version of the memcpy). The PR that added PowerPC tuning has some >> additional graphs of measurements. >> >> If you compile the memcpy file, you can see the assembly. The C++ >> provides >> a set of building blocks for producing efficient memcpy implementations. > > First and foremost, perhaps I should clear up that I have no opinion > on snmalloc or it replacing jemalloc. I'm here only about the memcpy > thing. > > Inspecting assembly is what I intended to do, but got the compilation > problem. > > So, as someone who worked on memcpy previously, I note the variant > currently implemented in libc is pessimal for sizes > 16 bytes because > it does not use SIMD. I do have plans to rectify that, but ENOTIME. > > I also note CPUs are incredibly picky when it comes to starting point > of the routine. The officialy recommended alignment of 16 bytes is > basically a tradeoff between total binary size and performance. Should > you move the routine at different 16 bytes intervals you will easily > find big variation in performance, depending on how big of an > alignment you ended up with. > > I tried to compile the benchmark but got bested by c++. I don't know > the lang and I don't want to fight it. > > $ pwd > /usr/src/contrib/snmalloc/src > $ c++ -I. test/perf/memcpy/memcpy.cc > [snip] > ./snmalloc/global/../backend/../backend_helpers/../mem/../ds_core/bits.h:= 57:26: > error: no template named 'is_integral_v' in namespace 'std'; did you > mean 'is_integral'? > static_assert(std::is_integral_v<T>, "Type must be integral"); > ~~~~~^~~~~~~~~~~~~ > is_integral > > and tons of other errors. I did buildworld + installworld. > > I'm trying to say that if you end up with different funcs depending on > bounds checking and you only align them to 16 bytes, the benchmark is > most likely inaccurate if only for this reason. > >> The fastest on x86 is roughly: >> >> - A jump table of power for small sizes that do power-of-two-sized smal= l >> copies (double-word, word, half-word, and byte) to perform the copy. > > Last I checked this was not true. The last slow thing to do was to > branch on few sizes and handle them with overlapping stores. Roughly > what memcpy in libc is doing now. > > Jump table aside, you got all sizes "spelled out", that is just > avoidable impact on icache. While overlapping stores do come with some > penalty, it is cheaper than the above combined. > > I don't have numbers nor bench code handy, but if you insist on > contesting the above I'll be glad to provide them. > >> - A vectorised copy for medium-sized copies using a loop of SSE copies. > > Depends on what you mean by medium and which simd instructions, but > yes, they should be used here. > >> - rep movsb for large copies. > > There are still old cpus here and there which don't support ERMS. They > are very negatively impacted the above and should roll with rep stosq > instead. > > I see the code takes some care to align the target buffer. That's > good, but not necessary on CPUs with FSRM. > > All that said, I have hard time believing the impact of bounds > checking on short copies is around 20% or so. The code to do it looks > super slow (not that I know to do better). > > People like to claim short sizes are inlined by the compiler, but > that's only true if the size is known at compilation time, which it > often is not. Then they claim they are rare. > > To illustrate why that's bogus, here is clang 15 compiling vfs_cache.c: > value ------------- Distribution ------------- count > -1 | 0 > 0 |@ 19758 > 1 |@@@@@@@@ 218420 > 2 |@@ 67670 > 4 |@@@@ 103914 > 8 |@@@@@@@@@@@ 301157 > 16 |@@@@@@@@@@ 293812 > 32 |@@ 57954 > 64 |@ 23818 > 128 | 13344 > 256 |@ 18507 > 512 | 6342 > 1024 | 1710 > 2048 | 627 > 4096 | 398 > 8192 | 34 > 16384 | 10 > 32768 | 6 > 65536 | 7 > 131072 | 4 > 262144 | 1 > 524288 | 1 > 1048576 | 0 > > obtained with this bad boy: > dtrace -n 'pid$target::memcpy:entry { @ =3D quantize(arg2); }' -c "cc > -target x86_64-unknown-freebsd14.0 > --sysroot=3D/usr/obj/usr/src/amd64.amd64/tmp > -B/usr/obj/usr/src/amd64.amd64/tmp/usr/bin -c -O2 -pipe > -fno-strict-aliasing -g -nostdinc -I. -I/usr/src/sys > -I/usr/src/sys/contrib/ck/include -I/usr/src/sys/contrib/libfdt > -D_KERNEL -DHAVE_KERNEL_OPTION_HEADERS -include opt_global.h > -fno-common -fno-omit-frame-pointer -mno-omit-leaf-frame-pointer > -MD -MF.depend.vfs_cache.o -MTvfs_cache.o > -fdebug-prefix-map=3D./machine=3D/usr/src/sys/amd64/include > -fdebug-prefix-map=3D./x86=3D/usr/src/sys/x86/include > -fdebug-prefix-map=3D./i386=3D/usr/src/sys/i386/include -mcmodel=3Dkernel > -mno-red-zone -mno-mmx -mno-sse -msoft-float > -fno-asynchronous-unwind-tables -ffreestanding -fwrapv > -fstack-protector -Wall -Wnested-externs -Wstrict-prototypes > -Wmissing-prototypes -Wpointer-arith -Wcast-qual -Wundef > -Wno-pointer-sign -D__printf__=3D__freebsd_kprintf__ > -Wmissing-include-dirs -fdiagnostics-show-option -Wno-unknown-pragmas > -Wno-error=3Dtautological-compare -Wno-error=3Dempty-body > -Wno-error=3Dparentheses-equality -Wno-error=3Dunused-function > -Wno-error=3Dpointer-sign -Wno-error=3Dshift-negative-value > -Wno-address-of-packed-member -Wno-error=3Darray-parameter > -Wno-error=3Ddeprecated-non-prototype -Wno-error=3Dstrict-prototypes > -Wno-error=3Dunused-but-set-variable -Wno-format-zero-length -mno-aes > -mno-avx -std=3Diso9899:1999 -Werror /usr/src/sys/kern/vfs_cache.c" > > tl;dr if this goes in, the fate of memcpy thing will need to be > handled separtely > -- > Mateusz Guzik <mjguzik gmail.com> > --=20 Mateusz Guzik <mjguzik gmail.com>
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?CAGudoHEvtNFs0%2BVoog4YcKoTQ026fj0MJdh2i5ZguzvGq1nWcQ>