memmove vs copying backwards

Question

I understand that memmove in C (cstring library) handles overlaps nicely "at the cost of slower runtime" (see this post). I was wondering why this additional runtime cost? It seems to me that any overlap problem could be fixed by copying backwards instead of forward, am I wrong?

As a toy example, here are two versions of a "right-shift" function, that shifts the contents of an array by one element on the right:

// Using memmove
template <typename T>
void shift_right( T *data, unsigned n )
{
    if (n)
    {
        data[n-1].~T();
        memmove( data+1, data, (n-1)*sizeof(T) );
        new (data) T();
    }
}

// Using copy_backward
template <typename Iterator>
void shift_right( Iterator first, Iterator last )
{
    Iterator it = last;
    std::copy_backward( first, --it, last );
}

Are they equivalent? Performance-wise, which one is best to use?

---

Note: judging by the comment of @DieterLücking, and despite the precautions taken, the above version using memmove is unsafe in this situation.

Answer 1

Assuming a good implementation, the only "extra cost" of memmove is the initial check (an add and a compare-and-branch) to decide whether to copy front-to-back or back-to-front. This cost is so completely negligible (the add and compare will be hidden by ILP and the branch is perfectly predictable under normal circumstances) that on some platforms, memcpy is just an alias of memmove.

In anticipation of your next question ("if memcpy isn't significantly faster than memmove, why does it exist?"), there are a few good reasons to keep memcpy around. The best one, to my mind, is that some CPUs essentially implement memcpy as a single instruction (rep/movs on x86, for example). These HW implementations often have a preferred (fast) direction of operation (or they may only support copying in one direction). A compiler may freely replace memcpy with the fastest instruction sequence without worrying about these details; it cannot do the same for memmove.

Answer 2

Memmove figures out for you whether to copy backward or forward; it is also highly optimized for this task (i.e. copying in SSE-optimized blocks as much as feasible).

It is unlikely that you can do any better by calling any generic STL algorithm (the best they could do is to call memcopy or memmove behind the scenes), but of course you could answer this question simply by running your code and timing it.