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

21–30 of 110 posts

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

#21

Post by kwertyoowiyop »

gpderetta wrote: post #14
vlovich123 wrote: post #13

Earlier quoted context omitted.

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…

Interesting that you mention linux, because Linus has very very strong opinions about this :)

What are they?

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

#22

Post by rasz »

gpderetta wrote: post #9
rasz wrote: post #8

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/m... Since…

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.

Such ram capability would result in implementing hybrid compressed caches. Why waste whole cache line for storing zeroes when you can have dedicated compressed representation.

On a similar note part of ATI 2000 https://en.wikipedia.org/wiki/HyperZ was fast Z clear, today a norm on every GPU.

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

#23

Post by rwmj »

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 __attribute__((__nonnull__ (1)))
  is_zero (const char *buffer, size_t size)
  {
    size_t i;
    const size_t limit = size
Example usage for sparsifying while copying disk images: https://gitlab.com/nbdkit/libnbd/-/blob/46fa6ecc7422e830f10d...

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

#25

Post by mananaysiempre »

rasz wrote: post #8

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/m... Since…

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.

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

#26

Post by nynyny7 »

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, 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=, c=, s=0x29690)
      at /home/pi/memset_benchmark/src/lib.c:33
  33          *((uint64_t *)last) = val8;

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

#27

Post by OskarS »

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…

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

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

#28

Post by mananaysiempre »

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?

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.

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

#29

Post by rwmj »

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…

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!

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

#30

Post by gpderetta »

xvmt wrote: post #20
gpderetta wrote: post #14

Earlier quoted context omitted.

Interesting that you mention linux, because Linus has very very strong opinions about this :)

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.
Post reply on HN