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

101–110 of 110 posts

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

#101

Post by sedatk »

josefx wrote: post #40
OskarS wrote: post #27

Earlier quoted context omitted.

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

> on x86, probably "rep movsb" or whatever) Sadly I don't have a link, but as far as I remember rep movsb was always hilariously slow. So memcpy implementations tried to optimize copies using half a page of vector instructions with size and alignment tests, which of course killed the CPUs instruction cache.

Yes, a compiler would at least add a combo of rep movsq + rep movsd + rep movsw to the mix before finishing the final remainder with rep movsb. Vector instructions might help tremendously too.

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

#102

Post by sedatk »

mananaysiempre wrote: post #25
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.

On a related note, Windows has a dedicated kernel thread solely for zeroing out freed memory, so, a new page allocation won't worry about zeroing the memory itself.

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

#103

Post by boibombeiro »

BeeOnRope wrote: post #42
yissp wrote: post #34

Earlier quoted context omitted.

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.

This, and loop unrolling, are two commons misconception about uarch optimization.

https://lemire.me/blog/2012/05/31/data-alignment-for-speed-m...

Memory alignment is innocuous (others than often compromise code legibility).

Loop unrolling, on the other hand, can slow down the code. Specially in small loops.

See Agner uarch PDF.

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

#104

Post by [deleted] »

boibombeiro wrote: post #103
BeeOnRope wrote: post #42

Earlier quoted context omitted.

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.

This, and loop unrolling, are two commons misconception about uarch optimization. https://lemire.me/blog/2012/05/31/data-alignment-for-speed-m... Memory alignment is innocuous (others than often compromise code legibility). Loop unrolling, on the other hand, can slow down the code. Specially in small loops. See Agner uarch PDF.

[deleted]

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

#105

Post by bjourne »

josefx wrote: post #40
OskarS wrote: post #27

Earlier quoted context omitted.

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

> on x86, probably "rep movsb" or whatever) Sadly I don't have a link, but as far as I remember rep movsb was always hilariously slow. So memcpy implementations tried to optimize copies using half a page of vector instructions with size and alignment tests, which of course killed the CPUs instruction cache.

Hilariously slow before Intel engineers decided to optimize the shit out of the construction. :)

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

#106

Post by junon »

klyrs wrote: post #98
junon wrote: post #96

Earlier quoted context omitted.

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

Those find the first zero -- not the number of contiguous zeros.

Oops, you're right. I was going to reach for `strcspn` but then realized it doesn't work for null bytes.

Huh. OP is right, there is no good function for this in the standard library.

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

#107

Post by bcrl »

The claim that the new implementation is faster fails to do the sort of benchmarks that systems developers must look into to justify this kind of change. A benchmark that runs the new memset implementation repeatedly in a loop ends up priming the branch predictor, trace cache and all sorts of things, often making it look better in testing that it does in the system as a whole. This kind of microbenchmark is semi-useful uring development, but is actually insufficient to justify the changes being adopted by a libc or kernel project. Cold caches and branch mispredicts are a major issue for memset/memcpy in a real world system, and other benchmarks need to be run - everything from SPEC to TPCC. I know as I have seen it with my own eyes. Using SSE memset looked promising in microbenchmarks but ended up having problems in a number of real world workloads due to the expensive floating point register save / restores in the kernel outweighing the benefits.

On x86 the situation is in some ways worse. Quite a few x86 CPUs have had atrociously bad implementation of the string instructions. As a result, some high performance systems rolled their own memset/memcpy implementations. That results in feedback to the CPU designers failing to prioritize further optimize those string instructions. Thankfully, string instructions have kept getting better, so the general recommendation today is to just use the string instructions.

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

#108

Post by The_rationalist »

mananaysiempre wrote: post #37
ninkendo wrote: post #35

Earlier quoted context omitted.

Here's the code in godbolt: gcc: https://godbolt.org/z/6xG5dKjj9 clang: https://godbolt.org/z/Mh9zozjvK I'm no asm expert, but it doesn't look like a lot of vector instructions in the gcc compilation of this, while the clang compilation seems to have more calls with the 128-bit xmm registers (at least on x86_64.) You can also just see visibly how many more instructions the gcc version outputs.

Thank you! Indeed GCC does not use SIMD here unless you set -O3 (... I seem to remember this enables some vectorization?) or allow it to use AVX with -mavx or -march=x86-64-v3. For some reason I’m unable to get it to use plain SSE (always available on x86-64) with any -mtune setting or even with -march=x86-64-v2.

https://www.phoronix.com/scan.php?page=news_item&px=GCC-12-A...

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

#109

Post by rurban »

errcorrectcode wrote: post #38
rurban wrote: post #31

I have a memset that's not only 10x faster than glibc, but also secure. The trick is to bypass the generic asm, and let the compiler optimize it, esp. with constant sizes and known alignments. Esp. with clang.

Don't do this. Security. explicit_bzero() won't be optimized away.

I do it because nobody else implemented a secure memset. What they call secure is just avoiding that the compiler ignores it. A secure memset also cleans the caches with a memory barrier, so that meltdown cannot read it.

explicit_bzero and it's numerous variants are not only insecure, but also slow. (byte wise!)

Only safelibc has a secure memset_s. https://github.com/rurban/safeclib/blob/master/tests/perf_me...

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

#110

Post by renox »

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…

Interesting but you must also take care of the CPU caches..
Post reply on HN