Categories
程式開發

如何使用SSE2指令集加速字符替換


導語

我們在寫代碼的時候,在字符串處理的時候,可能會遇到這樣的需求,就是把一個目標字符串中所有出現的某個字符 a 替換為另外一個字 c.

比如對於Yaf_Loader中,在處理命名空間的類名的自動加載的時候,我需要把所有的 替換為 _ ,一般通常的寫法會是:

如何使用SSE2指令集加速字符替換 1

SSE2如何加速

而目前SIMD指令的支持已經非常普遍,尤其 SSE2,基本當代的CPU都支持, 可以通過 cat /proc/cpuinfo 來看cpu支持的SIMD指令集:

如何使用SSE2指令集加速字符替換 2

可見我的這個CPU支持 mmxssesse2ssse3sse4.1sse4.2avx.

回到正題,我們知道 SIMD 128 指令集可以一次處理 16 個字符,上面的代碼可以通過如下代碼來等效實現:

如何使用SSE2指令集加速字符替換 3

這裡面核心的代碼部分是:

如何使用SSE2指令集加速字符替換 4

我來一行一行解釋,假設我們現在要處理的字符串是”GNamespacepackageclassname

  • 第一行:拿 16 個字符和字符 ‘’ 做比較,如果某位相等,則 16 位結果中對應的 byte 就為 0xff(-1),否則就為 0,那麼對於:

    如何使用SSE2指令集加速字符替換 5

    來說,會得到結果:

    如何使用SSE2指令集加速字符替換 6

  • 第二行:如果對比的結果不全為零的話,就進行到這行,這行的核心思想是因為ascii 碼 ‘_’(95)‘’(92) 之間差了 3,所以我們通過and指令得到如下結果:

    如何使用SSE2指令集加速字符替換 7

  • 第三行:我們把剛剛的 delta 結果加回到原始字符串中去,也就是:

    如何使用SSE2指令集加速字符替換 8

  • 第四行:把結果寫回內存

總結

這樣一來,我就可以用一條指令同時檢測 16 個字符,效率會大大提升。我們來做個簡單的測試,測試腳本在這裡是:replace_chr.c(閱讀原文可見)

下載下來以後,用 -O2 編譯,在我的開發機上跑的結果是(結果會根據字符串中出現 ‘’ 的位置和數量不同而有些許差異):

如何使用SSE2指令集加速字符替換 9

從結果上可以看到,在字符串長度小於 16 的時候,SSE2 版本的速度略遜於普通版本,但是當字符串長度大於 16以後,SSE2 的版本的優勢就非常明顯了。

附言

與其說是針對這個特定的字符替換的問題,我其實更主要對是想分享這種使用 SIMD 解決問題的思路,如何把類似的問題抽象為這樣的”批量操作”。比如在之前在開發 PHP7 的時候,我也為 PHP7 引入過採用 SIMD 指令來實現快速的base64_encode/decode函數,這個性能提升很明顯,因為被操作的字符串一般都很長,有興趣的伙伴可以參看Base64 Encode with SSSE3(閱讀原文可見) , 以後有機會也可以分享下那個例子是怎麼做的。

最後,關於 SIMD 指令集的速查,可以看這裡:Intel Intrinsics Guide

本文轉載自公眾號貝殼產品技術。

原文鏈接

https://mp.weixin.qq.com/s?__biz=MzIyMTg0OTExOQ==&mid=2247485398&idx=1&sn=f698839b2c54609d7d0b27dc7b43fa1a&chksm=e83734a6df40bdb0f08249a69252db4bb7c758158ff243ce03e99fe2333780f9ca2268712370&scene=27#wechat_redirect