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