學(xué)習(xí)高效編程的有效途徑之一就是閱讀高手寫(xiě)的源代碼，CRT(C/C++ Runtime Library)作為底層的函數(shù)庫(kù)，實(shí)現(xiàn)必然高效。恰好手中就有g(shù)libc和VC的CRT源代碼，于是挑了一個(gè)相對(duì)簡(jiǎn)單的函數(shù)strlen研究了一下，并對(duì)各種實(shí)現(xiàn)作了簡(jiǎn)單的效率測(cè)試。
strlen的函數(shù)原形如下：
??????size_t strlen(const char *str);
strlen返回str中字符的個(gè)數(shù)，其中str為一個(gè)以'\0'結(jié)尾的字符串(a null-terminated string)。
1. 簡(jiǎn)單實(shí)現(xiàn)
如果不管效率，最簡(jiǎn)單的實(shí)現(xiàn)只需要4行代碼：
1?size_t?strlen_a(const?char?*
str)?{
2?????size_t?length?=?0
;
3?????while?(*str++
)
4?????????++
length;
5?????return
?length;
6?}
也許可以稍加改進(jìn)如下：
1?size_t?strlen_b(const?char?*
str)?{
2?????const?char?*cp?=
?str;
3?????while?(*cp++
)
4?
????????;
5?????return?(cp?-?str?-?1
);
6?}
2. 高效實(shí)現(xiàn)
很顯然，標(biāo)準(zhǔn)庫(kù)的實(shí)現(xiàn)肯定不會(huì)如此簡(jiǎn)單，上面的strlen_a以及strlen_b都是一次判斷一個(gè)字符直到發(fā)現(xiàn)'\0'為止，這是非常低效的。比較高效的實(shí)現(xiàn)如下(在這里WORD表示計(jì)算機(jī)中的一個(gè)字，不是WORD類型)：
(1) 一次判斷一個(gè)字符直到內(nèi)存對(duì)齊，如果在內(nèi)存對(duì)齊之前就遇到'\0'則直接return，否則到(2)；
(2) 一次讀入并判斷一個(gè)WORD，如果此WORD中沒(méi)有為0的字節(jié)，則繼續(xù)下一個(gè)WORD，否則到(3)；
(3) 到這里則說(shuō)明WORD中至少有一個(gè)字節(jié)為0，剩下的就是找出第一個(gè)為0的字節(jié)的位置然后return。
NOTE：
數(shù)據(jù)對(duì)齊(data alignment)，是指數(shù)據(jù)所在的內(nèi)存地址必須是該數(shù)據(jù)長(zhǎng)度的整數(shù)倍，這樣CPU的存取速度最快。比如在32位的計(jì)算機(jī)中，一個(gè)WORD為4 byte，則WORD數(shù)據(jù)的起始地址能被4整除的時(shí)候CPU的存取效率比較高。CPU的優(yōu)化規(guī)則大概如下：對(duì)于n字節(jié)(n = 2,4,8...)的元素，它的首地址能被n整除才能獲得最好的性能。
為了便于下面的討論，這里假設(shè)所用的計(jì)算機(jī)為32位，即一個(gè)WORD為4個(gè)字節(jié)。下面給出在32位計(jì)算機(jī)上的C語(yǔ)言實(shí)現(xiàn)(假設(shè)unsigned long為4個(gè)字節(jié))：
?1?typedef?unsigned?long
?ulong;
?2?
?3?size_t?strlen_c(const?char?*
str)?{
?4?
?5?????const?char?*
char_ptr;
?6?????const?ulong?*
longword_ptr;
?7?
????register?ulong?longword,?magic_bits;
?8?
?9?????for?(char_ptr?=
?str;?((ulong)char_ptr?
10?????????&?(sizeof(ulong)?-?1))?!=?0
;
11?????????++
char_ptr)?{
12?????????if?(*char_ptr?==?'\0'
)
13?????????????return?char_ptr?-
?str;
14?
????}
15?
16?????longword_ptr?=?(ulong*
)char_ptr;
17?
18?????magic_bits?=?0x7efefeffL
;
19?
20?????while?(1
)?{
21?
22?????????longword?=?*longword_ptr++
;
23?
24?????????if?((((longword?+?magic_bits)?^?~longword)?&?~magic_bits)?!=?0
)?{
25?
26?????????????const?char?*cp?=?(const?char*)(longword_ptr?-?1
);
27?
????????????
28?????????????if?(cp[0]?==?0
)
29?????????????????return?cp?-
?str;
30?????????????if?(cp[1]?==?0
)
31?????????????????return?cp?-?str?+?1
;
32?????????????if?(cp[2]?==?0
)
33?????????????????return?cp?-?str?+?2
;
34?????????????if?(cp[3]?==?0
)
35?????????????????return?cp?-?str?+?3
;
36?
????????}
37?
????}
38?}
3. 源碼剖析
上面給出的C語(yǔ)言實(shí)現(xiàn)雖然不算特別復(fù)雜，但也值得花點(diǎn)時(shí)間來(lái)弄清楚，先看9-14行：
for?(char_ptr?=?str;?((ulong)char_ptr?&?(sizeof(ulong)?-?1))?!=?0;?++char_ptr)?{
????if?(*char_ptr?==?'\0')
????????return?char_ptr?-?str;
}
上面的代碼實(shí)現(xiàn)了數(shù)據(jù)對(duì)齊，如果在對(duì)齊之前就遇到'\0'則可以直接return char_ptr - str;
第16行將longword_ptr指向數(shù)據(jù)對(duì)齊后的首地址
longword_ptr?=?(ulong*)char_ptr;
第18行給magic_bits賦值(在后面會(huì)解釋這個(gè)值的意義)
magic_bits?=?0x7efefeffL;
第22行讀入一個(gè)WORD到longword并將longword_ptr指向下一個(gè)WORD
longword?=?*longword_ptr++;
第24行的if語(yǔ)句是整個(gè)算法的核心，該語(yǔ)句判斷22行讀入的WORD中是否有為0的字節(jié)
if?((((longword?+?magic_bits)?^?~longword)?&?~magic_bits)?!=?0)
if語(yǔ)句中的計(jì)算可以分為如下3步：
(1) longword + magic_bits
其中magic_bits的二進(jìn)制表示如下：
??????????????????b3??????b2?????? b1?????? b0
??????????????31------------------------------->0
??magic_bits:?01111110?11111110?11111110?11111111
magic_bits中的31,24,16,8這些bits都為0，我們把這幾個(gè)bits稱為holes，注意在每個(gè)byte的左邊都有一個(gè)hole。
檢測(cè)0字節(jié)：如果longword 中有一個(gè)字節(jié)的所有bit都為0，則進(jìn)行加法后，從這個(gè)字節(jié)的右邊的字節(jié)傳遞來(lái)的進(jìn)位都會(huì)落到這個(gè)字節(jié)的最低位所在的hole上，而從這個(gè)字節(jié)的最高位則永遠(yuǎn)不會(huì)產(chǎn)生向左邊字節(jié)的hole的進(jìn)位。則這個(gè)字節(jié)左邊的hole在進(jìn)行加法后不會(huì)改變，由此可以檢測(cè)出0字節(jié)；相反，如果longword中所有字節(jié)都不為0，則每個(gè)字節(jié)中至少有1位為1，進(jìn)行加法后所有的hole都會(huì)被改變。
為了便于理解，請(qǐng)看下面的例子：
??????????????????b3??????b2?????? b1?????? b0
??????????????31------------------------------->0
??longword:???XXXXXXXX?XXXXXXXX?00000000?XXXXXXXX
+?magic_bits:?01111110?11111110?11111110?11111111
上面longword中的b1為0，X可能為0也可能為1。因?yàn)閎1的所有bit都為0，而從b0傳遞過(guò)來(lái)的進(jìn)位只可能是0或1，很顯然b1永遠(yuǎn)也不會(huì)產(chǎn)生進(jìn)位，所以加法后longword的第16 bit這個(gè)hole不會(huì)變。
(2)? ^ ~longword
這一步取出加法后longword中所有未改變的bit。
(3)? & ~magic_bits
最后取出longword中未改變的hole，如果有任何hole未改變則說(shuō)明longword中有為0的字節(jié)。
根據(jù)上面的描述，如果longword中有為0的字節(jié)，則if中的表達(dá)式結(jié)果為非0，否則為0。
NOTE：
如果b3為10000000，則進(jìn)行加法后第31 bit這個(gè)hole不會(huì)變，這說(shuō)明我們無(wú)法檢測(cè)出b3為10000000的所有WORD。值得慶幸的是用于strlen的字符串都是ASCII標(biāo)準(zhǔn)字符，其值在0-127之間，這意味著每一個(gè)字節(jié)的第一個(gè)bit都為0。因此上面的算法是安全的。
一旦檢測(cè)出longword中有為0的字節(jié)，后面的代碼只需要找到第一個(gè)為0的字節(jié)并返回相應(yīng)的長(zhǎng)度就OK：
const?char?*cp?=?(const?char*)(longword_ptr?-?1);
if?(cp[0]?==?0)
????return?cp?-?str;
if?(cp[1]?==?0)
????return?cp?-?str?+?1;
if?(cp[2]?==?0)
????return?cp?-?str?+?2;
if?(cp[3]?==?0)
????return?cp?-?str?+?3;
4. 另一種實(shí)現(xiàn)?1?size_t?strlen_d(const?char?*str)?{
?2?
?3?????const?char?*char_ptr;
?4?????const?ulong?*longword_ptr;
?5?????register?ulong?longword,?himagic,?lomagic;
?6?
?7?????for?(char_ptr?=?str;?((ulong)char_ptr?
?8?????????&?(sizeof(ulong)?-?1))?!=?0;
?9?????????++char_ptr)?{
10?????????if?(*char_ptr?==?'\0')
11?????????????return?char_ptr?-?str;
12?????}
13?
14?????longword_ptr?=?(ulong*)char_ptr;
15?
16?????himagic?=?0x80808080L;
17?????lomagic?=?0x01010101L;
18?
19?????while?(1)?{
20?
21?????????longword?=?*longword_ptr++;
22?
23?????????if?(((longword?-?lomagic)?&?himagic)?!=?0)?{
24?
25?????????????const?char?*cp?=?(const?char*)(longword_ptr?-?1);
26?????????????
27?????????????if?(cp[0]?==?0)
28?????????????????return?cp?-?str;
29?????????????if?(cp[1]?==?0)
30?????????????????return?cp?-?str?+?1;
31?????????????if?(cp[2]?==?0)
32?????????????????return?cp?-?str?+?2;
33?????????????if?(cp[3]?==?0)
34?????????????????return?cp?-?str?+?3;
35?????????}
36?????}
37?}
上面的代碼與strlen_c基本一樣，不同的是：
magic_bits換成了himagic和lomagic
himagic?=?0x80808080L;
lomagic?=?0x01010101L;
以及?if語(yǔ)句變得比較簡(jiǎn)單了
if?(((longword?-?lomagic)?&?himagic)?!=?0)
if語(yǔ)句中的計(jì)算可以分為如下2步：
(1) longword - lomagic
himagic和lomagic的二進(jìn)制表示如下：
????????????????b3??????b2???????b1???????b0
????????????31------------------------------->0
??himagic:??10000000?10000000?10000000?10000000
? lomagic:??00000001 00000001?00000001?00000001
在這種方法中假設(shè)所有字符都是ASCII標(biāo)準(zhǔn)字符，其值在0-127之間，因此longword總是如下形式：
????????????????b3??????b2???????b1???????b0
????????????31------------------------------->0
??longword:?0XXXXXXX 0XXXXXXX?0XXXXXXX?0XXXXXXX
檢測(cè)0字節(jié)：
如果longword 中有一個(gè)字節(jié)的所有bit都為0，則進(jìn)行減法后，這個(gè)字節(jié)的最高位一定會(huì)從0變?yōu)?；相反，如果longword中所有字節(jié)都不為0，則每個(gè)字節(jié)中至少有1位為1，進(jìn)行減法后這個(gè)字節(jié)的最高位依然為0。
?(2)? & himagic
這一步取出每個(gè)字節(jié)最高位的1，如果有任意字節(jié)最高位為1則說(shuō)明longword中有為0的字節(jié)。
根據(jù)上面的描述，如果longword中有為0的字節(jié)，則if中的表達(dá)式結(jié)果為非0，否則為0。
5. 匯編實(shí)現(xiàn)
VC CRT的匯編實(shí)現(xiàn)與前面strlen_c算法類似
??1?????????page????,132
??2?????????title???strlen?-?return?the?length?of?a?null-terminated?string
??3?;***
??4?;strlen.asm?-?contains?strlen()?routine
??5?;
??6?;???????Copyright?(c)?Microsoft?Corporation.?All?rights?reserved.
??7?;
??8?;Purpose:
??9?;???????strlen?returns?the?length?of?a?null-terminated?string,
?10?;???????not?including?the?null?byte?itself.
?11?;
?12?;*******************************************************************************
?13?
?14?????????.xlist
?15?????????include?cruntime.inc
?16?????????.list
?17?
?18?page
?19?;***
?20?;strlen?-?return?the?length?of?a?null-terminated?string
?21?;
?22?;Purpose:
?23?;???????Finds?the?length?in?bytes?of?the?given?string,?not?including
?24?;???????the?final?null?character.
?25?;
?26?;???????Algorithm:
?27?;???????int?strlen?(const?char?*?str)
?28?;???????{
?29?;???????????int?length?=?0;
?30?;
?31?;???????????while(?*str++?)
?32?;???????????????????++length;
?33?;
?34?;???????????return(?length?);
?35?;???????}
?36?;
?37?;Entry:
?38?;???????const?char?*?str?-?string?whose?length?is?to?be?computed
?39?;
?40?;Exit:
?41?;???????EAX?=?length?of?the?string?"str",?exclusive?of?the?final?null?byte
?42?;
?43?;Uses:
?44?;???????EAX,?ECX,?EDX
?45?;
?46?;Exceptions:
?47?;
?48?;*******************************************************************************
?49?
?50?????????CODESEG
?51?
?52?????????public??strlen
?53?
?54?strlen??proc?\
?55?????????buf:ptr?byte
?56?
?57?????????OPTION?PROLOGUE:NONE,?EPILOGUE:NONE
?58?
?59?????????.FPO????(?0,?1,?0,?0,?0,?0?)
?60?
?61?string??equ?????[esp?+?4]
?62?
?63?????????mov?????ecx,string??????????????;?ecx?->?string
?64?????????test????ecx,3???????????????????;?test?if?string?is?aligned?on?32?bits
?65?????????je??????short?main_loop
?66?
?67?str_misaligned:
?68?????????;?simple?byte?loop?until?string?is?aligned
?69?????????mov?????al,byte?ptr?[ecx]
?70?????????add?????ecx,1
?71?????????test????al,al
?72?????????je??????short?byte_3
?73?????????test????ecx,3
?74?????????jne?????short?str_misaligned
?75?
?76?????????add?????eax,dword?ptr?0?????????;?5?byte?nop?to?align?label?below
?77?
?78?????????align???16??????????????????????;?should?be?redundant
?79?
?80?main_loop:
?81?????????mov?????eax,dword?ptr?[ecx]?????;?read?4?bytes
?82?????????mov?????edx,7efefeffh
?83?????????add?????edx,eax
?84?????????xor?????eax,-1
?85?????????xor?????eax,edx
?86?????????add?????ecx,4
?87?????????test????eax,81010100h
?88?????????je??????short?main_loop
?89?????????;?found?zero?byte?in?the?loop
?90?????????mov?????eax,[ecx?-?4]
?91?????????test????al,al???????????????????;?is?it?byte?0
?92?????????je??????short?byte_0
?93?????????test????ah,ah???????????????????;?is?it?byte?1
?94?????????je??????short?byte_1
?95?????????test????eax,00ff0000h???????????;?is?it?byte?2
?96?????????je??????short?byte_2
?97?????????test????eax,0ff000000h??????????;?is?it?byte?3
?98?????????je??????short?byte_3
?99?????????jmp?????short?main_loop?????????;?taken?if?bits?24-30?are?clear?and?bit
100?????????????????????????????????????????;?31?is?set
101?
102?byte_3:
103?????????lea?????eax,[ecx?-?1]
104?????????mov?????ecx,string
105?????????sub?????eax,ecx
106?????????ret
107?byte_2:
108?????????lea?????eax,[ecx?-?2]
109?????????mov?????ecx,string
110?????????sub?????eax,ecx
111?????????ret
112?byte_1:
113?????????lea?????eax,[ecx?-?3]
114?????????mov?????ecx,string
115?????????sub?????eax,ecx
116?????????ret
117?byte_0:
118?????????lea?????eax,[ecx?-?4]
119?????????mov?????ecx,string
120?????????sub?????eax,ecx
121?????????ret
122?
123?strlen??endp
124?
125?????????end
6. 測(cè)試結(jié)果為了對(duì)上述各種實(shí)現(xiàn)的效率有一個(gè)大概的認(rèn)識(shí)，我在VC8和GCC下分別進(jìn)行了測(cè)試，測(cè)試時(shí)均采用默認(rèn)優(yōu)化方式。下面是在GCC下運(yùn)行幾百萬(wàn)次后的結(jié)果(在VC8下的運(yùn)行結(jié)果與此相似)：
strlen_a
--------------------------------------------------
???????1:????????515?ticks?????????0.515?seconds
???????2:????????375?ticks?????????0.375?seconds
???????3:????????375?ticks?????????0.375?seconds
???????4:????????375?ticks?????????0.375?seconds
???????5:????????375?ticks?????????0.375?seconds
???total:???????2015?ticks?????????2.015?seconds
?average:????????403?ticks?????????0.403?seconds
--------------------------------------------------
strlen_b
--------------------------------------------------
???????1:????????360?ticks??????????0.36?seconds
???????2:????????390?ticks??????????0.39?seconds
???????3:????????375?ticks?????????0.375?seconds
???????4:????????360?ticks??????????0.36?seconds
???????5:????????375?ticks?????????0.375?seconds
???total:???????1860?ticks??????????1.86?seconds
?average:????????372?ticks?????????0.372?seconds
--------------------------------------------------
strlen_c
--------------------------------------------------
???????1:????????187?ticks?????????0.187?seconds
???????2:????????172?ticks?????????0.172?seconds
???????3:????????187?ticks?????????0.187?seconds
???????4:????????187?ticks?????????0.187?seconds
???????5:????????188?ticks?????????0.188?seconds
???total:????????921?ticks?????????0.921?seconds
?average:????????184?ticks????????0.1842?seconds
--------------------------------------------------
strlen_d
--------------------------------------------------
???????1:????????172?ticks?????????0.172?seconds
???????2:????????187?ticks?????????0.187?seconds
???????3:????????172?ticks?????????0.172?seconds
???????4:????????187?ticks?????????0.187?seconds
???????5:????????188?ticks?????????0.188?seconds
???total:????????906?ticks?????????0.906?seconds
?average:????????181?ticks????????0.1812?seconds
--------------------------------------------------
strlen
--------------------------------------------------
???????1:????????187?ticks?????????0.187?seconds
???????2:????????172?ticks?????????0.172?seconds
???????3:????????188?ticks?????????0.188?seconds
???????4:????????172?ticks?????????0.172?seconds
???????5:????????187?ticks?????????0.187?seconds
???total:????????906?ticks?????????0.906?seconds
?average:????????181?ticks????????0.1812?seconds
--------------------------------------------------
源代碼：
點(diǎn)擊下載