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

91–100 of 110 posts

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

#91

Post by RustyRussell »

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…

You want this:

https://rusty.ozlabs.org/?p=560

Hope that helps!

(And yes, the CCAN memeqzero routine is the same as yours above in form).

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

#92

Post by emmelaich »

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…

C++ has an bool none() function for bitset. Along with any(), all(),...

I haven't looked at the implementation, but you could test it against yours.

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

#93

Post by LgWoodenBadger »

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…

Fwiw, and OT, but “could’ve” == “could have” and “should’ve” == “should have.” In no scenario would it be “could of” or “should of.”

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

#94

Post by Rendello »

LgWoodenBadger wrote: post #93
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…

Fwiw, and OT, but “could’ve” == “could have” and “should’ve” == “should have.” In no scenario would it be “could of” or “should of.”

This reminds me of an interesting problem. In oral speech, I frequently say "wouldn't've" and "couldn't've", but in text form both look completely asinine and aren't generally even recognized by spellcheckers.

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

#95

Post by akamoonknight »

Rendello wrote: post #94
LgWoodenBadger wrote: post #93

Earlier quoted context omitted.

Fwiw, and OT, but “could’ve” == “could have” and “should’ve” == “should have.” In no scenario would it be “could of” or “should of.”

This reminds me of an interesting problem. In oral speech, I frequently say "wouldn't've" and "couldn't've", but in text form both look completely asinine and aren't generally even recognized by spellcheckers.

Language is pretty fun. My favored multi-contraction is y'all'r'nt, similar in flavor of feeling natural/fun to say and use, but looking really ridiculous written out (not even sure I've even done it right...)

I feel like there's also something in this topic that relates to things like "going to" getting reduced to "gonna".

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

#96

Post by junon »

rwmj wrote: post #86
junon wrote: post #65

Earlier quoted context omitted.

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

Which functions in particular?

    strchr(str, 0) == NULL
    memchr(str, 0, len) == NULL

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

#97

Post by ckennelly »

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

https://research.google/pubs/pub50338.pdf goes into more depth on the mem* libc functions and principles for the implementations in llvm libc.

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

#100

Post by moonchild »

moonchild wrote: post #83

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

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

Post reply on HN