最佳化背景
在編程時,循環展開注重於利用批量處理,減少總處理分支數。而在串列複製數據時,當總循環次數無法被展開後循環的增量整除時,一般就用直接跳轉到展開後循環體中部的方式,完成剩餘數據的複製流程。
因此,根據循環展開的思想,針對串列複製數據的需要,湯姆·達夫以每次疊代時賦最多8個值的方式,用C語言寫出了一個最佳化實現,成功最佳化了串列複製的效率。
原版代碼
若要將數組元素複製進存儲器映射輸出暫存器,較為直接的做法如下所示 :
達夫洞察到,若在這一過程中將一條switch和一個循環相結合,則可展開循環,實現如下所示:
實現機制
達夫設備基於彙編語言編程中常用的“在複製時最小化判斷數和分支數”所用算法,並以C語言實現。代碼看起來雖與環境格格不入,但仍可與C兼容,其因有二:
一方面,C語言對switch語句的規範較松。達夫設備發明時,正值《C程式設計語言》第一版引領C語言規範,而按其中規定,在switch控制語句內,條件標號(case)可以出現在任意子語句之前,充作其前綴。另外,若未加入break語句,則在switch語句在根據條件判定,跳轉到對應標號,並開始執行後,控制流會無視其餘條件標號限定,一直執行到switch嵌套語句的末尾,此即switch語句的“掉落”(fall-through)特性。利用以上特性,這段代碼便可從連續地址中將count個數據複製到存儲器映射輸出暫存器中。
另一方面,C語言對跳轉到循環內部提供了支持,因而此處的switch/case語句便可跳轉到循環內部。
許多C語言編譯器會仿效彙編語言的編程方式,將switch語句轉換為轉移表,從而提高執行效率。在C語言中,switch語句默認的“掉落”特性長期以來亦備受爭議,而達夫也發覺,“這段代碼成為了這一討論中某些觀點的論據,但我不確定到底是支持還是否定(這些觀點)。”
性能表現
從速度上說,由於採用了循環展開技巧,使所需處理的分支數減少,從而降低了在處理分支時,中斷與刷新流水線的巨大運算開銷,因而相較於簡單、直接的循環代碼,這段代碼的執行效率較高。另外,由代碼易知,若不帶switch語句,則這段代碼只能複製8*n個數據項,而若count無法為8整除,則仍有count%8(即count除於8的餘數)項未處理;有鑒於此,此間嵌入了switch/case語句,負責處理剩餘數據。
但是,達夫設備亦有其局限性。在某些環境下,利用switch/case語句處理剩餘數據項,有時並非最優選擇;相對應的,若採用雙循環機制(先實現一個展開後循環,複製8*n個數據項,而後再實現另一循環,複製剩餘數據項),可能反倒更快。究其肇因,則常是由於編譯器無法針對達夫設備進行最佳化,但亦可能是因某些架構的流水線與轉移預測機制有所差異。除此以外,據測試看,當從XFree86 Server 4.0代碼中清理掉所有達夫設備代碼後,執行性能卻大幅提升。因此,若打算使用達夫設備,最好先針對所用的硬體架構、最佳化等級和編譯器對達夫設備進行基準測試,而後再做定奪。
史特勞斯魯普版代碼
原版的達夫設備僅能滿足將數據複製到一個(存儲器映射)暫存器的需求。若要在存儲地址間串列複製數據,則在每次引用指針to時,都需進行一次自增操作,如下所示:
此版代碼摘自比雅尼·史特勞斯特魯普著《C++程式設計語言》一書的“這段代碼有何用?(what does this code do?)”練習部分,而他之所以如此修改,很可能是因考慮到編程新手一般對存儲器映射輸出暫存器一無所知。值得一提的是,針對串列複製的需求,標準C語言庫提供了memcpy函式,而其效率不會比史特勞斯魯普版的達夫設備低,並可能包含了針對特定架構的最佳化,從而進一步大幅提升執行效率。