為了效率，我們可以用的招數 之 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 位是一樣的，只不過位數增加了。
