c - 复制字符串的最有效方法是什么？

Question

cpu（基准方法）复制字符串的最有效方法是什么？

我是 c 的新手，我目前正在复制这样的字符串

    char a[]="copy me";
    char b[sizeof(a)];
    for (size_t i = 0; i < sizeof(a); i++) {
        b[i] = a[i];
    }
    printf("%s",b); // copy me

这是另一种选择，while 循环比 for 循环（我听说的）快一点

 char a[]="copy me";
 char b[sizeof(a)];
 char c[sizeof(a)];
    
void copyAString (char *s, char *t)
{
    while ( (*s++ = *t++) != '[=11=]');
};

copyAString(b,a);

printf("%s",c);

Answer 1

通常，复制字符串的最有效方法是手动展开循环以最大限度地减少所需的操作数。

示例：

char *mystrcpy(char *restrict dest, const char * restrict src)
{
    char *saveddest = dest;

    while(1)
    {
        if(!(*dest++ = *src++)) break;
        if(!(*dest++ = *src++)) break;
        if(!(*dest++ = *src++)) break;
        if(!(*dest++ = *src++)) break;
        if(!(*dest++ = *src++)) break;
        if(!(*dest++ = *src++)) break;
        if(!(*dest++ = *src++)) break;
        if(!(*dest++ = *src++)) break;
        if(!(*dest++ = *src++)) break;
        if(!(*dest++ = *src++)) break;
        if(!(*dest++ = *src++)) break;
        if(!(*dest++ = *src++)) break;
        if(!(*dest++ = *src++)) break;
        if(!(*dest++ = *src++)) break;
        if(!(*dest++ = *src++)) break;
        if(!(*dest++ = *src++)) break;
    }
    return saveddest;
}

https://godbolt.org/z/q3vYeWzab

glibc 实现使用了非常相似的方法。

Answer 2

当您可以使用像 memcpy（长度已知时）或 strcpy（长度未知时）这样的标准函数时，不要编写自己的复制循环).

现代编译器将它们视为“内置”函数，因此对于常量大小可以将它们扩展为几个 asm 指令，而不是实际设置对库实现的调用，这将不得不在大小上分支等等.因此，如果您因为库函数调用短副本的开销而避免使用 memcpy，请不要担心，如果长度是 compile-time 常量，则不会有 memcpy。

但即使在未知/runtime-variable 长度的情况下，库函数通常也是优化版本 hand-written 在 asm 中比你能做的任何事情都快得多（尤其是对于中到大的字符串）在纯 C 中执行，特别是对于没有未定义行为的 strcpy 读取缓冲区末尾。

您的第一个代码块具有 compile-time 大小不变（您可以使用 sizeof 而不是 strlen）。您的复制循环实际上会被现代编译器识别为 fixed-size 副本，并且（如果很大）变成对 memcpy 的实际调用，否则通常会进行类似的优化。

数组索引的方式无关紧要；优化编译器可以看穿 size_t 索引或指针，并为目标平台制作良好的 asm。有关代码实际编译方式的示例，请参阅 this and this 问答。请记住，CPU 运行 asm，而不是直接 C。
不过，此示例太小且过于简单，无法实际用作基准。参见

你的第二种方式相当于 strcpy 的 implicit-length 字符串。这比较慢，因为它必须搜索终止 0 字节，如果在编译时在内联和展开循环后不知道它的话。

特别是如果您像这样对 non-constant 字符串进行手工操作；现代 gcc/clang 无法 auto-vectorize 循环，程序无法在第一次迭代之前计算 trip-count。即它们在 strlen 和 strcpy 等搜索循环中失败。

如果您实际上只是调用 strcpy(dst, src)，编译器将以某种有效的方式内联扩展它，或者发出对库函数的实际调用。 libc 函数使用 hand-written asm 来高效地执行它，特别是在 SIMD 可以提供帮助的像 x86 这样的 ISA 上。例如，对于 x86-64，glibc 的 AVX2 版本 (https://code.woboq.org/userspace/glibc/sysdeps/x86_64/multiarch/strcpy-avx2.S.html) 应该能够在 Zen2 和 Skylake 等主流 CPU 上为 medium-sized 个副本每个时钟周期复制 32 个字节，其中源和目标在缓存中处于热状态。

似乎现代 GCC/clang 做 not 将这种模式识别为 strcpy 他们识别 memcpy-equivalent 循环的方式，所以如果你想有效地复制 unknown-size C字符串，你需要使用实际的strcpy。（或者更好，stpcpy to get a pointer to the end，这样你之后就知道字符串长度，允许你使用 explicit-length 东西而不是下一个函数也必须扫描字符串的长度。）

自己一次写一个 char 将最终使用字节 load/store 指令，因此每个时钟周期最多可以使用 1 个字节。（或者在 Ice Lake 上接近 2，可能在加载 / macro-fused test/jz / 存储的 5-wide front-end 上遇到瓶颈。）因此对于具有 runtime-variable 编译器无法删除循环的源代码。

(https://agner.org/optimize/ for performance of x86 CPUs. Other architectures are broadly similar, except for how useful SIMD is for strcpy. ISAs without x86's efficient SIMD->integer ability to branch on SIMD compare results may need to use general-purpose integer bithacks like in - 但请注意，这是 glibc 的可移植 C 回退，仅用于少数没有人编写 hand-tuned asm 的平台。)

他们展开的 char-at-a-time 循环比 glibc strcpy 对于 1024 个字符的字符串更快，但这是难以置信的，可能是错误的基准测试方法的结果. （比如编译器优化打败基准测试，或页面错误开销或 libc strcpy 的惰性动态链接。）

相关问答：

Is memcpy() usually faster than strcpy()? - 是的，尽管对于 x86 上的大型副本，strcpy 几乎可以跟上； x86 SIMD 可以有效地检查整个块中的任何零字节。
faster way than memcpy to copy 0-terminated string
- 微基准测试很难：您需要编译器优化应该优化的部分，但仍然在基准循环中重复工作，而不是只做一次。
- 是的，以及内存保护在对齐页面中工作的所有其他 ISA。（它在技术上仍然是 C UB，但在 asm 中是安全的，所以 hand-written 库函数的 asm 可以 100% 安全地做到这一点。）
Efficiency: arrays vs pointers
In C, accessing my array index is faster or accessing by pointer is faster?

Answer 3

这可能不适合您的 use-case，但我发现当我复制 image-array（我说的是 >10 倍）时，这段代码比 memcpy 快得多。可能有很多人会从中受益，所以我把它贴在这里：

void fastMemcpy(void* Dest, void* Source, unsigned int nBytes)
{
    assert(nBytes % 32 == 0);
    assert((intptr_t(Dest) & 31) == 0);
    assert((intptr_t(Source) & 31) == 0);
    const __m256i* pSrc = reinterpret_cast<const __m256i*>(Source);
    __m256i* pDest = reinterpret_cast<__m256i*>(Dest);
    int64_t nVects = nBytes / sizeof(*pSrc);
    for (; nVects > 0; nVects--, pSrc++, pDest++)
    {
        const __m256i loaded = _mm256_stream_load_si256(pSrc);
        _mm256_stream_si256(pDest, loaded);
    }
    _mm_sfence();
}

这使用了内在函数，因此包括。 stream-commands 绕过 CPU 缓存，似乎在速度上有很大的不同。对于更大的数组，您还可以使用多线程，这会进一步提高性能。

c - 复制字符串的最有效方法是什么？

c - what is the most efficient way to copying a string?

c

string

benchmarking

loops

for-loop