- 论坛徽章:
- 2
|
------ 理论篇
1. 逐byte
如果是C代码编写的最verbose版本：
- void* memcpy(void* dst, void const* src, size_t n) {
- char *d=dst, *s=src;
- for (;--n; *d++=*s++);
- return dst;
- }
- char* strcpy(char* dst, char const* src) {
- char* d=dst;
- while (*d++=*src++);
- return dst;
- }
- size_t strlen(char const* s) {
- char const* p=s;
- while (*p++);
- return p-s-1;
- }
需要注意的是， gcc -O2和-O3生成的memcpy的代码会很不相同（下面会解释）
具体是什么-O3中的哪个选项触发的这个优化我就不知道了……
2. 多byte
一些memcpy, strcpy, strlen都不是像上面那样逐byte复制或比较， 而是尽可能一次比较一个机器字。
若要按机器字复制， 就需要考虑对齐问题； strxxx还需要考虑0检测问题。
2.1 memcpy
例如memcpy， 若有适当的对齐， 就可以按int32或者int64复制。
gcc -O3 memcpy就会生成： "对齐检测 -> 按适当对齐复制" 的代码， 而不是单纯的逐byte复制。
有适当对齐下： gcc中用int64会比int32更快一些， msvc两者差不多。
2.2 strcpy
strcpy也首先需要计算一个合适的对齐， 然后按最适合的数据类型复制。
它比memcpy要多考虑的一个问题就是0byte检测。
它慢（源代码实现）也慢在这个地方。
memcpy有长度， 所以可以准确知道循环次数。
strcpy没有长度， 0byte检测虽然有较高效的bit算法， 但还是不如和counter比较来得快。
2.3 合适的对齐
memcpy和strcpy需要计算dst和src最合适的复制类型。
例如： dst=16, src=64。
那么两者可以按1、2、4、8、16字节复制。
可以根据平台上的特点， 选择合适的数据类型（比如32位平台上也许没有16字节的整数类型， 8字节不一定比4字节快）
dst=17, src=65， 那么首先复制1个byte， 然后按上面处理。
dst=18, src=66， 那么前2个byte可以一次复制2byte或者复制2次1byte， 看哪个快， 然后按上面处理。
所以， 在最差的情况下， memcpy和strcpy都只能按byte复制， 例如 dst=x, src=x+2^n-1。
而strlen和它们不同的是， strlen只需要考虑一个串的对齐。
在长度足够的情况下， strlen总是可以将两头单独处理， 中间按最高效的整数类型检测。
------ 实际篇
实际情况是：
在i386下， 逐机器字比逐byte快。
即使没有对齐（i386可以处理整数未对齐）速度会降低， 但还是比byte快。
而且i386上有串复制指令。
所以， 比较它们的效率的时候， 需要注意的问题之一就是：
0. 比较libc的版本， 而不是C写的版本。
另外一些问题：
1. 加入对长串的比较
短串可能赚不回处理零碎部分带来的损失。
2. 比较misalignment的情况
这个其实很简单， malloc返回的是对齐的。
dst=malloc( ... );
src=malloc( ... );
xxxcpy(dst+1, src, ... );
就会让xxxcpy很痛苦。
3. 检测cache情况
有些malloc（甚至calloc）的实现在实际访问内存前， 是不会分配物理内存的。
所以， 对先被测试的函数来说总是不公平的， 它会引发多得多的页错误。
比较的不是memcpy和strcpy的比较， 而是它们和页置换算法+memcpy的比较。
可以考虑将相同的动作执行连续执行2（多）次， 取后一次（第2次之后的综合）结果。 |
|
免费注册
发表于 2010-08-05 21:21
发表于 2010-08-05 21:33
