为了效率，我们可以用的招数 之 strlen
如果要你写一个计算字符串长度的函数 strlen，应该怎么写？相信你很容易写出如下实现：
1 int strlen_1(const char* str) { 2 int cnt = 0; 3 4 if (NULL == str) { 5 return 0; 6 } 7 8 while (*str != '\0') { 9 cnt++; 10 str++; 11 } 12 return cnt; 13 }
那么，它的运行情况怎么样？写段代码测试一下：
1 const char* strs[] = { 2 NULL, 3 "", 4 "1", 5 "12", 6 "123", 7 "012345678901234567890" 8 "012345678901234567890" 9 "012345678901234567890" 10 "012345678901234567890" 11 "012345678901234567890" 12 "012345678901234567890" 13 "012345678901234567890" 14 "012345678901234567890" 15 "012345678901234567890" 16 "012345678901234567890" 17 }; 18 19 int main() 20 { 21 int arrSize = sizeof(strs) / sizeof(char*); 22 for (int i = 0; i < arrSize; i++) { 23 printf("%5d: %10d\n", i, strlen_1(strs[i])); 24 } 25 26 return 0; 27 }
运行结果如下：
我们得到了正确结果，但是这样就够了吗？写代码，尤其是经常被调用的代码，效率是一个很重要的考虑方面，我们的 strlen_1 的效率如何呢？为了测试效率，我们测量一个100M 个字符的超长的字符串。编辑如下测试代码:
1 typedef size_t(*pStrLen)(const char* str); 2 void testProf( 3 pStrLen sl, 4 const char* testName, 5 const char* str) { 6 7 long start = GetTickCount64(); 8 long end = 0; 9 10 int len = sl(str); 11 12 end = GetTickCount64(); 13 14 printf( 15 "%s, start: %ld, end: %ld, total: %ld, result: %d\n", 16 testName, 17 start, 18 end, 19 end - start, 20 len 21 ); 22 } 23 24 void testLen(pStrLen sl, const char* name) { 25 int arrSize = sizeof(strs) / sizeof(char*); 26 puts("------------------------------------------"); 27 puts(name); 28 puts("\n"); 29 30 for (int i = 0; i < arrSize; i++) { 31 printf("%5d: %10d\n", i, strs[i] == NULL ? 0 : sl(strs[i])); 32 } 33 }
修改主程序如下：
// 100M #define STR_SIZE 100000000 int main() { char* str = (char*)malloc(sizeof(char) * STR_SIZE); if (str == NULL) { return -1; } memset(str, 'a', STR_SIZE - 1); str[STR_SIZE - 1] = '\0'; testLen(strlen_1, "strlen_1"); testProf(strlen_1, "strlen_1", str); free((void*)str); return 0; }
得到结果如下（为了去除debug信息的影响，这里使用 release x86 编译，以下同）：
耗时94ms，时间有点长啊，可以优化吗?考虑到我们只需要计算开始和结束地址之间的差，就得到了长度，那么如果省略计数变量，改成如下会不会好些？
1 size_t strlen_2(const char* str) { 2 const char* eos = str; 3 if (NULL == eos) { 4 return 0; 5 } 6 while (*eos) { 7 eos++; 8 } 9 return (eos - str); 10 }
添加 strlen_2 的测试，修改主程序如下：
1 // 100M 2 #define STR_SIZE 100000000 3 int main() 4 { 5 char* str = (char*)malloc(sizeof(char) * STR_SIZE); 6 7 if (str == NULL) { 8 return -1; 9 } 10 11 memset(str, 'a', STR_SIZE - 1); 12 str[STR_SIZE - 1] = '\0'; 13 14 testLen(strlen_1, "strlen_1"); 15 testLen(strlen_2, "strlen_2"); 16 17 testProf(strlen_1, "strlen_1", str); 18 testProf(strlen_2, "strlen_2", str); 19 20 free((void*)str); 21 22 return 0; 23 }
运行一下，得到如下结果：
看起来有一些效果，但这就够了吗？那么系统自带的 strlen 函数效果怎么样呢？新增 strlen 的测试代码:
1 testLen(strlen_1, "strlen_1"); 2 testLen(strlen_2, "strlen_2"); 3 testLen(strlen, "strlen"); 4 5 testProf(strlen_1, "strlen_1", str); 6 testProf(strlen_2, "strlen_2", str); 7 testProf(strlen, "strlen", str);
运行结果如下：
哇，居然快了4倍(63/15=4.2)，那就要了解下系统自带strlen的实现了，经过查找，找到系统 strlen 的汇编代码如下：
1 public strlen 2 3 strlen proc \ 4 buf:ptr byte 5 6 OPTION PROLOGUE:NONE, EPILOGUE:NONE 7 8 .FPO ( 0, 1, 0, 0, 0, 0 ) 9 10 string equ [esp + 4] 11 12 mov ecx,string ; ecx -> string 13 test ecx,3 ; test if string is aligned on 32 bits 14 je short main_loop 15 16 str_misaligned: 17 ; simple byte loop until string is aligned 18 mov al,byte ptr [ecx] 19 add ecx,1 20 test al,al 21 je short byte_3 22 test ecx,3 23 jne short str_misaligned 24 25 add eax,dword ptr 0 ; 5 byte nop to align label below 26 27 align 16 ; should be redundant 28 29 main_loop: 30 mov eax,dword ptr [ecx] ; read 4 bytes 31 mov edx,7efefeffh 32 add edx,eax 33 xor eax,-1 34 xor eax,edx 35 add ecx,4 36 test eax,81010100h 37 je short main_loop 38 ; found zero byte in the loop 39 mov eax,[ecx - 4] 40 test al,al ; is it byte 0 41 je short byte_0 42 test ah,ah ; is it byte 1 43 je short byte_1 44 test eax,00ff0000h ; is it byte 2 45 je short byte_2 46 test eax,0ff000000h ; is it byte 3 47 je short byte_3 48 jmp short main_loop ; taken if bits 24-30 are clear and bit 49 ; 31 is set 50 51 byte_3: 52 lea eax,[ecx - 1] 53 mov ecx,string 54 sub eax,ecx 55 ret 56 byte_2: 57 lea eax,[ecx - 2] 58 mov ecx,string 59 sub eax,ecx 60 ret 61 byte_1: 62 lea eax,[ecx - 3] 63 mov ecx,string 64 sub eax,ecx 65 ret 66 byte_0: 67 lea eax,[ecx - 4] 68 mov ecx,string 69 sub eax,ecx 70 ret 71 72 strlen endp
简单说明如下：
12 – 14 行，判断ecx 指针是否4字节对齐,如果4字节对齐，就跳转到 主循环，否则就进入str_misaligned 循环；
16 – 23 行，逐字节读取字符并判断是否为 ‘\0’,如果找到 ‘\0’,就跳转到第 51 行(byte_3)，计算地址差（即为字符串长度），并返回；如果没有找到 ‘\0’ 字符并且地址已经四字节对齐，就继续执行主循环（29行);
29 – 49 行，是程序主循环，逻辑可用 C 描述为：
1 // 已经32位对齐 2 int* eos = (int*)c; 3 int val = 0; 4 while (true) { 5 val = *eos; 6 int ad = val + 0x7efefeff; 7 val ^= -1; // 0b 1111 1111 1111 1111 1111 1111 1111 1111 8 val ^= ad; 9 eos++; 10 if (!(val & 0x81010100)) { 11 continue; 12 } 13 val = *(eos - 1); 14 if ((val & 0x000000ff) == 0) { 15 return (int)eos - (int)str - 4; 16 } 17 18 if ((val & 0x0000ff00) == 0) { 19 return ((int)eos - (int)str) - 3; 20 } 21 22 if ((val & 0x00ff0000) == 0) { 23 return ((int)eos - (int)str) - 2; 24 } 25 26 if ((val & 0xff000000) == 0) { 27 return ((int)eos - (int)str) - 1; 28 } 29 // taken if bits 24-30 are clear and bit 31 is set 30 }
其中，每次读取，均读取四字节，且一次性进行是否包含 ‘\0’ 的判断，减少操作次数位逐个字节读取的 1/4，怪不得速度上也是快了四倍左右。
那么，系统strlen是怎样一次判断四个字节呢？我们注意到两个特殊值，0x7efefeff 和 0x81010100，那么为什么可以用这两个值判断是否包含 ‘\0’ 呢？我们看看这两个值得二进制表示：
我们看看第一步操作:
1 int ad = val + 0x7efefeff;
我们把四个字节和 0x7efefeff 这个值相加了，如果 val 的最后一个字节不为0，则会向上一个字节产生一个进位，从而导致 ad 的倒数第二个字节的最后一位不为0，则倒数第二个字节就会变成 1111 1111 的状态，第二个字节同理，如果不为0，则会补充倒数第三个字节，最后，倒数第三个字节又会补充第一个字节；这就导致，在每个字节都不为 0 的前提下，ad 每个字节的最低位肯定和 0x7efefeff 与 val 值相加对应位的本应值相反（因为产生了进位，如果当前字节相加结果的最低位为1，则因为上一个字节的进位，则最低位会变成0，如果结果的最低位为0，则因为进位，最低位为1）；
我们再看第二步，val值异或 -1，这里实际上是将 val 值得各个位取反，然后再用 val 值得取反结果异或 ad; 从上一步分析我们可以知道，如果第一步从字符串取到的 4 个字节均不为 0，则经过操作，ad对应字节的最低位肯定和原始值相反，这里拿 val 值的取反结果异或 ad，则在四字节均不为 0 的情况下，各个字节的最低位肯定为0；
最后一步，拿第二步获取到的结果和 0x81010100 相与(test)，则因为上一步获取到的值最低位在取到四字节均不为0的情况下，最低位肯定为 0，所以如果 val & 0x81010100 为 0，则说明四字节均不为0(即’\0′)；
其他步骤就好说了，读取四字节，并一次判断各个字节的值是否为 0,如果为 0，则计算结果并返回。
最后，编辑 strlen_3 如下：
1 size_t __cdecl strlen_3(const char* str) { 2 if (NULL == str) { 3 return 0; 4 } 5 6 const char* c = str; 7 8 while (((int)c) & 3) { 9 if (*c == '\0') { 10 return c - str; 11 } 12 c++; 13 } 14 15 // 已经32位对齐 16 int* eos = (int*)c; 17 int val = 0; 18 while (true) { 19 val = *eos; 20 int ad = val + 0x7efefeff; 21 val ^= -1; // 0b 1111 1111 1111 1111 1111 1111 1111 1111 22 val ^= ad; 23 eos++; 24 if (!(val & 0x81010100)) { 25 continue; 26 } 27 val = *(eos - 1); 28 if ((val & 0x000000ff) == 0) { 29 return (int)eos - (int)str - 4; 30 } 31 32 if ((val & 0x0000ff00) == 0) { 33 return ((int)eos - (int)str) - 3; 34 } 35 36 if ((val & 0x00ff0000) == 0) { 37 return ((int)eos - (int)str) - 2; 38 } 39 40 if ((val & 0xff000000) == 0) { 41 return ((int)eos - (int)str) - 1; 42 } 43 // taken if bits 24-30 are clear and bit 31 is set 44 } 45 }
添加并执行测试代码，结果如下：
可以看到，新版本的 strlen 运行时间已经和系统 strlen 一样级别了。
最后，我们再考虑下，这里用的是 32 位系统，如果在 64 位系统上，是否也可以用类似方法呢？答案是肯定的，而且事实上，strlen 的 64 位版本也是这么做的：
可以看到，这里使用的方法和 32 位是一样的，只不过位数增加了。
