c - If destination and source are the same, what does memmove do?

Question

If destination and source are the same, does memmove still "move" the data (or does it return directly)? What about realloc; what if the new size is the same as the old size?

Answer 1

That's really going to be implementation-specific. It would be good practice to do so, sure, but it really depends which implementation you mean.

It's going to work either way, but presumably a suitably clever implementation would check for overlapping segments (and particularly for the case where source == dest) and deal with it appropriately.

Answer 2

As far as I know no standard gives any promises about returning immediately in such case, so you should not expect this behavior.

Better do not pass invalid pointers in hope it's not going to access the data ;-)

Answer 3

At least for realloc, it is implicitly assumed that a "no move necessary" condition exists and is valid, since moving is noted as a special case:

The realloc() function shall change the size of the memory object pointed to by ptr to the size specified by size. The contents of the object shall remain unchanged up to the lesser of the new and old sizes. If the new size of the memory object would require movement of the object, the space for the previous instantiation of the object is freed.

The wording "if... would" suggests that this is not necessarily always so. Of course there is no requirement at all for an implementation to omit a copy that is not necessary.

The only requirement for memmove is that the final effect is the same as if the data was copied to a temporary buffer first and then copied to the final destination. This "as if" constraint allows the copying of overlapping regions without corrupting data (no implementation that I know really copies to a temporary buffer first).

So, in one word: unspecified.

Answer 4

As others have said, the spec doesn't require a shortcut, and it's not clear when adding the extra branch actually improves performance.

But that doesn't answer the question of what is actually happening when you call memmove. I dug through the glibc source code and found many assembly implementations for various architectures along with a portable C implementation.

The TL;DR is that the pure C version does not shortcut, but the x86_64 assembly version does (I think).

The pure C version is a fairly standard memmove loop. The one trick is that if you are moving 16 KiB or more, it will manipulate virtual memory instead of copying bytes. The function is defined in string/memmove.c, and the meat of the implementation is the BYTE_COPY_FWD macro from sysdeps/generic/memcopy.h.

For x86_64 assembly, there are several versions depending on available instructions (e.g. AVX, SSE, etc). Those are in sysdeps/x86_64/multiarch.

Here is one implementation from memmove-vec-unaligned-erms.S that uses Enhanced REP MOVSB (ERMS):

ENTRY (__memmove_erms)
        movq    %rdi, %rax
        /* Skip zero length.  */
        test    %RDX_LP, %RDX_LP
        jz      2f
L(start_movsb):
        mov     %RDX_LP, %RCX_LP
        cmp     %RSI_LP, %RDI_LP
        jb      1f
        /* Source == destination is less common.  */
        je      2f
        lea     (%rsi,%rcx), %RDX_LP
        cmp     %RDX_LP, %RDI_LP
        jb      L(movsb_backward)
1:
        rep movsb
2:
        ret
L(movsb_backward):
        leaq    -1(%rdi,%rcx), %rdi
        leaq    -1(%rsi,%rcx), %rsi
        std
        rep movsb
        cld
        ret
END (__memmove_erms)

My ability to read assembly isn't great, but from what I can tell, this implementation does shortcut the case where source and destination are the same.

If I read this correctly, it starts by comparing the pointers. If the destination comes before the source, it jumps to label 1 (jb 1f) which calls rep movsb. As I understand it, this is basically an instruction for memcpy. If the pointers are equal, it jumps to label 2 (je 2f) which returns immediately. Otherwise it arranges for a rep movsb to run backwards over the data.

I also took a look at the SSSE3 implementation in sysdeps/x86_64/multiarch/memcpy-ssse3.S. That version also appears to implement the shortcut.

Obviously, all of this only applies to glibc. I haven't checked llvm-libc.