8 ms·
Fast memcpy, a system design
- zX41ZdbW 4y agomemcpy implementation is a rabbit hole. The main trap is trying to benchmark and profile it without the context of the whole application. I recommend to read a comment in ClickHouse source code (disclaimer: written by me) https://github.com/ClickHouse/ClickHouse/blob/master/base/glibc-compatibility/memcpy/memcpy.h#L6 https://github.com/ClickHouse/ClickHouse/blob/master/base/gl...
- vanderZwan 4y ago> The main trap is trying to benchmark and profile it without the context of the whole application. Emery Berger's "Performance (Really) Matters" talk also goes into this[0]. He paints a really, really depressing picture of how unreliable benchmarks truly are. Like, things like link order having ridiculous impacts and stuff like that. [0] https://www.youtube.com/watch?v=7g1Acy5eGbE&t=306s https://www.youtube.com/watch?v=7g1Acy5eGbE&t=306s
- titzer 4y agoJust make memcpy a bonafide hardware instruction already. Since it could take unbounded execution time, you could, e.g. limit to a fixed, large size, like 4KB. That'd be a huge benefit, just in handling all the alignment/misalignment cases. And it's big enough that the loop you need to put around it has relatively low overhead. You could specify that address translations (and therefore faults) happen at the beginning, and no data is written.
- userbinator 4y agox86 has had that since the 8086. It's called REP MOVS. As far as I know, it's still the fastest general-purpose way to do copying.
- titzer 4y agoI've heard this before and unfortunately it isn't.
- userbinator 4y agoDo you have any more information to share? The ultra-bloated unrolled vector implementations may appear a little faster in microbenchmarks but the amount of cache they take up and other effects like AVX downclocking (for those implementations that use AVX) mean that in practice they can actually be slower overall.
- titzer 4y agoI've heard this directly from engineers at Intel.
- saagarjha 4y agoIs this pre- or post-ERMS?
- titzer 4y agoI heard this around 2018 or so.
- loeg 4y agoI don't believe it's been consistently the fastest way to copy memory even post-ERMSB. (It would be great and convenient if it were!)
- saagarjha 4y agoPerhaps for very small sizes (just use a mov directly) and very large ones (that fall out of your cache, so you’d probably want non-temporal stores). I think it would be difficult to cover all cases.
- 4y ago
- stephencanon 4y agoARM did so in ARMv8.8, and x86 has had REP MOVS since forever (though it only became consistently faster than SW sequences relatively recently).
- deleted 4y ago[deleted]
- nerpderp82 4y agoNot just an instruction, but something the MMU can use to coalesce memory in the background, if the MMU can do multiple levels of indirection or RC pages, then it can also do GC. The MMU has been too underpowered for too long.
- moonchild 4y ago> We introduce two new instructions to handle the short move case quickly These are more or less built in to avx512 already... (The hot path is: load immediate; bzhi; kmov; load; store. 5 instructions rather than 2, but still trivial. If you look at the _latencies_ involved, the difference is trivial.)\ (Afaik it's in sve too.)
- als0 4y ago> We suggest a few new instructions Not really a novel idea, particularly since ARM already announced memcpy instructions earlier this year.
- 323 4y agoIntel is known to analyze code from actual applications and invent new instructions that seem to be missing. Surely they are aware of the memcpy problem, so if it's true that servers spend a lot of time copying memory, what is Intel (or AMD) doing regarding this?
- userbinator 4y agowhat is Intel (or AMD) doing regarding this? In this case they haven't invented new instructions at all but have been steadily improving REP MOVS over time.
- 323 4y agoSo does that mean that further major optimizations are basically impossible? You don't always need the operation finished right away. Maybe REP MOVS could return a sort of a handle that you then wait for when you actually need to use the destination, and the CPU can keep chugging along in the background. Like when you submit commands to the GPU or how you can wait at memory fences for other threads in a warp to complete.
- __init 4y agoFurther optimization are certainly possible, especially as the hardware improves and gains additional capabilities. With regards to your suggestion, this is essentially what already happens, thanks to the magic of out-of-order cores.
- meindnoch 4y agohttps://en.m.wikipedia.org/wiki/Direct_memory_access https://en.m.wikipedia.org/wiki/Direct_memory_access
- twoodfin 4y agoSee the Data Streaming Accelerator: https://01.org/blogs/2019/introducing-intel-data-streaming-accelerator https://01.org/blogs/2019/introducing-intel-data-streaming-a...
- actionfromafar 4y agoCan’t we get content addressable memory already? That would make memcpy moot in many cases.
- warkdarrior 4y agoContent addressable memory with built-in copy-on-write, fine granularity, and security tags? Not sure it is possible.
- actionfromafar 4y agoWould be amazing though? I’m thinking lots of tiny compute near the RAM chips.
- rsaxvc 4y agoSounds like Belt.
- meindnoch 4y agoOk, I’ll bite: in which cases does content addressable memory obsolete memcpy? It’s just a lookup table in hardware…
- actionfromafar 4y agoContent addressable memory is the ultimate "zero copy architecture". Imagine a "CPU instruction" or library call which determines that, "no, I have already seen this address" (where address isn't an address as much as a unique hash) and can pass that hash along to the destination instead of running a copy. Overhead increases by effectively removing pointers as we know them, replacing them with hash+length, but the reward is lower memory pressure and better cache locality. It also carries the promise of making a "buffer overrun" not only impossible but unthinkable. In such a world, incrementing "one extra" would not step into some other heap or stack, because everything would be segmented.
- rwmj 4y agoSomething similar in this paper, putting an FPGA between the processor and DRAM so you can arbitrarily remap bits of it: https://arxiv.org/abs/2109.14349 https://arxiv.org/abs/2109.14349
- WalterBright 4y agoIn my entire long career in software, faster memcpy is a constant topic. I remember using the IBM PC DMA chip to make it faster.
- userbinator 4y agofleet-wide profiling revealed that 25-35% of all CPU time was spent just moving bytes around[...]If data movement were faster, more work could be done on the same processors. Here's a different thought experiment: how much of that data movement is actually necessary? If data movement was taking up so much time, why not investigate why and if that's even necessary, instead of thinking it's the hardware that needs to be faster? As the old saying goes, "the fastest way to do something is to not do it at all." One style of code that seems to be particularly exacerbated by the widespread use of HLLs is making lots of unnecessary temporary copies of data. The biggest inefficiency isn't the hardware (unless your goal is to sell more hardware, but that's a different rant...) --- it's the insanely complex and bloated layers of software that gets layered on top of what is otherwise perfectly adequate hardware. From that perspective, faster hardware only leads to even more wasteful and inefficient software. Making memory copies faster will only cause software to make more unnecessary copies. But after reading the whole thing, I can say that this is certainly a very strange article. It's written by someone who is presumably quite knowledgeable about hardware, yet seems completely oblivious to the fact that x86 has had a dedicated instruction for this since the 8086, and 16 bytes per cycle was already achievable with the P6 (1996) "fast strings" enhancement: https://stackoverflow.com/questions/33902068/what-setup-does-rep-do https://stackoverflow.com/questions/33902068/what-setup-does...
- hinkley 4y agoCynical answer: because that's not sexy. I have some coworkers trying to re-architect a big chunk of our application to selectively provide data because "only about 10% is used on each interaction". Nobody has bothered to check what % of the data is never used at all. If it's 50%, then you're complicating a whole lot of code and reuse semantics in order to get a 2-4x improvement in 'performance' that you're selling as a 10x improvement. But to your bigger question, defensive copies are about keeping someone else from munging your data. Borrow Semantics prevent some of those scenarios, which at least moves some of that inefficiency to compile time, where the tax is paid by the perpetrator and their peers, instead of by the users.
- maria2 4y agoMemory gets moved for a lot of reasons. Any type of FFI usually requires memory copies. For instance, if you pass a C string from Swift to C, the C side needs to copy the memory to use it after the immediate call. Or if C returns a string to Swift, Swift needs to copy the string into its own format.
- chubot 4y agoI wonder if 25-35% of all CPU cycles being devoted to moving bytes around is a design problem, i.e. a result of the RPC-oriented programming model we used at Google I know there were also measurements about protobuf encode/decode, and I think it was a similarly large portion of the total workload. (Anecdotally I think that's why people say the protobuf libraries are huge and big and slow to compile -- because they're highly optimized that's probably what empirically resulted in the fastest execution time) It feels like a content-oriented and value-oriented model would have less of this profile, i.e. with (correct) local caching and differential compression
- secondcoming 4y agoInterestingly, the publicly available protobuf implementation is quite bad for only using std::string for string & repeated bytes fields, with std::string_view support only coming soon. I believe Google’s internal protobuf code support ABSL’s string_view equivalent.
- nerpderp82 4y agohttps://github.com/protocolbuffers/upb https://github.com/protocolbuffers/upb A Hardware Accelerator for Protocol Buffers https://dl.acm.org/doi/abs/10.1145/3466752.3480051 https://dl.acm.org/doi/abs/10.1145/3466752.3480051
- chubot 4y agoAh yeah, I think the historical issue is that Google doesn't use std::string internally for performance reasons. They have their own C++ string implementation, which protobuf uses internally, like all other code. And then when they open sourced it, I guess they left out that code. So the open source version is probably "de-optimized" a bit unfortunately.
- kazinator 4y agoYou should try to code in such a way that if memcpy were made 100X slower, you wouldn't notice.
- saagarjha 4y agoOk, how?
- secondcoming 4y agoOn GCP adding RAM to a machine type increases costs by a stupid amount. Now it seems like they’re thinking of ways to penalise you for actually using it, because you may interfere with another tenant on the same machine.
- gct 4y agoPlease, quit messing with my scroll speed.
- plasticeagle 4y agoI know, it's awful isn't it? The irony of an article about detailed low-level optimisation of memcpy (which is probably being used unnecessarily anyway), re-implementing scrolling in javascript... You've got to admire it, really.
- dxf 4y agoIf anyone is curious or otherwise interested, the version of memcpy() used for Google production is basically what is in LLVM's libc, https://libc.llvm.org https://libc.llvm.org
- jeffbee 4y agoI really like this refutation of the GNU-style micro-optimized-but-slow-in-practice mess of assembly.
- moonchild 4y agoI would like such a refutation, notionally. I do not particularly like this refutation, considering that it is just as overabstracted, and probably not much faster (if at all). What I would really like is to see more widespread hoisting of dispatch. Rather than calling 'memcpy', call 'memcpy_small', 'memcpy8', etc.
- jeffbee 4y agoThat's the whole gist of gchatelet's implementation. Make it easy for the compiler to inline memcpy, so the compiler gets a chance to propagate the information it has about the parameters. In many cases it can eliminate all the branches but one. The GNU way of using a huge, branchy assembly block that is selected at runtime using ifunc means that the compiler never even got a chance. Regarding the question of whether or not they are faster, see section 4.4 of this paper. Replacing the glibc memcmp with something trivial resulted in up to 1% speedup in Google web search, when considering the whole program. It doesn't microbenchmark as well as glibc memcmp, but it is a better function that doesn't wreck the performance of the rest of the system. https://storage.googleapis.com/pub-tools-public-publication-data/pdf/e52f61fd2c51e8962305120548581efacbc06ffc.pdf https://storage.googleapis.com/pub-tools-public-publication-...
- moonchild 4y ago> Make it easy for the compiler to inline memcpy, so the compiler gets a chance to propagate the information it has about the parameters I have low hopes for compilers. Inlining heuristics are terribly complicated, and optimisations that result therefrom will only be things that the compiler can prove for _all_ invocations. Inlining won't get you 'this call site is usually large', or 'this call site is small, but predictable', or 'this call site is really unpredictable, so use weird branchfree tricks'. (A JIT compiler might do better, but people do not usually JIT c or c++.) > Replacing the glibc memcmp with something trivial resulted in up to 1% speedup in Google web search, when considering the whole program. It doesn't microbenchmark as well as glibc memcmp, but it is a better function that doesn't wreck the performance of the rest of the system It's not all or nothing, and rep cmps is utter trash. My memcmp, for instance, I was careful to keep below 4 cache lines (or 3, considering only the version that doesn't overread)—<https://github.com/moon-chilled/fancy-memcmp/blob/master/memcmp-avx512.S https://github.com/moon-chilled/fancy-memcmp/blob/master/mem...>—and it actually has reasonable throughput. (Also: inlining is not the way to go if you are frontend-bound...)
- cryptonector 4y agoThis reminds me of the old Motorola M68K dbcc instruction, which was a specialized looping instruction where you could loop back only a small number of instructions which would all be cached tightly in a tiny cache that existed only for the dbcc case. Are there modern analogues to that dbcc instruction?
- ant6n 4y agoA branch?
- cryptonector 4y agodbcc had a specific semantic that you could only branch back a very small amount and that the CPU would cache the body of the loop. A modern equivalent would use a small amount of cache that is not even L1.
- unwind 4y agoVery interesting and hardcore solutions, adding new instructions to improve data copying in a more "clever" way that just the repeat-prefix seems like an interesting path. There was a silly typo in the very first sentence that threw me off: When I worked at Google, fleet-wide profiling revealed that 25-35% of all CPU time was spent just moving bytes around: memcpy, strcmp, [...] I think that should be `strcpy()`, since obviously `strcmp()` doesn't move data around.