11 ms·

A 100LOC C impl of memset, that is faster than glibc's

99 points by Q26124 5y ago

cryptonector 5y ago
> if (n == 0) > return s; That branch is not needed because memset() is UD if length is 0, but it's nice that it's safer.
- deleted 5y ago
  [deleted]
- Filligree 5y ago
  You wouldn't rather have an arguably very slighter faster memset, with the caveat that it might explode in your face?
teddyh 5y ago
> The implementation of memset in this repository is around 25% faster than the glibc implementation. This is the geometric mean for sizes 0..512.
jstanley 5y ago
I'm curious why the time is so much worse for sizes just slightly larger than 400, but then better again for sizes larger than this?
- MauranKilom 5y ago
  Could be hitting a critical cache stride. See also https://stackoverflow.com/questions/11413855/why-is-transposing-a-matrix-of-512x512-much-slower-than-transposing-a-matrix-of https://stackoverflow.com/questions/11413855/why-is-transpos...
Jyaif 5y ago
I think that Duff's device could be used on lines 65-86 ( https://github.com/nadavrot/memset_benchmark/blob/eac67b6205ad9e426c5c3d725289ac91c5b4efde/src/lib.c#L65 https://github.com/nadavrot/memset_benchmark/blob/eac67b6205... )
- brrrrrm 5y ago
  Is Duff’s device still relevant? Compilers can typically do such unroll logic for you these days.
nynyny7 5y ago
In all fairness it needs to be said that the libc's implementation has to consider portability to more "exotic" architectures. For example, not every CPU allows to make unaligned 32-bit or 64-bit writes, or it takes a huge penalty for such writes.
- gpderetta 5y ago
  glibc has hand crafted assembler implementations of memcpy (often specialized for specific size ranges) for many architectures.
- asdfasgasdgasdg 5y ago
  Does glibc not have feature detection and conditional compilation for cases like this? That is surprising to me.
  - rwmj 5y ago
    It does. Each subdirectory of sysdeps/ can contain specific implementations per platform, arch, etc. eg: the aarch64 assembler memset is: https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/aarch64/memset.S https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/aar... There's also the "ifunc" mechanism which can be used to make the choice at runtime, eg: https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/aarch64/multiarch/memset.c https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/aar...
- nynyny7 5y ago
  What do I mean by "not every CPU allows to make unaligned 32-bit or 64-bit writes"? Let's test the code (as of commit eac67b6) on a Raspberry Pi 400: pi@rasppi400:~/memset_benchmark $ uname -a Linux rasppi400 5.10.63-v8+ #1459 SMP PREEMPT Wed Oct 6 16:42:49 BST 2021 aarch64 GNU/Linux pi@rasppi400:~/memset_benchmark $ ./bench_memset size, alignment, offset, libc, local 0, 16, 0, 1237452, 834116, 1.483549, 1, 16, 0, 1612697, 945325, 1.705971, 2, 16, 0, 1779538, 945320, 1.882472, 3, 16, 0, 1557081, 945324, 1.647140, 4, 16, 0, 1779527, 889736, 2.000062, 5, 16, 0, 1557103, 1000940, 1.555641, 6, 16, 0, 1779551, 1000944, 1.777873, 7, 16, 0, 1557111, 1000945, 1.555641, 8, 16, 0, 1334654, 889723, 1.500078, Bus error pi@rasppi400:~/memset_benchmark $ gdb ./bench_memset [...] (gdb) run Starting program: /home/pi/memset_benchmark/bench_memset size, alignment, offset, libc, local 0, 16, 0, 1557105, 722928, 2.153887, 1, 16, 0, 1557103, 889797, 1.749953, 2, 16, 0, 1557107, 889849, 1.749855, 3, 16, 0, 1557108, 889759, 1.750033, 4, 16, 0, 1557117, 889789, 1.749985, 5, 16, 0, 1557110, 889745, 1.750063, 6, 16, 0, 1557116, 889754, 1.750052, 7, 16, 0, 1557110, 889758, 1.750038, 8, 16, 0, 1557109, 889803, 1.749948, Program received signal SIGBUS, Bus error. small_memset (n=<optimized out>, c=<optimized out>, s=0x29690) at /home/pi/memset_benchmark/src/lib.c:33 33 *((uint64_t *)last) = val8;
marcodiego 5y ago
Great! Now benchmark it with all compiler X architectures supported by glibc.
rasz 5y ago
memset is something JEDEC SDRAM standard should of implemented on a hardware level back in 1993. Why even bother writing to ram byte by byte when we could of had dedicated command to fill up to whole row (8-16kbit per chip, 8-32KB per DIMM) at a time with _single command_. Safe zero fill memory allocation would be free and standard. For background: https://faculty-web.msoe.edu/johnsontimoj/EE4980/files4980/memory_sdram_operation.pdf https://faculty-web.msoe.edu/johnsontimoj/EE4980/files4980/m... Since 1993 ram chips have integrated state machines receiving and interpreting higher level commands. They also have wide sense amplifier banks being loaded/stored all at once.
- mananaysiempre 5y ago
  Modern microcontrollers can have DMA units that you can program to, among other things, do a memset or even a memcpy when the memory bus happens to be idle, and they’ll interrupt you when they’re done. The design point is different (a microcontroller application can be limited by processor cycles but rarely by memory bus bandwidth), but I still wonder why PCs don’t have anything like that.
  - com2kid 5y ago
    Programming Microcontrollers was such an interesting and different experience, designing code to be asynchronous in regards to memory operations was a whole 'nother level of arranging code. Likewise for doing copies from external RAM to internal SRAM, it was slow enough compared to the 1 cycle latency accessing SRAM, and CPU cycles were precious enough, that code copying lots of memory from external memory was designed to stop execution and let other code run and resume once the copy was finished. We were able to get some serious speed out of the 96mhz CPU because we optimized everything around our memory bus.
  - drran 5y ago
    Just implement a driver for your memory controller and update all software to use syscall into kernel (about 10k total instructions per syscall), which will perform memset or memcpy, then measure performance improvement and tell it to us.
  - 5y ago
AreYouSirius 5y ago
What is not faster then GLIBC ? ??
cma 5y ago
Calls to memset outside of the benchmark may be of heterogenous sizes, which may heavily affect branch prediction since every branch relates to size. I'm not saying it would go either way, just a big flaw to consider with the benchmarking method where it is doing only repeated calls of the same size only. It is suprising the GCC version does an integer multiply, if I am reading right (several cycles, unless it is cheaper for uint32 * char).
- gpderetta 5y ago
  Also repeatedly zeroing the same memory can have different performance characteristics than zeroing different memory each time. Haven't checked what the benchmark does though.
- BeeOnRope 5y ago
  Yes, it's hard to take the benchmark results seriously in light of the failure to use anything other than a single size at a time.
  - stephencanon 5y ago
    There's a bunch of things that make benchmarking memset and similar functions really hard: Measuring the time _repeated_ small calls to memset usually doesn't make any sense, even when the lengths are heterogeneous; this results in an instruction stream that's almost all memset, but for small memsets you almost always have lots of "other stuff" mixed in in real use. This can lead you to a suboptimal implementation. You have to factor in what distribution of sizes actually occurs in a live system. I haven't looked at this for a decade or so, but the last time I checked the majority of system-wide time in memset (on macOS running diverse applications) was spent in length-4096 calls, and the next highest spike was (perversely) length-zero. A system implementation has to balance the whole system's needs; a memset for just your program can certainly do better. Dtrace or similar tooling is invaluable to gather this information. As with any benchmarking, the only way to actually know is to swap out the implementation and measure real app / system performance. All that said, Nadav's implementation looks pretty plausible. It's branchier than I would like, and doesn't take advantage of specialized instructions for large buffers, but for some input distributions that's a very reasonable tradeoff, and I don't doubt that it's competitive with system memsets.
jmull 5y ago
I’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?
- mananaysiempre 5y ago
  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 use the maximum memory access width (which you can’t do otherwise without SIMD instructions). I’m curious about what the referenced code compiles down to, actually, because not only could GCC be auto-vectorizing it, it could be replacing it with a REP STOSQ or indeed a call to memset.
  - ninkendo 5y ago
    Here's the code in godbolt: gcc: https://godbolt.org/z/6xG5dKjj9 https://godbolt.org/z/6xG5dKjj9 clang: https://godbolt.org/z/Mh9zozjvK 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.
    - mananaysiempre 5y ago
      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.
      - The_rationalist 5y ago
stephc_int13 5y ago
A 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 low-level, already optimized routine, used extensively in many stages of a game engine. I think that we should never assume that standard implementations are optimal, trust but verify.
- OskarS 5y ago
  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 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? [1]: https://github.com/gcc-mirror/gcc/blob/master/libgcc/memcpy.c https://github.com/gcc-mirror/gcc/blob/master/libgcc/memcpy....
  - saagarjha 5y ago
    > 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.
rwmj 5y ago
There 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/b31859402d1404ba0433ba2eb64f2047ae21677b/common/include/iszero.h#L48 https://gitlab.com/nbdkit/nbdkit/-/blob/b31859402d1404ba0433... static inline bool __attribute__((__nonnull__ (1))) is_zero (const char *buffer, size_t size) { size_t i; const size_t limit = size < 16 ? size : 16; for (i = 0; i < limit; ++i) if (buffer[i]) return false; if (size != limit) return ! memcmp (buffer, buffer + 16, size - 16); return true; } Example usage for sparsifying while copying disk images: https://gitlab.com/nbdkit/libnbd/-/blob/46fa6ecc7422e830f10d64b62c808abe6f8b49af/copy/multi-thread-copying.c#L389 https://gitlab.com/nbdkit/libnbd/-/blob/46fa6ecc7422e830f10d...
- TonyTrapp 5y ago
  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?
  - BeeOnRope 5y ago
    It is probably faster, yes (half the number of reads) – but the point of this truck is that you can re-use the (hopefully) vectorized memcmp on every platform with portable code rather than getting on the SIMD ISA treadmill yourself.
    - rwmj 5y ago
      The qemu implementation does indeed do it the hard way. It's a lot of code: https://gitlab.com/qemu-project/qemu/-/blob/master/util/bufferiszero.c https://gitlab.com/qemu-project/qemu/-/blob/master/util/buff...
nly 5y ago
I once maintained a project that had a custom memcpy implementation because they didn't want to link to libc. They assumed aligned writes were safe and the compiler optimized it incorrectly, resulting in memory corruption.
rurban 5y ago
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.
- errcorrectcode 5y ago
  Don't do this. Security. explicit_bzero() won't be optimized away.
  - rurban 5y ago
    I do it because nobody else implemented a secure memset. What they call secure is just avoiding that the compiler ignores it. A secure memset also cleans the caches with a memory barrier, so that meltdown cannot read it. explicit_bzero and it's numerous variants are not only insecure, but also slow. (byte wise!) Only safelibc has a secure memset_s. https://github.com/rurban/safeclib/blob/master/tests/perf_memset_s.c https://github.com/rurban/safeclib/blob/master/tests/perf_me...
jvanderbot 5y ago
Is this one of those times where you ignore 2% of the edge cases or legacy compatibilities and get a bunch of extra performance?
- deleted 5y ago
  [deleted]
dathinab 5y ago
But is it still faster if used in real world instead of benachmars? Given it's comparatively huge impl. it probably massively messes with the instruction cache of the rest of your program or am I overlooking something?
moonchild 5y ago
Also in assembly, up to 370% the speed of glibc - https://github.com/moon-chilled/fancy-memset https://github.com/moon-chilled/fancy-memset
- moonchild 5y ago
  (I have not yet publicized the implementation because I still need to check its performance in real-world applications. But quipping '370% in microbenchmarks with ideal branch-prediction and caching' seems appropriate considering that's no less than what the linked post does. That being said, preliminary instrumentation indicates the tradeoffs made were correct. My main point, however, is that for such low-level, essential subroutines, assembly remains the correct implementation language; c is still inadequate.)
brrrrrm 5y ago
The author, Nadav, has a lot of performance gems out there. Another good one explaining how to implement a fast matrix multiply: https://gist.github.com/nadavrot/5b35d44e8ba3dd718e595e40184d03f0 https://gist.github.com/nadavrot/5b35d44e8ba3dd718e595e40184...
bcrl 5y ago
The claim that the new implementation is faster fails to do the sort of benchmarks that systems developers must look into to justify this kind of change. A benchmark that runs the new memset implementation repeatedly in a loop ends up priming the branch predictor, trace cache and all sorts of things, often making it look better in testing that it does in the system as a whole. This kind of microbenchmark is semi-useful uring development, but is actually insufficient to justify the changes being adopted by a libc or kernel project. Cold caches and branch mispredicts are a major issue for memset/memcpy in a real world system, and other benchmarks need to be run - everything from SPEC to TPCC. I know as I have seen it with my own eyes. Using SSE memset looked promising in microbenchmarks but ended up having problems in a number of real world workloads due to the expensive floating point register save / restores in the kernel outweighing the benefits. On x86 the situation is in some ways worse. Quite a few x86 CPUs have had atrociously bad implementation of the string instructions. As a result, some high performance systems rolled their own memset/memcpy implementations. That results in feedback to the CPU designers failing to prioritize further optimize those string instructions. Thankfully, string instructions have kept getting better, so the general recommendation today is to just use the string instructions.

99 points by Q26124 5y ago

> if (n == 0) > return s; That branch is not needed because memset() is UD if length is 0, but it's nice that it's safer.

deleted 5y ago
[deleted]
Filligree 5y ago
You wouldn't rather have an arguably very slighter faster memset, with the caveat that it might explode in your face?

teddyh 5y ago

> The implementation of memset in this repository is around 25% faster than the glibc implementation. This is the geometric mean for sizes 0..512.

jstanley 5y ago

I'm curious why the time is so much worse for sizes just slightly larger than 400, but then better again for sizes larger than this?

MauranKilom 5y ago
Could be hitting a critical cache stride. See also https://stackoverflow.com/questions/11413855/why-is-transposing-a-matrix-of-512x512-much-slower-than-transposing-a-matrix-of https://stackoverflow.com/questions/11413855/why-is-transpos...

Jyaif 5y ago

I think that Duff's device could be used on lines 65-86 ( https://github.com/nadavrot/memset_benchmark/blob/eac67b6205ad9e426c5c3d725289ac91c5b4efde/src/lib.c#L65 https://github.com/nadavrot/memset_benchmark/blob/eac67b6205... )

brrrrrm 5y ago
Is Duff’s device still relevant? Compilers can typically do such unroll logic for you these days.

nynyny7 5y ago

In all fairness it needs to be said that the libc's implementation has to consider portability to more "exotic" architectures. For example, not every CPU allows to make unaligned 32-bit or 64-bit writes, or it takes a huge penalty for such writes.

gpderetta 5y ago
glibc has hand crafted assembler implementations of memcpy (often specialized for specific size ranges) for many architectures.
asdfasgasdgasdg 5y ago
Does glibc not have feature detection and conditional compilation for cases like this? That is surprising to me.
- rwmj 5y ago
  It does. Each subdirectory of sysdeps/ can contain specific implementations per platform, arch, etc. eg: the aarch64 assembler memset is: https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/aarch64/memset.S https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/aar... There's also the "ifunc" mechanism which can be used to make the choice at runtime, eg: https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/aarch64/multiarch/memset.c https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/aar...
nynyny7 5y ago
What do I mean by "not every CPU allows to make unaligned 32-bit or 64-bit writes"? Let's test the code (as of commit eac67b6) on a Raspberry Pi 400: pi@rasppi400:~/memset_benchmark $ uname -a Linux rasppi400 5.10.63-v8+ #1459 SMP PREEMPT Wed Oct 6 16:42:49 BST 2021 aarch64 GNU/Linux pi@rasppi400:~/memset_benchmark $ ./bench_memset size, alignment, offset, libc, local 0, 16, 0, 1237452, 834116, 1.483549, 1, 16, 0, 1612697, 945325, 1.705971, 2, 16, 0, 1779538, 945320, 1.882472, 3, 16, 0, 1557081, 945324, 1.647140, 4, 16, 0, 1779527, 889736, 2.000062, 5, 16, 0, 1557103, 1000940, 1.555641, 6, 16, 0, 1779551, 1000944, 1.777873, 7, 16, 0, 1557111, 1000945, 1.555641, 8, 16, 0, 1334654, 889723, 1.500078, Bus error pi@rasppi400:~/memset_benchmark $ gdb ./bench_memset [...] (gdb) run Starting program: /home/pi/memset_benchmark/bench_memset size, alignment, offset, libc, local 0, 16, 0, 1557105, 722928, 2.153887, 1, 16, 0, 1557103, 889797, 1.749953, 2, 16, 0, 1557107, 889849, 1.749855, 3, 16, 0, 1557108, 889759, 1.750033, 4, 16, 0, 1557117, 889789, 1.749985, 5, 16, 0, 1557110, 889745, 1.750063, 6, 16, 0, 1557116, 889754, 1.750052, 7, 16, 0, 1557110, 889758, 1.750038, 8, 16, 0, 1557109, 889803, 1.749948, Program received signal SIGBUS, Bus error. small_memset (n=<optimized out>, c=<optimized out>, s=0x29690) at /home/pi/memset_benchmark/src/lib.c:33 33 *((uint64_t *)last) = val8;

marcodiego 5y ago

Great! Now benchmark it with all compiler X architectures supported by glibc.

rasz 5y ago

memset is something JEDEC SDRAM standard should of implemented on a hardware level back in 1993. Why even bother writing to ram byte by byte when we could of had dedicated command to fill up to whole row (8-16kbit per chip, 8-32KB per DIMM) at a time with _single command_. Safe zero fill memory allocation would be free and standard. For background: https://faculty-web.msoe.edu/johnsontimoj/EE4980/files4980/memory_sdram_operation.pdf https://faculty-web.msoe.edu/johnsontimoj/EE4980/files4980/m... Since 1993 ram chips have integrated state machines receiving and interpreting higher level commands. They also have wide sense amplifier banks being loaded/stored all at once.

mananaysiempre 5y ago
Modern microcontrollers can have DMA units that you can program to, among other things, do a memset or even a memcpy when the memory bus happens to be idle, and they’ll interrupt you when they’re done. The design point is different (a microcontroller application can be limited by processor cycles but rarely by memory bus bandwidth), but I still wonder why PCs don’t have anything like that.
- com2kid 5y ago
  Programming Microcontrollers was such an interesting and different experience, designing code to be asynchronous in regards to memory operations was a whole 'nother level of arranging code. Likewise for doing copies from external RAM to internal SRAM, it was slow enough compared to the 1 cycle latency accessing SRAM, and CPU cycles were precious enough, that code copying lots of memory from external memory was designed to stop execution and let other code run and resume once the copy was finished. We were able to get some serious speed out of the 96mhz CPU because we optimized everything around our memory bus.
- drran 5y ago
  Just implement a driver for your memory controller and update all software to use syscall into kernel (about 10k total instructions per syscall), which will perform memset or memcpy, then measure performance improvement and tell it to us.
- 5y ago

AreYouSirius 5y ago

What is not faster then GLIBC ? ??

cma 5y ago

Calls to memset outside of the benchmark may be of heterogenous sizes, which may heavily affect branch prediction since every branch relates to size. I'm not saying it would go either way, just a big flaw to consider with the benchmarking method where it is doing only repeated calls of the same size only. It is suprising the GCC version does an integer multiply, if I am reading right (several cycles, unless it is cheaper for uint32 * char).

gpderetta 5y ago
Also repeatedly zeroing the same memory can have different performance characteristics than zeroing different memory each time. Haven't checked what the benchmark does though.
BeeOnRope 5y ago
Yes, it's hard to take the benchmark results seriously in light of the failure to use anything other than a single size at a time.
- stephencanon 5y ago
  There's a bunch of things that make benchmarking memset and similar functions really hard: Measuring the time _repeated_ small calls to memset usually doesn't make any sense, even when the lengths are heterogeneous; this results in an instruction stream that's almost all memset, but for small memsets you almost always have lots of "other stuff" mixed in in real use. This can lead you to a suboptimal implementation. You have to factor in what distribution of sizes actually occurs in a live system. I haven't looked at this for a decade or so, but the last time I checked the majority of system-wide time in memset (on macOS running diverse applications) was spent in length-4096 calls, and the next highest spike was (perversely) length-zero. A system implementation has to balance the whole system's needs; a memset for just your program can certainly do better. Dtrace or similar tooling is invaluable to gather this information. As with any benchmarking, the only way to actually know is to swap out the implementation and measure real app / system performance. All that said, Nadav's implementation looks pretty plausible. It's branchier than I would like, and doesn't take advantage of specialized instructions for large buffers, but for some input distributions that's a very reasonable tradeoff, and I don't doubt that it's competitive with system memsets.

jmull 5y ago

I’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?

mananaysiempre 5y ago
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 use the maximum memory access width (which you can’t do otherwise without SIMD instructions). I’m curious about what the referenced code compiles down to, actually, because not only could GCC be auto-vectorizing it, it could be replacing it with a REP STOSQ or indeed a call to memset.
- ninkendo 5y ago
  Here's the code in godbolt: gcc: https://godbolt.org/z/6xG5dKjj9 https://godbolt.org/z/6xG5dKjj9 clang: https://godbolt.org/z/Mh9zozjvK 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.
  - mananaysiempre 5y ago
    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.
    - The_rationalist 5y ago

stephc_int13 5y ago

A 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 low-level, already optimized routine, used extensively in many stages of a game engine. I think that we should never assume that standard implementations are optimal, trust but verify.

OskarS 5y ago
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 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? [1]: https://github.com/gcc-mirror/gcc/blob/master/libgcc/memcpy.c https://github.com/gcc-mirror/gcc/blob/master/libgcc/memcpy....
- saagarjha 5y ago
  > 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.

rwmj 5y ago

There 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/b31859402d1404ba0433ba2eb64f2047ae21677b/common/include/iszero.h#L48 https://gitlab.com/nbdkit/nbdkit/-/blob/b31859402d1404ba0433... static inline bool __attribute__((__nonnull__ (1))) is_zero (const char *buffer, size_t size) { size_t i; const size_t limit = size < 16 ? size : 16; for (i = 0; i < limit; ++i) if (buffer[i]) return false; if (size != limit) return ! memcmp (buffer, buffer + 16, size - 16); return true; } Example usage for sparsifying while copying disk images: https://gitlab.com/nbdkit/libnbd/-/blob/46fa6ecc7422e830f10d64b62c808abe6f8b49af/copy/multi-thread-copying.c#L389 https://gitlab.com/nbdkit/libnbd/-/blob/46fa6ecc7422e830f10d...

TonyTrapp 5y ago
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?
- BeeOnRope 5y ago
  It is probably faster, yes (half the number of reads) – but the point of this truck is that you can re-use the (hopefully) vectorized memcmp on every platform with portable code rather than getting on the SIMD ISA treadmill yourself.
  - rwmj 5y ago
    The qemu implementation does indeed do it the hard way. It's a lot of code: https://gitlab.com/qemu-project/qemu/-/blob/master/util/bufferiszero.c https://gitlab.com/qemu-project/qemu/-/blob/master/util/buff...

nly 5y ago

I once maintained a project that had a custom memcpy implementation because they didn't want to link to libc. They assumed aligned writes were safe and the compiler optimized it incorrectly, resulting in memory corruption.

rurban 5y ago

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.

errcorrectcode 5y ago
Don't do this. Security. explicit_bzero() won't be optimized away.
- rurban 5y ago
  I do it because nobody else implemented a secure memset. What they call secure is just avoiding that the compiler ignores it. A secure memset also cleans the caches with a memory barrier, so that meltdown cannot read it. explicit_bzero and it's numerous variants are not only insecure, but also slow. (byte wise!) Only safelibc has a secure memset_s. https://github.com/rurban/safeclib/blob/master/tests/perf_memset_s.c https://github.com/rurban/safeclib/blob/master/tests/perf_me...

jvanderbot 5y ago

Is this one of those times where you ignore 2% of the edge cases or legacy compatibilities and get a bunch of extra performance?

deleted 5y ago
[deleted]

dathinab 5y ago

But is it still faster if used in real world instead of benachmars? Given it's comparatively huge impl. it probably massively messes with the instruction cache of the rest of your program or am I overlooking something?

moonchild 5y ago

Also in assembly, up to 370% the speed of glibc - https://github.com/moon-chilled/fancy-memset https://github.com/moon-chilled/fancy-memset

moonchild 5y ago
(I have not yet publicized the implementation because I still need to check its performance in real-world applications. But quipping '370% in microbenchmarks with ideal branch-prediction and caching' seems appropriate considering that's no less than what the linked post does. That being said, preliminary instrumentation indicates the tradeoffs made were correct. My main point, however, is that for such low-level, essential subroutines, assembly remains the correct implementation language; c is still inadequate.)

brrrrrm 5y ago

The author, Nadav, has a lot of performance gems out there. Another good one explaining how to implement a fast matrix multiply: https://gist.github.com/nadavrot/5b35d44e8ba3dd718e595e40184d03f0 https://gist.github.com/nadavrot/5b35d44e8ba3dd718e595e40184...

bcrl 5y ago

The claim that the new implementation is faster fails to do the sort of benchmarks that systems developers must look into to justify this kind of change. A benchmark that runs the new memset implementation repeatedly in a loop ends up priming the branch predictor, trace cache and all sorts of things, often making it look better in testing that it does in the system as a whole. This kind of microbenchmark is semi-useful uring development, but is actually insufficient to justify the changes being adopted by a libc or kernel project. Cold caches and branch mispredicts are a major issue for memset/memcpy in a real world system, and other benchmarks need to be run - everything from SPEC to TPCC. I know as I have seen it with my own eyes. Using SSE memset looked promising in microbenchmarks but ended up having problems in a number of real world workloads due to the expensive floating point register save / restores in the kernel outweighing the benefits. On x86 the situation is in some ways worse. Quite a few x86 CPUs have had atrociously bad implementation of the string instructions. As a result, some high performance systems rolled their own memset/memcpy implementations. That results in feedback to the CPU designers failing to prioritize further optimize those string instructions. Thankfully, string instructions have kept getting better, so the general recommendation today is to just use the string instructions.