实现自己的memcpy（以字节为单位的大小？）

Question

实现自己的memcpy（以字节为单位的大小？）

10

最近我参加了一次面试，其中需要我实现memcpy函数。由于我的经验中使用了大量memcpy函数，所以这似乎不是一个难题。

因此，我开始实现一个循环，从指针到指针逐个复制地址，类似于以下代码：

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

然而，面试官打断了我指出memcpy的man page上说它“从src复制n个字节到dest”（后来我证实了这一点），然后想让我通过size/4进行迭代，再用另一个循环来处理剩下的index < 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个字节”，而实际上并非如此？我在这里看不清楚什么？

- VaporwareWolf

9

附注：您无法对“void*”进行解引用操作。 - Marcelo Cantos

原型应该是 void memcpy (void* dest, const void* src, size_t size);。如果需要与C标准的memcpy()兼容，它应该返回一个void*。 - Lundin

@Lundin：小修正，我认为您在这里打错了，原型应为“void* memcpy (void* dest, const void* src, size_t size);”。 - Rndp13

@Rndp13 请仔细阅读整个评论。准确来说，标准的 C 原型是 void* memcpy (void*restrict s1, const void*restrict s2, size_t n);。 - Lundin

7个回答

13

他们要求你优化你的实现，在循环中一次性复制32位字，而不是逐个字节地操作。这将需要进行一些仔细的检查来处理边界情况，例如 size 不是4的倍数，或者 dest 或 src 没有对齐到4字节边界。

- John Kugelman

但是"dest[index] = src[index];"不仅仅复制一个字节。我意识到void不能被解引用，所以假设src和dest是int。该操作不仅复制一个字节，而是复制整个32位的整数。在32位机器上，每个地址可以有32位的数据，对吗？我不理解。 - VaporwareWolf

1

小问题：dest和src不必对齐。它们可以被同样的数量错位，尽管当然你必须特殊处理前几个字节以及最后几个字节。 - Marcelo Cantos

@HCHogan：由于您将类型声明为void*，大多数阅读您问题的人都认为您指的是char*，这是一个天真的memcpy的通常选择。这就是为什么John建议您一次复制一个字节。 - Marcelo Cantos

1

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

因此，大部分复制是通过快速的4字节复制完成的，但你不受大小为4的倍数的限制，因为第二个“清理”循环将复制任何不是4的倍数的内容。

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

- Adam

即使要复制的总数据是4字节的倍数，仍可能存在问题。第一个指针可能指向形式为4N+1的字节地址，而第二个指针可能指向形式为4N+2的字节地址；在这种情况下，很难进行4字节的倍数复制。 - Jonathan Leffler

1

面试官要求你进行过早的优化，出于某种原因。通常这是一个不好的想法。

32位机器复制一个32位块比复制4个1字节要快。但是优化不仅仅是这样。

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

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

此外，除法在许多CPU架构上都很慢。根据要复制的数据量，除法可能导致memcpy变得更慢。

总之，手动优化非常复杂，需要深入了解CPU和硬件。你不能也不应该“为32位CPU进行优化”，你需要知道具体情况。在大多数情况下，编译器将比你更有效地优化代码。特别是库memcpy()通常是用内联汇编语言编写的，针对特定目标进行了优化。

- Lundin

2

有足够经验的人会知道，缓存也是按照甚至更粗的边界对齐的。16字节是一个常见的值。"除法"同样是一个误导。将一个常数除以2的幂次方在实际上是免费的，因为它只是一个位移(>>2)。 - MSalters

0

他们希望你加快速度。一个32位处理器可以比复制8位更快地复制32位。因此，如果有人想要复制4个字节而不是逐个复制，则可以一次性完成。

- dave

但是"dest[index] = src[index];"复制整个寄存器，而不仅仅是一个字节。（假设我将函数签名从void更改为int）。 - VaporwareWolf

但是你的循环有问题，复制的字节数是你想要的4倍。他们忽略了类型问题（因为这很容易解决，并不是他们在面试中想从你那里找出的东西....） - dave

0

面试官测试了您的计算机架构知识，并希望您优化算法。内存操作是按字而不是字节进行的。在32位系统中，一个字通常为4个字节，读/写1个字节所需的时间与读/写1个字相同。第二个循环是处理要复制的字节数不是恰好可被4字节整除的情况。

实际上，您需要3个循环。2个循环用于在dest和dest+size之间的字节中，当任何一个都不是字对齐时使用。然后，另一个循环用于介于两者之间的所有字。

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

- Yunchi

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];
}

了解更多信息

- parasrish

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Remy Lebeau · Accepted Answer

正如其他人所说，每次复制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;
    }
}