9 ms·
The Hunt for the Fastest Zero
- PeterHacker123 7y agoThumbs up, but at least on macOS both is equally fast :-(
- BeeOnRope 7y agoProbably you are using clang, right? As mentioned, clang does the idiom recognition even at -O2. Try at -O1. If it's still fast at -O1, I guess the libc++ implementation is different (AFAIK clang uses libstdc++ on Linux but libc++ on OSX).
- BeeOnRope 7y agoAuthor here, happy for any feedback or questions.
- mkbosmans 7y agoYour links in the article to the HN discussion point to a different submission, not this one.
- BeeOnRope 7y agoThanks, it got submitted twice it seems: the links are to the original submission. I'll update them to this one.
- gpderetta 7y agoJust wanted to say thay I love reading your articles.
- BeeOnRope 7y agoThanks! I love writing them.
- deleted 7y ago[deleted]
- wruza 7y agojmp memset Classic plot twist.
- alecco 7y agoDiscussion on cpp subreddit https://www.reddit.com/r/cpp/comments/erialk/the_hunt_for_the_fastest_zero/ https://www.reddit.com/r/cpp/comments/erialk/the_hunt_for_th...
- marcoperaza 7y agoIf you're routinely zeroing this much memory and the performance matters, you might benefit from idle-zeroing it. That is, when you need to zero the massive block, just switch to a different block that has already been zeroed or partly-zeroed in the background. Whatever hasn't already been zeroed, finish synchronously. The background thread doing the zeroing would be scheduled with the lowest priority, so that it only runs when the system otherwise has nothing to do. At first, I thought you might just want to get fresh pages from the kernel (which are always zeroed), but this answer convinced me that might not actually be faster because of the overhead from syscalls and fiddling with virtual memory https://stackoverflow.com/questions/49896578/fastest-way-to-zero-pages-in-linux https://stackoverflow.com/questions/49896578/fastest-way-to-... . And Linux doesn't idle-zero or pre-zero pages (though I believe there's a switch to enable pre-zeroing for purposes of security hardening), so you're probably gonna end up with the OS doing a synchronous[1] zeroing anyway. [1] Synchronous from when you actually first write to each page. My understanding is that when your process gets new pages, they're all mapped to a special zero-page and set to copy-on-write. So there is still some efficiency here in theory: you don't have a long wait for the entire range to be zeroed all at once and you never have to zero pages that you don't modify.
- fyp 7y agoIs that how languages that always give you zeroed arrays (e.g., java) do it?
- deleted 7y ago[deleted]
- NohatCoder 7y agoThere is no canonical answer to that question. Compilers wary wildly in implementation details.
- marcoperaza 7y agoI doubt it. Needing to zero ultra large chunks of memory often enough that you care about performance to this extent is a very niche scenario. If I had to guess, Java probably just zeroes the memory upon garbage collecting it or before handing it back out; fresh pages from the OS are already zeroed. But anything is possible. Maybe some big customer used this pattern and now Java detects it and does something fancy like what I suggested. But really, this is an unusual scenario for an application.
- rob74 7y agoThis goes to show that sometimes it really pays to read the docs: the doc comment of "fill" says "For char types filling contiguous areas of memory, this becomes an inline call to @c memset or @c wmemset"...
- IshKebab 7y agoYes that was mentioned in the article.
- gpderetta 7y agoarguably is still a standard library bug (or better, missed optimization). What triggers the optimization should be the value type of the range, not the type of the value to be filled in. The issue here is a quirk of overloading rules: after template instantiations two overloads of __fill_a are available, one with a deduced 'int' type for the fill value type and another with a 'char' type. Both are perfectly valid instantiations, but the 'int' valued one is preferred by the partial ordering rules as it does not require a conversion. I think this might easily be solved by making the type of the value to be filled in a separate template parameter even for the pointer variant. Also, in addition to pointers, the memset optimization should really be applied for all contiguous iterators (for example std::vector::iterator). Just use -O3. edit: minor fixes and rewording.
- quietbritishjim 7y ago> What triggers the optimization should be the value type of the range, not the type of the value to be filled in. As the article says, you have to do at least some checking on the type of the source value, because it could be a user-defined type with an overloaded implicit conversion operator (operator char()) that does something non-trivial. (I'm not completely sure that my comment contradicts what you've just said, but that's because I don't quite see what you're saying.)
- gpderetta 7y agoSure, but the enable_if<is_scalar<> > already takes care of it, I'm not suggesting taking the check away (although it might be possible to relax it to checking whether a type is trivially constructible and copyable). Now that I think of it you probably need to check that both the iterator value type and the value itself are trivially copyable, constructible and that the value is trivially convertible to the iterator value type itself. No wonder that the std library maintainers went for the easier way.
- eb0la 7y ago> If this were C, we would probably reach for memset Actually I was thinking about bzero(). Seeing memset() made me smile :-)
- dgellow 7y agoWould you mind you explaining what you mean by that? I don't have much C experience, and don't understand what makes you smile.
- eb0la 7y agoIt brings me memories from my old Turbo C 2.0 years (https://en.wikipedia.org/wiki/Borland_Turbo_C https://en.wikipedia.org/wiki/Borland_Turbo_C) ;-)
- lorenzhs 7y ago> The bzero() function is deprecated (marked as LEGACY in POSIX.1-2001); use memset(3) in new programs. POSIX.1-2008 removes the specification of bzero(). from the manpage on linux.
- JdeBP 7y agoNot for long. Seeing some copied-and-pasted autoconf setup, for a program that isn't even portable from Linux, valiantly checking to see whether you have a memset() function will make you despair once more. Or watching autoconf insist that on Debian Linux there is no memset() library function. * https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=927705 https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=927705 Come 1989, this stuff will be standardized, you know. (-:
- nwmcsween 7y agoDon't blame stove for blowing up the house?
- drfuchs 7y agoI’ve always wondered how much CPU time and memory bandwidth is taken up by the OS zeroing out pages before handing them out, as well as programs and libraries clearing chunks of memory. I guess it’s enough that I’m surprised that there’s no hardware support for the memory system to support a way to handle it by itself on command, without taking up bus bandwidth or CPU cycles. Kind of like old-fashioned REP STOS but handled off-chip, as it were. [Added:] Concerning various instructions for clearing whole cache lines in one go, you still end up with lots of dirty cache lines that have to be sent to L1, L2, ..., RAM (not to mention the stuff that was previously in those cache lines), so there’s still lots of bus bandwidth being consumed.
- Doxin 7y agoI'm sure there's some DMA going on there. The OS could simply keep a reserved zeroed out page and tell the DMA hardware to copy it wherever when it needs to zero out a page. I'd be rather surprised if tricks like that don't already happen. I'd be doubly surprised if modern DMA hardware doesn't support fancier tricks, if writing a repeated byte pattern is supported you wouldn't even need to reserve a whole page of zeroes, a single byte would do.
- vardump 7y agoDMA implies going to DRAM or in some cases L3. It's going to be way slower.
- gpderetta 7y agoOne issue is that the memory controller is in the cpu itself (what goes on the wire are the low level line control signals). Also for small ranges, the memory actually being zeroed would be in cache anyway and anything touching the cache would interfere with the cpu, so it is hard to do better than rep stos.
- BeeOnRope 7y agoYeah, this. Unless you are zeroing a really big chunk of memory, you expect that it might already be in the cache and you almost always want it in the cache after, so pushing it down to the memory is often counter-productive in this sense: you want it close to the core. Zeroing memory does take up a non-negligible amount of time some some workflows, especially those that make sparse use of the memory (e.g., don't end up writing all the memory in the end, think a large-radix histogram where many counters stay zero, or allocations that are larger than needed and don't end up getting used, etc). That said, zeroing can be pretty fast as this post shows: around 30 bytes per cycle, which on a 4 GHz CPU is 120 GB/s. AVX-512 doubles that to ~60 bytes/cycle.
- underdeserver 7y agoAnother leaky abstraction.
- heisenbit 7y agoWay back in my 6502 days I entered a competition for the fastest sieve program. My program had self modifying code running on the zero page. To reset the 8K memory the program employed 24k memory for the store instructions. The winning entry left me in the dust - rather than zeroing the memory in the winning program’s array was initialized with a template of the first few primes. There can be solutions that are even faster than the fastest possible zeroing.
- pharrington 7y agoTypes are meaningful. At least to me, the discovery would have been to be mindful of your types when invoking idioms you've learned.
- BeeOnRope 7y agoAgreed, but it is especially insidious here because for integer literals like 0 or 1, etc - it is common to simply assign or pass those directly to other integer types, and 99% of the time, C++ does the right thing. Here it still does the right thing in that the code is correct, but you walk off a performance cliff.
- gumby 7y agoAs an anonymous `mmap()` returns zeroed pages it's likely the fastest mechanism for large arrays.
- quotemstr 7y agoWhere do you think those zeros come from? The kernel demand faults that mmap, and on each fault, has to find a page containing zero. Sometimes it has to make one.
- gumby 7y agoYes but the large array needs to allocate that memory already.
- quotemstr 7y agoSure. I'm just saying that the kernel doesn't have some kind of magic capability that lets it zero memory faster than userspace can. It does have a small free-list of already-zero pages, granted, but a really big allocation will deplete that list, and that list needs to be replenished somehow. For Linux, I want to grant MAP_UNINITIALIZED access to unprivileged users (keep reading) but actually zero pages it gives to these unprivileged MAP_UNINITIALIZED --- users unless it knows that a page doesn't contain privileged information. For example, if a process munmap()s a particular region and then immediately mmap()s a different one, and no other process has ever mapped that page, there's no harm in allowing the process to see its own previous page content.
- BeeOnRope 7y agoHeh, I've had similar thoughts about "safe MAP_UNINITIALIZED", although the demand for this feature is probably pretty low since you can do much the same thing in userspace (just don't return that memory in the first place). Of course, the kernel way has some advantages: - You are making the memory available to the rest of the system if needed. - It could give you other types of pages w/o privileged info, e.g., page cache pages from files you have permission to read, or something like that.
- sradman 7y agoDaniel Lemire compares std::fill in C++ with memset in C in agreement with Travis Down https://lemire.me/blog/2020/01/20/filling-large-arrays-with-zeroes-quickly-in-c/ https://lemire.me/blog/2020/01/20/filling-large-arrays-with-...
- thestoicattack 7y agoInterestingly the std::array::fill member function is identical in the case of int or char, I suppose because there's only one overload of fill and it has to take the element type. No idea if the generated stosq is as fast as built-in memset: https://godbolt.org/z/4iYGup https://godbolt.org/z/4iYGup
- leeter 7y agoIIRC it's very CPU dependent. I remember running into a similar issue with memcpy vs. memmove where the latter was actually faster on some CPUs because it used stosb instead of AVX/SSE and some intel CPUs could make that really go fast. TL;DR: benchmark for your specific hardware if it really matters.
- BeeOnRope 7y agoRecent glibc seems to use 'rep stosb' for largish regions of memset. At least for the numbers I give in this post, the ~30 bytes/cycle is actually coming from rep stosb inside memset. The q variants (as opposed to b) are a bit of a grey area: Intel has this REP ERMBS thing [1] that promises fast performance for rep movsb and rep movsb specifically, but not for the w, d or q variants. However, I think all Intel hardware that has implemented it has implemented the d and q variants just as fast. It would be good to verify it though... --- [1] https://stackoverflow.com/q/43343231 https://stackoverflow.com/q/43343231
- PaulDavisThe1st 7y agoanother day, another reason I am glad I only know some C++ idioms. If I had a byte-oriented block of data, it would never occur to me to use std::fill() ... because it would never occur to me use std::fill() for anything at all ! :)