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