Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

github.com

Post reply on HN
Print view View original

41–50 of 110 posts

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

#41

Post by BeeOnRope »

TonyTrapp wrote: post #33
rwmj wrote: post #23

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/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?

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.

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

#42

Post by BeeOnRope »

yissp wrote: post #34
rwmj wrote: post #23

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/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.

Not the OP, but 16 has the benefit of keeping both pointers in the comparison 16-byte aligned if the buffer was initially aligned.

This would eliminate split loads and provide a decent speedup.

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

#43

Post by BeeOnRope »

cma wrote: post #15

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 che…

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.

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

#44

Post by nynyny7 »

rwmj wrote: post #29
nynyny7 wrote: post #26

Earlier quoted context omitted.

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, 16…

Is that 32 bit ARM code on 64 bit kernel? I thought ARM (since v6) allows unaligned access, although it might have to be emulated through the kernel which is going to be super-slow. On SPARC you have no choice, align or die!

Yes it is 32 bit code on a 64 bit kernel. I didn't debug what the instruction is that ultimately causes the bus error.

  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 $
  pi@rasppi400:~/memset_benchmark $ file ./bench_memset
  ./bench_memset: ELF 32-bit LSB executable, ARM, EABI5 version 1 (SYSV), dynamically linked, interpreter /lib/ld-linux-armhf.so.3, for GNU/Linux 3.2.0, BuildID[sha1]=ebeb69b6cb9664d78c1256a2c862f3d28f11e15e, with debug_info, not stripped

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

#45

Post by dolmen »

rwmj wrote: post #23

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/b31859402d1404ba0433... static inline bool __a…

Sources: https://gitlab.com/nbdkit/libnbd/-/blob/46fa6ecc7422e830f10d...

https://listman.redhat.com/archives/libguestfs/2017-April/ms...

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

#46

Post by dolmen »

nynyny7 wrote: post #5

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.

In all fairness we need the fastest memset on every architecture. Whatever the cost of maintenance.

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

#47

Post by rwmj »

BeeOnRope wrote: post #41
TonyTrapp wrote: post #33

Earlier quoted context omitted.

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?

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.

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/buff...

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

#48

Post by omegalulw »

rwmj wrote: post #23

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/b31859402d1404ba0433... static inline bool __a…

Clever, I love it. Maybe I'm just dumb, but it took me a lil bit to convince myself it's correct.

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

#49

Post by knome »

FpUser wrote: post #19
gpderetta wrote: post #9

Earlier quoted context omitted.

What's the use of filling your ram with zeros when the data needs to be on L1, L2 or L3? Unless you are memsetting hundreds of MBs of memory, memset/memcpy in practice need to be handled by the cpu or something very close to it. Zen has CLZERO which can clear a cacheline in one go, but not sure how good it is.

>"Unless you are memsetting hundreds of MBs of memory" Not hundreds but in one of my apps I do have 10th MB of continuous cache that has to be zeroed before use / reuse.

I wonder if someone was zeroing enough memory, where the memory is a private anonymous mapping, they might use madvise() with MADV_DONTNEED, which in linux will effectively zero the pages.

It returns the memory to the OS, and will pagefault on later accesses remapping them as zero-filled. It works in pages. Sizes smaller than a page result in whatever else is in the same page getting nuked.

If you don't immediately reuse the whole cache, it might spread out the zeroing/remapping over time, rather than in a single large go. Imagine some testing would be in order to see if a syscall + mapping changes ( require reloading with TLB for the process ? ) would be smaller than a straight run of writing zeros at some point.

IIRC, the zeroing is not something you can expect from non-linux madvise implementations.

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

#50

Post by gavinray »

stephc_int13 wrote: post #18

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 l…

This is brilliant and really interesting/neat, thanks for posting.
Post reply on HN