面试中经常考察memcpy和memmov的实现，百度一搜，有很多篇文章，但遗憾的是，很多都是有问题的，并且互相抄来抄去，一起出错。
面试官通过考察memcpy的实现，可以考察应聘者对以下知识点的掌握：
- 内存对齐的理解
- 内存存取粒度与效率的关系
- 内存重叠的问题(memory overlap)
基本实现
#include <stdio.h>
void *memcpy(void *dst, void const *src, size_t size)
{
assert((dst != NULL) && (src != NULL));
unsigned char *pdst = (char*)dst;
unsigned char const *psrc = src;
while(size--)
{
*pdst++ = *psrc++;
}
return dst;
}
基本实现很简单，assert断言的添加可以告诉面试官，我们是有边界条件的控制意识的。尽管许多官方的实现要求程序员自己去注意NULL指针的情况。但我们是在面试，不是嘛！
进一步完善
进一步完善，考虑内存重叠的情况。
首先来一个错误示范，网上很多都是这样实现的。
#include <stdio.h>
void *memcpy(void *dst, const void *src, size_t size)
{
assert((dst != NULL) && (src != NULL));
unsigned char *pdst = dst;
const unsigned char *psrc = src;
if(psrc < pdst)
{
psrc = psrc + size - 1;
pdst = pdst + size - 1;
while(size--) //自后向前
{
*pdst-- = *psrc--;
}
}
else
{
while(size--) //自前向后
{
*pdst++ = *psrc++;
}
}
return dst;
}
通过这段代码可以看到，应聘者是意识到内存重叠的情况，并试图解决的。但实际上，这段代码有一个不算致命的错误：psrc < pdst
错误就在于这两个指针的比较，C语言 the Standard, 6.5.9 规定：如果两个指针都指向同一个数组中的元素，那么它们之间可以执行<、<=、>和>=等关系运算。两个不相关的指针执行关系运算，其结果是未定义的。
然而，这段代码又是可以正常工作的，因为无论psrc < pdst结果是什么，都达到了不破坏内存的目的。
因此，作为一个无需太严谨的程序员，可以去这样实现。但如果去参与开发libc库的实现，就不能这么写了，这也许就是官方库实现中没有去检查内存重叠的原因。
就算允许内存重叠情况存在的memmove函数，也没有去判断是否有内存重叠，而是把源操作数复制到一个临时位置，这个临时位置不会与源或目标操作数重叠，再把它从这个临时位置复制到目标操作数。
其可能的实现大致是这样的：
void *memmove(void *dst, const void *src, size_t size)
{
unsigned char temp[size];
memcpy(temp, src, size);
memcpy(dst, temp, size);
return dst;
}
再进一步完善：存取效率与内存对齐
面试官可能进一步考察内存存取方面的知识。比如这位在Stack Overflow上的提问：Implementing own memcpy (size in bytes?)
我看了glibc-2.28中memcpy的实现，比较复杂。但可以看出考虑内存存取的优化：
void *
memcpy (void *dstpp, const void *srcpp, size_t len)
{
unsigned long int dstp = (long int) dstpp;
unsigned long int srcp = (long int) srcpp;
/* Copy from the beginning to the end. */
/* If there not too few bytes to copy, use word copy. */
if (len >= OP_T_THRES)
{
/* Copy just a few bytes to make DSTP aligned. */
len -= (-dstp) % OPSIZ;
BYTE_COPY_FWD (dstp, srcp, (-dstp) % OPSIZ);
/* Copy whole pages from SRCP to DSTP by virtual address manipulation,
as much as possible. */
PAGE_COPY_FWD_MAYBE (dstp, srcp, len, len);
/* Copy from SRCP to DSTP taking advantage of the known alignment of
DSTP. Number of bytes remaining is put in the third argument,
i.e. in LEN. This number may vary from machine to machine. */
WORD_COPY_FWD (dstp, srcp, len, len);
/* Fall out and copy the tail. */
}
/* There are just a few bytes to copy. Use byte memory operations. */
BYTE_COPY_FWD (dstp, srcp, len);
return dstpp;
}
下面看另一个库实现版本，这个比较容易理解。但是是网友提供的，不知道来源于哪个库：
00018 void *memcpy(void *dst, const void *src, size_t len)
00019 {
00020 size_t i;
00021
00022 /*
00023 * memcpy does not support overlapping buffers, so always do it
00024 * forwards. (Don't change this without adjusting memmove.)
00025 *
00026 * For speedy copying, optimize the common case where both pointers
00027 * and the length are word-aligned, and copy word-at-a-time instead
00028 * of byte-at-a-time. Otherwise, copy by bytes.
00029 *
00030 * The alignment logic below should be portable. We rely on
00031 * the compiler to be reasonably intelligent about optimizing
00032 * the divides and modulos out. Fortunately, it is.
00033 */
00034
00035 if ((uintptr_t)dst % sizeof(long) == 0 &&
00036 (uintptr_t)src % sizeof(long) == 0 &&
00037 len % sizeof(long) == 0) {
00038
00039 long *d = dst;
00040 const long *s = src;
00041
00042 for (i=0; i<len/sizeof(long); i++) {
00043 d[i] = s[i];
00044 }
00045 }
00046 else {
00047 char *d = dst;
00048 const char *s = src;
00049
00050 for (i=0; i<len; i++) {
00051 d[i] = s[i];
00052 }
00053 }
00054
00055 return dst;
00056 }
35~36行，判断dst与src是否以内存对齐方式存储的，对齐值为sizeof(long)。
37行，判断需要读取的字节数是否是sizeof(long)的整数倍。
如果以上两个条件都满足，以sizeof(long)字节为单位进行内存存取。这样效率比单字节存取效率高的多。
46~53行，是上述条件不满足的情况下，执行单字节存取。
内存对齐、内存存取粒度与效率的关系，可见我的博文：内存对齐相关问题的简要总结
根据上面的代码再进一步优化，比如当前是四字节对齐，那么将需要复制的字节数n拆为两部分，一部分是四字节的整数倍(n/4)，一部分不足四字节(n%4)。
当dst与src都按照四字节对齐时，前者按照四字节存取，后者按照单字节存取。否则，都按照单字节存取。代码如下：
#include <stdio.h>
//假设内存存取粒度是align = sizeof(unsigned int)字节
void *mymemcpy(void *dst, void const *src, size_t n)
{
size_t div = n / sizeof(unsigned int); //有多少个align字节
size_t rem = n % sizeof(unsigned int); //不足align字节的部分
unsigned char *pdst = dst;
unsigned char const *psrc = src;
if((unsigned int)dst % sizeof(unsigned int) == 0 && // 是否align字节对齐
(unsigned int)src % sizeof(unsigned int) == 0 )
{
for(size_t i = 0; i < div; ++i)
{
*((unsigned int *)pdst) = *((unsigned int*)psrc);//align字节存取
pdst += sizeof(unsigned int); //按align字节移动单字节指针。
psrc += sizeof(unsigned int);
}
for(size_t i = 0; i < rem; ++i) //单字节存取
*pdst++ = *psrc++;
}
else
{
for(size_t i = 0; i < n; ++i) //单字节存取
{
*pdst++ = *psrc++;
}
}
return dst;
}
以上总结，如有错误或不足，欢迎指正。
网友评论