I have a memset that's not only 10x faster than glibc, but also secure. The trick is to bypass the generic asm, and let the compiler optimize it, esp. with constant sizes and known alignments. Esp. with clang.
A 100LOC C impl of memset, that is faster than glibc's
31–40 of 110 posts
Re: A 100LOC C impl of memset, that is faster than glibc's
#32A long time ago, as I was working with the Nintendo SDK for the DS console I wondered if the provided memcpy implementation was optimal. Turned out it was quite slow. I replaced it with an Intel hand optimized version made for the StrongARM, and replaced the prefetch opcode by a simple load because this opcode was not supported by the arch of the CPU of this console. 50% faster, this is quite significant for such a l…
Modern compilers have quite a deep understanding of memcpy, and they will recognize the pattern and put in optimal assembly (on x86, probably "rep movsb" or whatever), even if you don't literally call memcpy. This is why the GCC implmentation of memcpy is, like, trivial: [1]. The compiler will recognize that this is a memcpy and sub the better implementation. I wonder though: it seems to me that memory bandwidth shou…
> on x86, probably "rep movsb" or whatever
Only on recent x86, and with a long list of caveats. Look up discussion about erms online.
> I wonder though: it seems to me that memory bandwidth should far and away be the limiting factor for a memcpy, so I would think even a straight-forward translation of the "trivial" implementation wouldn't be that far off from an "optimal" one. I guess memory prefetching would make a difference, but would minimizing the number of loads/stores (or unrolling the loop) really matter that much?
Memory bandwidth is often the limiting factor, but not always. But your simple byte-by-byte loop is not going to get anywhere near saturating that; you'll need to unroll and use vector instructions, which might dispatch slower but copy several orders of magnitude more data.
Re: A 100LOC C impl of memset, that is faster than glibc's
#33There is an interesting related problem - how do you efficiently test if a buffer contains only zeroes? We use this for automatically sparsifying disk images. There's no standard C function for this. My colleague came up with the following nice trick. It reuses the (presumably already maximally optimized) memcmp function from libc: https://gitlab.com/nbdkit/nbdkit/-/blob/b31859402d1404ba0433... static inline bool __a…
Assuming that vector instructions are available, shouldn't it be much faster to actually compare the buffer contents against a vector register initialized to all-zeros rather than comparing against some other memory? Or would memcmp automatically optimize that away because of the precondition that the first 16 bytes are already known to be 0?
Re: A 100LOC C impl of memset, that is faster than glibc's
#34There is an interesting related problem - how do you efficiently test if a buffer contains only zeroes? We use this for automatically sparsifying disk images. There's no standard C function for this. My colleague came up with the following nice trick. It reuses the (presumably already maximally optimized) memcmp function from libc: https://gitlab.com/nbdkit/nbdkit/-/blob/b31859402d1404ba0433... static inline bool __a…
Is the choice of 16 as the "limit" value based on benchmarking? As opposed to just doing something like "!buffer[0] && !memcmp(buffer, buffer + 1, size - 1)" which uses the same principle.
Re: A 100LOC C impl of memset, that is faster than glibc's
#35I’m wonder how well this handles unaligned memory? That used to be stable stakes for this kind of thing, but maybe it doesn’t matter much anymore?
On the x86, in the P4 times the best performing bulk operations essentially required using SIMD, and that SIMD hated you unless you aligned your memory accesses. The result was horrible bloated code to handle leading and trailing data and thus also a need to split off the implementations for small sizes. The unaligned access penalty is much lower now, and REP-prefixed operations have microcoded implementations that u…
Here's the code in godbolt:
gcc: https://godbolt.org/z/6xG5dKjj9
clang: https://godbolt.org/z/Mh9zozjvK
I'm no asm expert, but it doesn't look like a lot of vector instructions in the gcc compilation of this, while the clang compilation seems to have more calls with the 128-bit xmm registers (at least on x86_64.) You can also just see visibly how many more instructions the gcc version outputs.
Re: A 100LOC C impl of memset, that is faster than glibc's
#36A long time ago, as I was working with the Nintendo SDK for the DS console I wondered if the provided memcpy implementation was optimal. Turned out it was quite slow. I replaced it with an Intel hand optimized version made for the StrongARM, and replaced the prefetch opcode by a simple load because this opcode was not supported by the arch of the CPU of this console. 50% faster, this is quite significant for such a l…
Modern compilers have quite a deep understanding of memcpy, and they will recognize the pattern and put in optimal assembly (on x86, probably "rep movsb" or whatever), even if you don't literally call memcpy. This is why the GCC implmentation of memcpy is, like, trivial: [1]. The compiler will recognize that this is a memcpy and sub the better implementation. I wonder though: it seems to me that memory bandwidth shou…
From my experience, good prefetching and pre-alignment changes a lot of things/
Compiler optimized memcpy are good for small copies that will be inlined, but copying big chunks is an other story and I've seen non-marginal differences depending on implementation.
The most difficult problem is that each implementation is usually tuned for a specific CPU and might be sub-optimal with a different brand or revision...
Re: A 100LOC C impl of memset, that is faster than glibc's
#37Earlier quoted context omitted.
On the x86, in the P4 times the best performing bulk operations essentially required using SIMD, and that SIMD hated you unless you aligned your memory accesses. The result was horrible bloated code to handle leading and trailing data and thus also a need to split off the implementations for small sizes. The unaligned access penalty is much lower now, and REP-prefixed operations have microcoded implementations that u…
Here's the code in godbolt: gcc: https://godbolt.org/z/6xG5dKjj9 clang: https://godbolt.org/z/Mh9zozjvK I'm no asm expert, but it doesn't look like a lot of vector instructions in the gcc compilation of this, while the clang compilation seems to have more calls with the 128-bit xmm registers (at least on x86_64.) You can also just see visibly how many more instructions the gcc version outputs.
Thank you! Indeed GCC does not use SIMD here unless you set -O3 (... I seem to remember this enables some vectorization?) or allow it to use AVX with -mavx or -march=x86-64-v3. For some reason I’m unable to get it to use plain SSE (always available on x86-64) with any -mtune setting or even with -march=x86-64-v2.
Re: A 100LOC C impl of memset, that is faster than glibc's
#38I have a memset that's not only 10x faster than glibc, but also secure. The trick is to bypass the generic asm, and let the compiler optimize it, esp. with constant sizes and known alignments. Esp. with clang.
Don't do this. Security. explicit_bzero() won't be optimized away.
Re: A 100LOC C impl of memset, that is faster than glibc's
#39A long time ago, as I was working with the Nintendo SDK for the DS console I wondered if the provided memcpy implementation was optimal. Turned out it was quite slow. I replaced it with an Intel hand optimized version made for the StrongARM, and replaced the prefetch opcode by a simple load because this opcode was not supported by the arch of the CPU of this console. 50% faster, this is quite significant for such a l…
Modern compilers have quite a deep understanding of memcpy, and they will recognize the pattern and put in optimal assembly (on x86, probably "rep movsb" or whatever), even if you don't literally call memcpy. This is why the GCC implmentation of memcpy is, like, trivial: [1]. The compiler will recognize that this is a memcpy and sub the better implementation. I wonder though: it seems to me that memory bandwidth shou…
If you think that a specific routine or algorithm is memory bound, you should always do a quick benchmark to check this assumption.
In practice everything is memory bound because of course the CPU is faster than memory, but you'd be surprised by how difficult it can be to reach the full CPU capacity.
"Memory bound" or "Network bound" are way too frequently used as poor excuses by lazy coders.
Re: A 100LOC C impl of memset, that is faster than glibc's
#40A long time ago, as I was working with the Nintendo SDK for the DS console I wondered if the provided memcpy implementation was optimal. Turned out it was quite slow. I replaced it with an Intel hand optimized version made for the StrongARM, and replaced the prefetch opcode by a simple load because this opcode was not supported by the arch of the CPU of this console. 50% faster, this is quite significant for such a l…
Modern compilers have quite a deep understanding of memcpy, and they will recognize the pattern and put in optimal assembly (on x86, probably "rep movsb" or whatever), even if you don't literally call memcpy. This is why the GCC implmentation of memcpy is, like, trivial: [1]. The compiler will recognize that this is a memcpy and sub the better implementation. I wonder though: it seems to me that memory bandwidth shou…
> on x86, probably "rep movsb" or whatever)
Sadly I don't have a link, but as far as I remember rep movsb was always hilariously slow. So memcpy implementations tried to optimize copies using half a page of vector instructions with size and alignment tests, which of course killed the CPUs instruction cache.