6 ms·
Filling large arrays with zeroes quickly in C++
- deleted 7y ago[deleted]
- gpderetta 7y agoBeOnRope article linked in the post is the better article in this case: https://travisdowns.github.io/blog/2020/01/20/zero.html https://travisdowns.github.io/blog/2020/01/20/zero.html
- dang 7y agoCurrently discussed at https://news.ycombinator.com/item?id=22104576 https://news.ycombinator.com/item?id=22104576.
- numlock86 7y agoIn my opinion the most interesting part - that does not even get addressed in the article - is this: std::fill(p, p + n, 0) : 1.71732 GB/s std::fill(p, p + n, '\0') : 30.3459 GB/s memset(p,0,n) : 30.419 GB/s Ok, memset ist fast, alright. But why the difference between simply setting 0 vs null char/byte? Is this because 0 is actually larger than a single byte?
- EdSchouten 7y agoIt’s likely because std::fill() is a generic function that can be used to fill any list with any kind of value (even class instances). There likely is some template specialization in place, that if it’s called with a ‘char’ list, that it gets translated into a call into libc’s memset(). That’s why the results for the last two are close to identical. Alternatively, there is no template specialization going on, but it’s the case that the compiler detects that this is identical to memset() and converts it accordingly. LLVM/Clang does this through something called the LibCall optimization pass, IIRC.
- deleted 7y ago[deleted]
- wyldfire 7y agoThe linked article goes into more detail. One calls memset and the other doesn't.
- simfoo 7y agoI would actually consider this a bug of the std library implementation. Would love to see a comparison between different implementations (libc++, libstdc++, MSVC)
- simfoo 7y agoIn fact all three major compilers manage to use memset in all cases, see here: https://godbolt.org/z/hVJfPE https://godbolt.org/z/hVJfPE
- hoseja 7y agoI bet it's some standardese about pointer aliasing preventing memset-like performance.
- gpderetta 7y agoThe reason is fully explained in BeOnRope article. It is due to a missed optimization in the standard library. The optimizer still fixes the issue at O3.
- wyldfire 7y ago...by calling memset(). The referenced article [1] is much clearer and more detailed. The bit in that article about lowering std::fill to memset but only with character types is interesting, e.g. [1] https://travisdowns.github.io/blog/2020/01/20/zero.html https://travisdowns.github.io/blog/2020/01/20/zero.html
- beci 7y agoI can't imagine any situation, when this could be the bottleneck.
- daxfohl 7y agoA cloud host launching a new 30GB VM securely? Edit: nvm they probably do this out of band. But still, things like this.
- pvtmert 7y agowhen thousands of megabytes allocated then deallocated for multiple users, this indeed cause impact on your application. simply running spring-framework tests are enough to demonstrate the impact (of course jvm with related arguments)
- deleted 7y ago[deleted]
- deleted 7y ago[deleted]
- daxfohl 7y agoSeems like something that could be done in HW? IDK much about HW architecture, but I'm surprised there's no way a CPU can tell the memory to zero out some range in a single command.
- kristoffer 7y agoWell, on e.g. x86 you have "rep stos" instruction which pretty much amounts to memset in HW. The operation needs to be blocking otherwise you could of course do it without CPU at all (DMA). But you still have to go through the memory controller and actually write each word of memory.
- daxfohl 7y agoWhy can't memory modules be smarter? Or wouldn't it make a difference? i.e. is the cpu-to-memory bus just as fast as any action exclusively inside the memory module itself could be?
- kristoffer 7y agoYou can only address one row/column at a time in a normal DDR memory. Start by reading this if you want to learn more: https://people.freebsd.org/~lstewart/articles/cpumemory.pdf https://people.freebsd.org/~lstewart/articles/cpumemory.pdf In the end memory design is limited by the laws of physics.
- daxfohl 7y agoAh, I never knew that was how it worked. Thanks! Still, it seems like there's a way it could be redesigned such that zeroing large blocks is done completely in the module and is faster, and provide an extra line for it. With the naive (and probably wrong) implementation I'm thinking, you'd get log N zeroing but bigger constant multiplier on lookup, so that would be the wrong compromise in just about every situation. Maybe you could generify it so that you could do various operations beyond just zeroing and that might be interesting? Though I'm sure this is a plenty well explored topic already, and has come up with what we have now.
- adev_ 7y agoIt is a very bad blog post. Pushing C++ dev to make premature C-style type of optimization is counter-productive... And in this case it is even wrong microbenchmarking. A simple switch to "-O3 -march=native" flag switch in the makefile to enable vectorization and a proper use of '\0' inverse the result make std::fill() globally faster than memset. ``` page count: 262144, volume:1024 MB std::fill(p, p + n, '\0') : 25.9191 GB/s memset(p,0,n) : 25.3283 GB/s std::fill(p, p + n, '\0') : 25.6167 GB/s memset(p,0,n) : 25.1646 GB/s std::fill(p, p + n, '\0') : 25.8355 GB/s memset(p,0,n) : 25.6276 GB/s ``` It would have been much more productive to describe why std::fill with '0' is slower than with '\0' ( integer vs char )
- adrianN 7y agoClang produces exactly the same code for both: https://godbolt.org/z/C7UTqN https://godbolt.org/z/C7UTqN and at -O3 gcc produces almost the same code for both (not at O2 though)
- adev_ 7y agoThis is also mis-interpretation of micro-benchmark and illustrate pretty well that benchmarking this kind of thing is difficult. If you analyze the ASM generated by the benchmark he proposed, you see something very different of what the godbolt "simple" compilation of micro-isolated function give you. - Most call to "fill" are generally transparently replace by a "memset" call directly by the compiler in high level of optimization when done in a normal glibc/GCC linux configuration. - It can even being removed entirely sometimes and this is also a problem ( https://www.usenix.org/system/files/conference/usenixsecurity17/sec17-yang.pdf https://www.usenix.org/system/files/conference/usenixsecurit... ) - This does not seem to occur on godbolt for ...reasons. https://godbolt.org/z/RGEXH8 https://godbolt.org/z/RGEXH8 - Enable vectorization + some compiler flags can in some case make the memset call replaced by a bunch of SIMD code depending of your compiler / compiler options and/or cpu. - The intel compiler is (like usual) much more aggressive and replace everything by their home-made memset implementation https://godbolt.org/z/7RAYGc https://godbolt.org/z/7RAYGc
- gpderetta 7y ago
- gambiting 7y agoProgrammers "typically" use std::fill?? Where are those programmers? I've been a professional C++ programmer for a while now and I've never seen it used over standard memset, even on different platforms with different architectures and multitude of compilers.