复制循环的效率是否低于memcpy()？

Question

我开始研究IT,现在我和朋友讨论这段代码是否效率低下.

// const char *pName
// char *m_pName = nullptr;

for (int i = 0; i < strlen(pName); i++)
    m_pName[i] = pName[i];

他声称例如memcopy会像上面的for循环那样做.我不知道这是不是真的,我不相信.

如果有更有效的方法或者效率低下,请告诉我原因!

提前致谢!

Answer 1

我看了一下代码的实际g++ -O3输出,看看它有多糟糕.

char*可以别名,所以即使__restrict__GNU C++扩展也无法帮助编译器提升strlen循环.

我以为它会被提升,并期望这里的主要低效率只是一次一个字节的复制循环.但不,这真的和其他答案所暗示的一样糟糕. m_pName甚至必须每次都重新加载,因为别名规则允许m_pName[i]别名this->m_pName. 编译器不能假设存储到m_pName[i]不会改变类成员变量,src字符串或其他任何东西.

#include <string.h>
class foo {
   char *__restrict__ m_pName = nullptr;
   void set_name(const char *__restrict__ pName);
   void alloc_name(size_t sz) { m_pName = new char[sz]; }
};

// g++ will only emit a non-inline copy of the function if there's a non-inline definition.
void foo::set_name(const char * __restrict__ pName)
{
    // char* can alias anything, including &m_pName, so the loop has to reload the pointer every time
    //char *__restrict__ dst = m_pName;  // a local avoids the reload of m_pName, but still can't hoist strlen
    #define dst m_pName
    for (unsigned int i = 0; i < strlen(pName); i++)
        dst[i] = pName[i];
}

编译为此asm(g ++ -O3 for x86-64,SysV ABI):

...
.L7:
        movzx   edx, BYTE PTR [rbp+0+rbx]      ; byte load from src.  clang uses mov al, byte ..., instead of movzx.  The difference is debatable.
        mov     rax, QWORD PTR [r12]           ; reload this->m_pName    
        mov     BYTE PTR [rax+rbx], dl         ; byte store
        add     rbx, 1
.L3:                                 ; first iteration entry point
        mov     rdi, rbp                       ; function arg for strlen
        call    strlen
        cmp     rbx, rax
        jb      .L7               ; compare-and-branch (unsigned)

使用unsigned int循环计数器引入了额外的mov ebx, ebp循环计数器,你不要么得到的副本int i或者size_t i,在这两个铛和gcc.据推测,他们更难以解释unsigned i可能产生无限循环的事实.

所以很明显这太可怕了:

• strlen复制每个字节的调用
• 一次复制一个字节
• m_pName每次循环重新加载(可以通过将其加载到本地来避免).

使用strcpy避免了所有这些问题,因为strlen允许假设它的src和dst不重叠.除非你想了解自己,否则 不要使用strlen+ .如果最有效的实现是+ ,则库函数将在内部执行此操作.否则,它会做更高效的事情,比如glibc 为x86-64 手写的SSE2.(有一个SSSE3版本,但它实际上在Intel SnB上速度较慢,并且glibc足够聪明,不能使用它.)即使是SSE2版本也可能比它应该展开的更多(在微基准测试上非常好,但是会污染指令缓存,uop -cache和branch-predictor缓存用作实际代码的一小部分时).大部分复制是在16B块中完成的,在启动/清理部分中有64位,32位和更小的块.memcpystrlenstrcpystrlenmemcpystrcpy

使用strcpy当然也避免了忘记'\0'在目的地存储尾随字符的错误.如果您的输入字符串可能是巨大的,那么使用int循环计数器(而不是size_t)也是一个错误.使用strncpy通常更好,因为您经常知道dest缓冲区的大小,但不知道src的大小.

memcpy可以更高效strcpy,因为rep movs在英特尔CPU上进行了高度优化,尤其是 IvB及以后.但是,扫描字符串以找到合适的长度将始终比差异更大.memcpy在您已经知道数据长度时使用.

Answer 2

充其量只是效率低下.在最坏的情况下,这是非常低效的.

在好的情况下,编译器会识别出它可以将调用提升到strlen循环之外.在这种情况下,您最终遍历输入字符串一次以计算长度,然后再次复制到目标.

在坏的情况下,编译器调用strlen循环的每次迭代,在这种情况下,复杂性变为二次而不是线性.

至于如何有效地做到这一点,我倾向于这样的事情:

char *dest = m_pName;

for (char const *in = pName; *in; ++in)
    *dest++ = *in;
*dest++ = '\0';

这遍历输入一次,所以这是有可能的两倍快为先,即使在较好的情况下(在二次情况下,也可以是多快的时间,这取决于字符串的长度).

当然,这与做同样的事情strcpy.这可能会或可能不会更有效 - 我当然看到它的情况.由于你通常会认为strcpy它会被大量使用,因此花费更多时间来优化它是值得的,因为互联网上的一些随机人员会在几分钟内输入答案.