10

我最近有一个面试问题，我必须实现 memcpy。根据我的经验，我使用过很多 memcpy，所以这似乎不是一个棘手的问题。

所以，我开始实现一个循环，从指针到指针一次复制一个地址，如下所示：

void memcpy(void* dest, void* src, int size){
    for(int index = 0; index < size; index++){
        dest[index] = src[index];
    }
}

然而，面试官打断了他们注意到 memcpy 的手册页说它“将 n 个字节从 src 复制到 dest”（我稍后确认）然后希望我通过 size/4 进行迭代，然后用另一个索引循环来获取剩余的< size%4 （我猜假设它是 32 位系统？）

好吧，这看起来很奇怪，因为我多年来一直没有问题地使用 memcpy 而不必给它一个 *4 修饰符）。当我回到家时，我启动了 gdb 并复制了一个小字符串“hello”，并小心地使用 strlen() 和常量输入大小以查看它在哪里开始和停止。

    char* src = "hello";
    char* dest = calloc(16, sizeof(char));
    int len = strlen(src);
    memcpy(dest, src, len); // both my version and official version

现在我用 gdb 仔细检查了 src 和 dest，它们都包含“hello\0”。

所以我的问题是：我对使用数字 4（或“以字节为单位的大小”）有什么不理解？当这不是真正的行为时，为什么文档会说“n字节”？我在这里看不清楚什么？

4

7 回答 7

15

正如其他人所说，一次复制 4 个字节比一次复制 1 个字节要快。面试官希望你做这样的事情：

void memcpy(void* dest, void* src, int size)
{
    uint8_t *pdest = (uint8_t*) dest;
    uint8_t *psrc = (uint8_t*) src;

    int loops = (size / sizeof(uint32_t));
    for(int index = 0; index < loops; ++index)
    {
        *((uint32_t*)pdest) = *((uint32_t*)psrc);
        pdest += sizeof(uint32_t);
        psrc += sizeof(uint32_t);
    }

    loops = (size % sizeof(uint32_t));
    for (int index = 0; index < loops; ++index)
    {
        *pdest = *psrc;
        ++pdest;
        ++psrc;
    }
}
于 2012-08-09T04:00:10.797 回答
13

他们要求您优化您的实现，并让它在循环内一次复制一个 32 位字，而不是一次复制一个字节。这将需要仔细检查以处理边界情况，例如size不是 4 的倍数，dest或者src未在 4 字节边界上对齐。

于 2012-08-09T03:31:10.600 回答
1

出于某种原因，面试官要求您执行过早的优化。这通常是个坏主意。

确实，32 位机器复制一个 32 位卡盘比复制 4x1 字节快。但优化远不止这些。

32 位机器很有可能将您的数据放入高速缓存内存中，然后突然快速的内存访问可能比 CPU 指令更相关。高速缓存存储器可能有各种对齐要求。他们可能更喜欢普通的循环，或者他们可能更喜欢 32 位对齐的块。我不是这方面的专家，所以我避免过早优化并将其留给编译器，希望编译器比我更了解高速缓存。

然后是 CPU 分支预测和指令管道。这个特定的代码是相当确定的，所以这可能不是问题。但作为经验法则：简单代码比复杂代码产生更有效的分支预测。

此外，还有除法，这在许多 CPU 架构上很慢。根据要复制的数据量，划分可能会导致 memcpy 慢得多。

总结一下：手动优化是相当复杂的，需要对CPU和硬件有深入的了解。您不能也不应该“针对 32 位 CPU 进行优化”，您需要了解具体情况。在大多数情况下，编译器会比您更有效地优化代码。特别是库 memcpy()，通常是用内联汇编程序编写的，针对特定目标进行了优化。

于 2012-08-09T06:41:52.363 回答
1

您的 memcpy 的逻辑是正确的，并且您的面试官没有要求您更改它或添加限制。一次复制 4 个字节会更快，但如果您的大小不是 4 的倍数，就会出现问题。因此面试官告诉您使用两个循环：第一个循环一次复制 4 个字节，第二个循环一个字节一次时间（最多迭代 3 次）。

所以大部分的拷贝是用快速的 4 字节拷贝完成的，但你不限于大小为 4 的倍数，因为第二个“清理”循环将复制任何不是 4 的倍数的东西。

第一个循环：复制 uint32_t 并递增 4
第二个循环：复制 uint8_t 并递增 1

于 2012-08-09T03:34:57.960 回答
1

面试官正在测试你对计算机体系结构的了解，并希望你优化你的算法。内存操作的是字而不是字节。在 32 位系统中，一个字通常是 4 个字节，读/写 1 个字节所用的时间与读/写 1 个字所用的时间相同。第二个循环是处理要复制的字节数不能被 4 个字节整除的情况。

你真正想要的是3个循环。2 循环用于 dest 之后和 dest+size 之前的字节，当两者都不是字对齐时。然后对中间的所有单词进行另一个循环。

您实际上可以通过利用特定于架构的指令进行更多优化。如果您有兴趣，请查看这篇文章：http ://www.eetimes.com/design/embedded/4024961/Optimizing-Memcpy-improves-speed

于 2012-08-09T03:41:58.290 回答
0

他们希望你加快速度。32 位处理器复制 32 位的速度比复制 8 位的速度快。因此，如果有人想要复制 4 个字节而不是一次复制一个，那么您可以一次完成所有操作。

于 2012-08-09T03:31:35.023 回答
0

看一下这个..

void myMemCpy(void *dest, void *src, size_t n)
{
   // Typecast src and dest addresses to (char *)
   char *csrc = (char *)src;
   char *cdest = (char *)dest;

   // Copy contents of src[] to dest[]
   for (int i=0; i<n; i++)
       cdest[i] = csrc[i];
}

欲了解更多信息

于 2017-04-24T06:34:26.140 回答