over 9 years ago

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倍)

整個就是很神奇

← 2009 雪訓室內課第三課:雪地行進與固定點架設 音樂小記 2009 02 →