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

61–70 of 110 posts

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

#61

Post by dahfizz »

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…

I wonder if it would be meaningfully faster if you checked the first 16 bytes as uint64_t or uint128_t instead of byte by byte. It would save you 14 or 15 comparisons per function call.

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

#62

Post by stephencanon »

BeeOnRope wrote: post #43
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.

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.

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

#63

Post by kevin_b_er »

jmull wrote: post #16

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?

Probably poorly. It is a violation to cast an unaligned pointer to an aligned type that the base pointer is not aligned for. And the code looks like it does just that right here: https://github.com/nadavrot/memset_benchmark/blob/main/src/l...

This is undefined behavior under C99 §6.3.2.3 Paragraph 7. "If the resulting pointer is not correctly aligned for the pointed-to type, the behavior is undefined."

The musl code referenced has handling for this.

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

#64

Post by nynyny7 »

nynyny7 wrote: post #44
rwmj wrote: post #29

Earlier quoted context omitted.

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), dynami…

PS: It's STRD, which as far as I understand the Arm Architecture Reference Manual always requires word alignment.

  Program received signal SIGBUS, Bus error.
  small_memset (n=, c=, s=0x29690)
      at /home/pi/memset_benchmark/src/lib.c:33
  33          *((uint64_t *)last) = val8;
  1: x/i $pc
  => 0x11c8c : strd    r0, [r7, #-8]
  (gdb) info registers
  r0             0x0                 0
  r1             0x0                 0
  r2             0x0                 0
  r3             0x1475              5237
  r4             0x5f5e100           100000000
  r5             0x11674             71284
  r6             0x29690             169616
  r7             0x29699             169625

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

#65

Post by junon »

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…

There are a number of standard functions that can achieve this, namely in string.h. Performance is a question of course.

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

#66

Post by dividuum »

nynyny7 wrote: post #26
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.

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…

Can't look right now, but you might not have benchmarked against libc, but against an optimized version included in Raspbian (https://github.com/simonjhall/copies-and-fills). I'm not sure if that's still active in the latest Raspberry Pi OS releases.

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

#67

Post by jeffbee »

stephencanon wrote: post #62
BeeOnRope wrote: post #43

Earlier quoted context omitted.

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.

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. Y…

As far as real-world performance goes, this paper claims (and shows) that code size is the relevant aspect of mem* functions, and concludes that `rep stosb` is optimal in practice, even though it obviously loses to exotic hand-rolled memset and memcmp in microbenchmarks.

https://storage.googleapis.com/pub-tools-public-publication-...

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

#68

Post by Something1234 »

gpderetta wrote: post #30
xvmt wrote: post #20

Earlier quoted context omitted.

What is his opinion about this?

He strongly believes that something like rep stos/rep mov is the right interface for memset/memcpy and off-core accelerators (like DMA) are misguided.

His reasoning or rant for this?

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

#69

Post by secondcoming »

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…

I have the same issue. I want to use SIMD to do ANDs between large buffers and also be able to detect if a buffer is empty (all zeroes) after an AND. It doesn't seem possible to do this without iterating over the entire buffer again because vpand() doesn't affect the eflags register.

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

#70

Post by monocasa »

vlovich123 wrote: post #13
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.

This would be a CPU command that works with the RAM controller rather than something you control yourself (kernels to my knowledge don’t talk directly to the controller beyond maybe some basic power management, if that). There is a definite need to do hundreds of MB - the Linux kernel has a background thread that does nothing but zero out pages. What do you think happens to the GBs of RAM freed by closing Chrome? Onc…

If you find yourself doing this a lot, there's write combining memory to coalesce writes to be more friendly to the RAM controller.

Additionally, CLZERO ends up doing very similar work since the resulting cache flush os seen by the RAM controller as a block write.

Post reply on HN