memmove vs向后复制

Question

据我所知,memmove在C(cstring库)中处理很好地" 以较慢的运行时为代价 "(参见这篇文章).我想知道为什么这个额外的运行时成本？在我看来,任何重叠问题都可以通过向后复制而不是向前复制来解决,我错了吗？

作为一个玩具示例,这里有两个版本的"右移"函数,它将数组的内容移动右侧的一个元素:

// 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 );
}

它们是等价的吗？性能方面,哪一个最好用？

---

注意:根据@DieterLücking的评论判断,尽管采取了预防措施,上述版本的使用memmove在这种情况下是不安全的.

Answer 1

假设一个好的实现,唯一的"额外成本" memmove是初始检查(添加和比较和分支),以决定是从前到后还是从后到前复制.这个成本是完全可以忽略的(添加和比较将被ILP隐藏,而分支在正常情况下是完全可预测的),在某些平台上,memcpy它只是一个别名memmove.

期待你的下一个问题("如果memcpy没有明显快于memmove,为什么它存在？"),有一些很好的理由可以保持memcpy.在我看来,最好的一个是,一些CPU实际上将memcpy实现为单个指令(rep/movs例如,在x86上).这些HW实现通常具有优选(快速)操作方向(或者它们可能仅支持在一个方向上复制).编译器可以自由地memcpy用最快的指令序列替换而不用担心这些细节; 它不能做同样的事情memmove.