基于龍芯2F的Glibc庫優化
加入技術交流群
3．2 數據轉換函數
數據轉換函數包括字符串轉換為整數和浮點數。文章分別在每類函數中取一個例子說明優化過程。
字符串轉換為整數包括strtol、strtoul、strtoll等函數，它們分別解析不同的整數類型，支持從2到36的轉換進制。各函數實現上不同的地方僅在于不同類型的整數大小范圍不同，處理流程類似。下面以strtol函數為例介紹優化過程，它的功能為將字符串轉換為long型整數。
Glibc庫中strtol的實現使用普通的逐字節讀取并計算的方式。我們首先對轉換進制分情況處理，對于2的冪次方的進制，如2、4、8、16、32，字符串中的每個數字在二進制位上沒有關聯。可以將它們逐個轉換成二進制位后填入返回值的相應位置，具有較快的轉換速度。其次十進制轉換是一種常用的情況，也將其單獨列出，可以省去對字母進行判斷。
給定進制后，在該進制下整數至多有多少位就可以確定。當字符串中的合法數字個數超過位數限制時，直接返回該類型下的最大值即可。當字符串中的合法數字小于位數限制時，可知解析后的結果絕對不會超過該整數類型的表示范圍，此時我們將字符串進行分段并對解析進程進行循環展開。如果合法數字個數恰好等于位數限制，此時解析結果有超過該類型下最大值的可能性，首先將小于位數限制的部分解析完成后，再考慮最后一位數字。提前確定解析結果的范圍可以避免每次循環內都要對是否超出該類型的最大值進行判斷。
取進制從2到36，字符串的長度從1到該進制下的最大值進行測試，得到各進制下的優化效果如圖1所示，各進制的平均優化比率為30．9％。
strtod、strtof、strtold等函數將字符串轉換為浮點數。我們以strtod函數為例進行介紹，它將字符串轉換為double型浮點數。
Glibc庫中strtod的實現使用高精度計算。首先遍歷整個字符串，找出其中的整數、小數和指數部分，各個部分分別使用高精度計算解析，再將結果合并。對于一般的實現來說，各個部分的取值不會太大，此時使用高精度計算時間消耗較大，改進的實現將每個部分再進行分
塊，對每個分塊使用整數進行解析，實現方式與strtol相同。各個部分的分塊解析完成后，使用一個long double類型作為臨時變量合并解析結果以避免精度丟失，最后將該變量轉換為doulble類型返回。對于strtof函數，使用double類型作為臨時變量。而對于strtold函數，使用上述方法無法保證精度，仍采用原始的實現。
由于雙精度浮點數的有效位數為16至17位，對字符串長度從1到17進行測試，得到各長度下的優化效果如圖2所示，各長度的平均優化比率為49．8％。
3．3 哈希表查找函數
Glibc庫中哈希表所包含的關鍵字和數據分別為字符串和內存塊，其相關的函數包括hcreate，hdestory以及hsearch，分別完成哈希表的創建，銷毀和查找。創建與銷毀操作都是一次性的，我們對查找操作進行優化。
hsearch函數讀入字符串關鍵字作為參數，首先將其映射為整數關鍵值，接著使用雙重散列逐個取出元素進行判斷。
Glibc庫中字符串映射為整數的實現方法為，首先求得字符串的長度作為初值，接著將其不斷左移4位并從末尾到頭部逐個與字符串中的字符相加。該方法需要對字符串進行兩次遍歷，并且當字符串較長時，字符串的長度和進行累加的前幾個字符會被移出而不影響最終的映射值。例如對32位的整型數來說，只有字符串的前8個字符對映射值有影響。
我們使用ELF哈希算法來替換原有的映射實現，此算法不先對字符串求長，僅進行移位和累加操作的循環，為了避免原始實現的缺點，每次循環中都會判斷移位是否超出范圍，如果超出，則把中間結果的高八位異或到低八位上。該哈希函數只需對字符串遍歷一遍，并且考慮了移位越界，避免了只有前幾個字符影響映射值的缺陷。
3．4 加密函數
Glibc庫中的加密函數為crypt函數，該函數單向加密給定的字符串，支持的算法包括MD5、SHA以及DES算法。由于MD5與DES算法的實現流程固定且做了較充分的展開，因此我們主要考慮SHA算法。針對該算法有設計硬件結構進行的優化，而我們的工作從代碼實現角度進行。下面以SHA-256為例說明優化過程，其它SHA算法與之類似。
評論