{"id":47,"date":"2008-05-24T14:42:34","date_gmt":"2008-05-24T19:42:34","guid":{"rendered":"http:\/\/vgable.com\/blog\/2008\/05\/24\/memcopy-memmove-and-speed-over-safety\/"},"modified":"2009-02-24T07:13:35","modified_gmt":"2009-02-24T12:13:35","slug":"memcopy-memmove-and-speed-over-safety","status":"publish","type":"post","link":"https:\/\/vgable.com\/blog\/2008\/05\/24\/memcopy-memmove-and-speed-over-safety\/","title":{"rendered":"memcopy, memmove, and Speed over Safety"},"content":{"rendered":"

“We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil<\/strong>.” <\/p><\/blockquote>\n

–Knuth, Donald. Structured Programming with go to Statements, ACM Journal Computing Surveys, Vol 6, No. 4, Dec. 1974. p.268.<\/p>\n

If you’ve programmed in C, you’ve seen memcpy<\/a><\/code> (pronounced “mem-copy”). It’s the preferred way to copy a block of memory somewhere. There is a safer and equally easy to use alternative, memmove<\/a>.<\/code> But it has never gained traction, in spite of it’s advantages. As we will see, this is unfortunate, and may be an example of a programming culture that values (superficial) speed over safety.<\/p>\n

The Difference<\/strong><\/p>\n

The difference between memcpy<\/code> and memmove<\/code> is simple: when the source and destination blocks of memory overlap (for example, if they are the same), memmove<\/code> works, but memcpy<\/code>‘s behavior is undefined<\/em>. It might work. It might crash. It might corrupt data. It might behave differently during debugging.<\/p>\n

memmove<\/code> is safer.<\/p>\n

memcpy<\/code> can be<\/em> faster, and usually is. There are less restrictions on it’s implementation, so more can be done to optimize it. But not necessarily a lot more — in fact, it could even be slower then memmove<\/code>, and sometimes this is the case. On some systems, memcpy<\/code> may just be memmove<\/code>.<\/p>\n

Faster<\/strong><\/p>\n

So how much faster can memcpy<\/code> be then memmove<\/code>? They both take O(N)<\/em> time to copy N<\/em> bytes of data. So in some computer-science circles, memcpy<\/code> wouldn’t be considered faster then memmove<\/code>.<\/p>\n

Algorithmically, memmove<\/code> needs one extra if<\/code>-statement before it starts to copy; to determine if it needs to copy front-to-back, or back-to-front. (See this reference implementation<\/a> for an example.) The only other advantage memcpy<\/code> may<\/em> have are esoteric processor-specific instructions that assume restricted pointers<\/a>. So unless there is a “memcpy<\/code> instruction”, we can expect the difference in speed to be pretty small.<\/p>\n

But the real proof is in the pudding and … memmove<\/code> is faster then memcpy<\/code><\/strong>! At least on my laptop, with this test<\/a>; basically copying 4MB of memory 100 times. See for yourself:
\n
\n$ gcc -O0 memcpy_memove_lab.c && .\/a.out
\n   Surprise!
\n   memmove is 1.404409 times faster then memcpy<\/p>\n

gcc -O3 memcpy_memove_lab.c && .\/a.out
\n   Surprise!
\n   memmove is 1.054571 times faster then memcpy
\n<\/code><\/p>\n

“This must be an unfair test!”, you’re probably thinking. Yes, it is. Or at least it’s a dangerously narrow test<\/strong>. But it is also an honest and simple test. By that I mean, it is the first<\/em> code I hammered out to just get some numbers for this article. Proper benchmarking is very<\/strong> difficult. I’m not going to attempt it.<\/p>\n

The real lesson from this naive benchmark is that you must measure your code<\/em> before concluding that an optimization is really faster<\/strong>. I would never have guessed that memmove<\/code> would be up to 40% faster, at copying 4MB. But it was — in this particular instance.<\/p>\n

On a related note, a significantly faster memcpy<\/code> (say 2x) won’t have an appreciable impact on an application’s performance, unless the application spends a surprisingly large portion of it’s time copying memory (Amdahl’s law<\/a>). For example, let’s say that 1 out of every 20 seconds is spent copying memory with memmove<\/code>. (That’s a lot of time just moving bits around! Programs should do something with bits, not just move them.) So we replace memmove<\/code> with memcpy<\/code>, and this<\/em> memcpy<\/code> is a full 2x faster then memmove<\/code> (which is optimistic). Surprisingly, we only get a 2.5% speedup! Remember that 1 in 20 is only 5% of the program’s total time. Cutting this time in half eliminates 2.5% of the program’s total execution time. If we can find an optimization that speeds up the other 95% of the program by just 2.7%, we get better performance overall.<\/p>\n

So memcpy<\/code> is unlikely to make a large difference to program performance, in general<\/em>. Switching memcpy<\/code> implementations is a “local optimization”, that has much less value then changing the algorithm that’s requiring all that duplication. It may even suddenly become slower<\/a> when hardware is upgraded.<\/p>\n

Safer<\/strong><\/p>\n

How much safer is memmove<\/code>? This is a hard dimension to quantify, and I don’t have a satisfying answer. My instinct tells me that it isn’t dramatically safer. I don’t have any data to support this, but I believe it’s very rare to be copying memory into itself; compared to other memory-management errors, like a double-free()<\/code>.<\/p>\n

But the bottom line is that, there are less ways your program can fail if you use memmove<\/code> over memcpy<\/code>.<\/strong> Period. Since memcpy<\/code>‘s behavior is undefined<\/em> when the source and destination overlap, it can be a vicious bitch to debug.<\/p>\n

Speed over Safety<\/strong><\/p>\n

memcpy<\/code> is preferred by a significant majority of C programmers. I don’t know exactly how many. But a google fight<\/a> shows that memcpy<\/code> is almost 6x more talked about then memmove<\/code> (as of 2008-04-11). Anecdotally, memmove<\/code> is mostly unheard of in my experience. It seems like the call of “faster” really is a siren’s-song for developers; luring them into dangerous code.<\/p>\n

I think this is very unfortunate. Especially, because the performance advantage of memcpy<\/code> just isn’t that big in general! (Sometimes it’s even harmful). Given the unreliability of software<\/a>, anything that elements bugs is a Very Good Thing.<\/p>\n

I wish I knew the full story of memcpy<\/code> winning the popularity contest with memmove<\/code>. By accident or design, it has left us with a programming culture that values superficial<\/em> speed over safety<\/strong>.<\/p>\n

For Further Reading:<\/strong><\/p>\n

Optimizing memcpy<\/code><\/a> — includes some graphs showing the tradeoffs between optimizing for large chunks of memory (say copying pictures), and small data structures.<\/p>\n

Why aren’t my optimizations optimizing?<\/a> — “Optimizing code is a tricky business.”<\/p>\n

memcpy_memove_lab.c<\/a> — The naive benchmark from this article, plus a reference implementation of memcpy and memmove.<\/p>\n

\n","protected":false},"excerpt":{"rendered":"

“We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.” –Knuth, Donald. Structured Programming with go to Statements, ACM Journal Computing Surveys, Vol 6, No. 4, Dec. 1974. p.268. If you’ve programmed in C, you’ve seen memcpy (pronounced “mem-copy”). It’s the preferred way to copy […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12,4],"tags":[35,36,37],"class_list":["post-47","post","type-post","status-publish","format-standard","hentry","category-design","category-programming","tag-hubris","tag-memcpy","tag-memmove"],"_links":{"self":[{"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/posts\/47","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/comments?post=47"}],"version-history":[{"count":0,"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/posts\/47\/revisions"}],"wp:attachment":[{"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/media?parent=47"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/categories?post=47"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/tags?post=47"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}