聊聊 memcpy
PT
Sent to you by PT via Google Reader:
嗯 .. 提到 memcpy 你是不是就条件反射的想到了这样的东西呢：
void * memcpy(void * dst, const void * src, size_t size) { size_t i=0; for(; i<size; ++i) { dst[i] = src[i]; } return dst; }
其实吧，memcpy 里面还是很有学问的 ... 首先从一个新闻说起吧
最近某个由 memcpy 引发的血案似乎引起了不少人关注，事情大概是 glibc 使用了一个号称经过优化的 memcpy 函数，这个函数对源地址和目标地址 重叠 的情况没有处理（虽然实际上 memcpy 函数也不要求处理这种情况），于是 Adobe Flash Player 闹情绪了，原因在于那个 tricky 的 memcpy 函数作风比较诡异，在某些机器上它是把数据 从后往前 拷贝的，对此 Linus 的评价是：
That said - why the heck would you ever do memcpy() backwards? Things like automatic prefetchers usually work better for the "natural" patterns, so a backwards memcpy is generally a bad thing to do unless you have some active reason for it, like doing a memmove()
不过我其实更觉得这完全是 Adobe 的问题，因为如果从后往前拷贝它就会出问题，那么遇到下面这种情况，从前往后拷贝也可以照样整垮它：
A: bbbbbaaaaa B: aaaaabbbbb memcpy(B,A,10);
Anyway，事情到现在已经基本上算是平息了： glibc 相信问题不在于 memcpy 而在于 Adobe 没有正确使用它，问题不再讨论；Linus 则给出了一个暂行方案，他的那个方案已经非常优秀了以至于想想很有可能破坏掉读者的挑战欲望，所以还是留着过一会儿再说吧……
现在我们回到主题上，memcpy，怎么样让它更快些呢。
首先， dst[i] = src[i] 这一句实际上的效率就相当于 *(dst+i) = *(src+i) ， 这里的加法显得有点太过分了。稍微修改一下下：
void * memcpy(void * dst, const void * src, size_t size) { unsigned char * _dst = dst; const unsigned char * _src = src, * _src_end; for(_src_end = _src+size; _src<_src_end; ++_src, ++_dst) { * _dst = * _src; } return dst; }
Andorid 上面的 libc 似乎就是类似这样的实现了。
但是，其实还不够，拷贝 size 个字节，比较运算就执行了 size 次，可不可以少一点？
答案：Yes!
方案一：Duff's Device
Duff's Device 是个非常 tricky 的东西，以至于你第一眼见到很可能怀疑“这货真能通过编译？”
void * memcpy(void * dst, const void * src, size_t size) { register n=(size+7)/8; register unsigned char * _dst = dst; register const unsigned char * _src = src; switch(size%8){ case 0: do{ *_dst++ = *_src++; case 7: *_dst++ = *_src++; case 6: *_dst++ = *_src++; case 5: *_dst++ = *_src++; case 4: *_dst++ = *_src++; case 3: *_dst++ = *_src++; case 2: *_dst++ = *_src++; case 1: *_dst++ = *_src++; } while(--n>0); } }
这样，被 switch 一次之后便陷入了 do while 循环；这里 case 0 - case 7 如果不够还可以再加， 此段代码相当于把上面的小于比较省掉了 7/8 。
方案二：不要一个字节一个字节操作，而要一个字一个字的处理：
通常一个机器字有好几个字节长 —— 比如 32 位机器上是 4 个字节，64 位机器上是 8 字节。
将每 n 个字节作为一个整体“超级字符”进行操作，在这种场合算是很常见的应用了：
void * memcpy(void * dst, const void * src, size_t size) { void * orig = dst; asm volatile("rep ; movsq" :"=D" (dst), "=S" (src) :"0" (dst), "1" (src), "c" (size >> 3) :"memory"); asm volatile("rep ; movsb" :"=D" (dst), "=S" (src) :"0" (dst), "1" (src), "c" (size & 7) :"memory"); return orig; }
解释一下，这里汇编代码的原理也就是先把 size/8 个字（size>>3）拷贝过去（movsq）， 再把后 size%8 个字节（size&7）拷贝过去（movsb）
这个就是 Linus 给出的临时方案了。
另外这里一个字是八个字节，那是因为这里出现症状的机器是 64 位的。
方案三（其实不算方案三）：结合以上二者
以字为单位，用 Duff's Device 操作…… 这个想想就觉得挺牛的，Newlib 似乎就是这么玩的了：
/* Nonzero if either X or Y is not aligned on a "long" boundary. */ #define UNALIGNED(X, Y) \ (((long)X & (sizeof (long) - 1)) | ((long)Y & (sizeof (long) - 1))) /* How many bytes are copied each iteration of the 4X unrolled loop. */ #define BIGBLOCKSIZE (sizeof (long) << 2) /* How many bytes are copied each iteration of the word copy loop. */ #define LITTLEBLOCKSIZE (sizeof (long)) /* Threshhold for punting to the byte copier. */ #define TOO_SMALL(LEN) ((LEN) < BIGBLOCKSIZE) _PTR _DEFUN (memcpy, (dst0, src0, len0), _PTR dst0 _AND _CONST _PTR src0 _AND size_t len0) { #if defined(PREFER_SIZE_OVER_SPEED) || defined(__OPTIMIZE_SIZE__) char *dst = (char *) dst0; char *src = (char *) src0; _PTR save = dst0; while (len0--) { *dst++ = *src++; } return save; #else char *dst = dst0; _CONST char *src = src0; long *aligned_dst; _CONST long *aligned_src; /* If the size is small, or either SRC or DST is unaligned, then punt into the byte copy loop. This should be rare. */ if (!TOO_SMALL(len0) && !UNALIGNED (src, dst)) { aligned_dst = (long*)dst; aligned_src = (long*)src; /* Copy 4X long words at a time if possible. */ while (len0 >= BIGBLOCKSIZE) { *aligned_dst++ = *aligned_src++; *aligned_dst++ = *aligned_src++; *aligned_dst++ = *aligned_src++; *aligned_dst++ = *aligned_src++; len0 -= BIGBLOCKSIZE; } /* Copy one long word at a time if possible. */ while (len0 >= LITTLEBLOCKSIZE) { *aligned_dst++ = *aligned_src++; len0 -= LITTLEBLOCKSIZE; } /* Pick up any residual with a byte copier. */ dst = (char*)aligned_dst; src = (char*)aligned_src; } while (len0--) *dst++ = *src++; return dst0; #endif /* not PREFER_SIZE_OVER_SPEED */ }
方案四，有请硬件牛
翻出 glibc 2.9 的代码，它的代码看上去倒是不长：
void * memcpy (dstpp, srcpp, len) 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; }
从注释可以看出，现在它在玩的都是些硬件上的 trick 了 (更别提 Linux Kernel 中的那些对应不同处理器的汇编实现)，于是我发现我似乎不太适合再继续挖下去了。
文章最后，我想以高中语文考试作文体结尾，非常感谢所有这些 —— hacker 也好 geek 也好 —— 做了这么多有意思又有意义的工作， 让我们有 Linux 这么优秀的操作系统可以用；正是由于这样的细节，这样的竞争气氛，这一点一滴的积累，才有了（ 我自己的测试中 ）比 Win7 快上近 1/3 的速度，让人没有理由再质疑开源的力量。
相关阅读
本文网址:http://www.if-yu.info/2010/11/16/about-memcpy.html
Things you can do from here:
- Subscribe to IF's using Google Reader
- Get started using Google Reader to easily keep up with all your favorite sites
