/Does/ memmove use an intermediate buffer?

Question

This is more a question out of curiosity than anything important, but I was just wondering about the following snippet in the memmove documentation:

Copying takes place as if an intermediate buffer were used

(emphasis mine). The formulation suggests to me that whether an intermediate buffer is used, is specific to the compiler implementation.

If you would ask me to write memmove, I would probably automatically do the following:

• allocate n bytes on the heap
• memcpy the source to the temp
• memcpy the temp to the destination
• free the buffer

I was hoping anyone could ...

1. ... confirm whether the formulation is only because it's easier for users to visualize what is going on, without fixing that specific implementations actually have to use an intermediate buffer;
2. ... shed some light on the actual implementation in some common C++ compilers (like gcc or Visual C++) - for example, does it use a buffer and does it check for overlap so it can memcpy directly;
3. ... maybe point out the blatantly obvious error / inefficiency in my simple algorithm above.

Answer 1

1. Indeed. "As if" means that it must behave like that's what it did; but doesn't constrain the implementation to actually do that. The only required behaviour is that the destination buffer ends up with the correct bytes from the source buffer, whether or not the buffers overlap.

2. A common implementation is to copy bytes forwards from the beginning of the buffer if the destination starts before the source, and backwards from the end otherwise. This ensures that the source bytes are always read before they're overwritten, if there is an overlap.

3. There are no errors, unless the allocation fails. The inefficiencies are allocating and freeing the temporary buffer, and copying each byte twice rather than once.

Answer 2

You are absolutely right on the #1 - the description is to help users visualize what's going on logically, not to explain how it is implemented.

However, no sane implementation would actually go about doing it with an expensive temporary buffer, because all you need to do to avoid double-copying is to decide if you want to copy from the beginning or from the end. Here is a sample implementation that does precisely that.

The only problem with your algorithm is that it can run your system out of memory when it is not necessary: imagine that your program tries to move a buffer sized at 60% of the allowed total memory to see an example of when it would happen.

Answer 3

One of the first optimization opportunities that comes to mind is to do a plain memcpy() if the buffers do not overlap. Due to the flat nature of the (virtual) address space, it's easy to check. I looked at the glibc and Android implementations, and both do this (the Android one is easier to follow for the uninitiated).

Allocating memory on the heap is probably a no-go, because it will be quite slow (dynamic allocation is not that cheap).

If the buffers do overlap, we could optimize copying of the parts which do not, and for the rest we might use a small scratch buffer, but that would be stack-allocated if indeed any allocation is needed at all. The Android one copies just one byte at a time; we can do better on amd64 but that's the same sort of optimization that would already be done in memcpy. The glibc one copies either forward or backward depending on the nature of the overlap (that's what "BWD" in the source refers to).

Answer 4

The implementation does not matter. The wording is to guarantee that memory will properly be handled.

char buf[] = { 0x11, 0x22, 0x33, 0x00 };
memcpy(buf, buf + 1, 3);

could result in buf being { 0x11, 0x11, 0x11, 0x11 }.

where as

char buf[] = { 0x11, 0x22, 0x33, 0x00 };
memmove(buf, buf + 1, 3);

is guaranteed that buf will be { 0x11, 0x11, 0x22, 0x33 }.