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

71–80 of 110 posts

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

#71

Post by monocasa »

Something1234 wrote: post #68
gpderetta wrote: post #30

Earlier quoted context omitted.

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?

I'm not sure about Linus's objections, but I've found that DMA accelerators for time sharing systems with general workloads haven't reaped benefits, as the overhead of multiplexing and synchronizing with them kills most of their benefits. At that point it's easier to blit memory yourself.

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

#72

Post by stephencanon »

jeffbee wrote: post #67
stephencanon wrote: post #62

Earlier quoted context omitted.

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

rep stos _is_ worth using, but that paper makes no mention of it (it does show that in their use rep cmps beat a more complicated memcmp implementation).

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

#74

Post by brettdeveffect »

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'd be curious about this in practice. Would it make sense to trade off probing in various places as 0s may be spatially correlated?

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

#75

Post by pm215 »

rwmj wrote: post #47
BeeOnRope wrote: post #41

Earlier quoted context omitted.

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

Interestingly, we used to have a special-case aarch64 version, but we dropped it because the C version was faster: https://gitlab.com/qemu-project/qemu/-/commit/2250d3a293d36e...

(Might or might not still be true on more modern aarch64 hardware...)

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

#77

Post by _zoltan_ »

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…

*should have

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

#78

Post by tkhattra »

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…

just make sure it's not "overly optimized" - https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95189 (in this case it was gcc's builtin memcmp that was broken, not glibc's) :)

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

#79

Post by _3u10 »

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…

use the popcnt instruction or the popcnt intrinsic function.

It counts how many bits are set to 1, you’re looking for 0.

You can also cast it into a uint64_t integer and do an equality test. There might be a way to use fused multiply add.

Also are you mmaping the file so you can just read it directly as a single buffer? You should be able to madvise to free pages after they’ve been checked.

PUSHFB can also be used. http://0x80.pl/articles/sse-popcount.html

Essentially you want to vectorize this tho memcmp may already be vectorized and do the cpu detection.

Edit: also… You should be able to load 15 x 256 bits and then test them. Try VPTEST https://www.intel.com/content/www/us/en/develop/documentatio...

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

#80

Post by [deleted] »

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…

[deleted]
Post reply on HN