在delphij那看到FreeBSD新的strlen實作。原本的版本很簡單，就一個一個字元比對是否為'\0'，如果是就回傳長度差距，像下面所示。

for (s = str; *s; ++s);
return(s - str);

新的版本想利用現代處理器對word的處理速度比較快的特性來加速，於是提出了一個神奇的演算法可以判斷4個byte中是否有一個byte 為零

(x - 0x01010101) & ~x & 0x80808080

如果4byte其中一個為'\0'，也就是零，以上算式的結果就會不為零，然後最多再比個四次就知道結尾是啥。但是呢，因為c-string 大部份的情況下都在0~127之間所以可以再簡化成
(x - 0x01010101) & 0x80808080

但128 ~255 之間的情況怎麼辦呢？因為最後本來就要檢查到底那一個byte為零，一起作就好，反正很少出現嘛。新的版本就長成這樣。新的版本在字串很短的情況下(小於一個word)會慢二倍，但是大於一個word的情況會快5.2倍)

整個就是很神奇

arrow
arrow
    全站熱搜

    cmchao 發表在 痞客邦 留言(0) 人氣()

    E-mail轉寄