<<代碼優化:有效使用內存>>代碼優化建議:
1. 展開讀取內存的循環
2. 消除數據相關性
如果請求的RAM單元存在地址數據相關性(也就是說,一個單元含有另一個單元的地址),那么CPU不能并行地處理它們,而在得到地址之前必須等待。消除數據相關性可以提高指令并發度。
3. 同時向存儲控制器發送多個查詢
4. 請求按不少于32個字節的增量方式讀取數據
在于內存進行數據交換的過程中所用的最小數據單位至少是32byte,所以處理速度與處理增量成反比。當增量以1(字節、字或雙字)讀取內存時,由一半的加載單元永遠不會訪問。當以增量4(字節、字或雙字)讀取內存時,僅僅有25%的加載單元會用到,其它的加載單元不會起任何作用。可見,內存中的數據必須盡可能緊密地存放在一起。
5. 使用所有經歷請求的頁面
6. 以一種排除了對相同DRAM頁面進行選取的增量方式來處理數據
7. 對齊數據源地址
8. 組合執行存取內存的代碼
9. 成組進行讀寫操作
10. 僅僅在必要時才放問內存
11. 從不針對特定平臺優化程序。
<<Programming Pearls(Second Edition)>>代碼優化規則:
1. 用空間換取時間規則
1.1 擴展數據結構:通常,通過給結構增加其他信息或改變結構內部的信息讓它訪問的更快能夠減少對數據的常用操作所需的時間。
1.2 存儲預先計算好的結果:計算函數一次,然后存儲計算結果能夠減少昂貴函數的重新計算所需要的成本。以后對該函數的請求就只需要通過查表來完成,而不需要重新計算該函數。
1.3 高速緩存:必須降低經常訪問的數據的訪問成本。
1.4 延遲計算法:除非需要,否則該策略永遠不會計算某個元素,這樣可以避免計算不必要的元素。
2. 用時間換取空間規則
2.1 壓縮:密集存儲表示能夠通過增加存儲和檢索所需的時間來降低存儲成本。
2.2 解釋程序:通常,使用解釋程序能夠減少表示程序所需的空間,解釋程序壓縮表示相同的操作序列。
3. 循環規則
3.1 將代碼移出循環:最好不要在循環的每次迭代中都執行相同的操作,而是將它放在循環外部,僅僅執行一次。
3.2 合并測試條件:高效的內部循環一個盡量少包含測試條件,最好只有一個。因此,程序員應該盡量使用其他退出條件模擬循環的一些推出條件。哨兵是該規則最常見的應用:在數據結構的邊界上放一個哨兵來測試是否已經遍歷完整個結構。
3.3 循環展開:展開循環能夠消除循環中修改循環下標的成本,同時一能避免管道時延、減少分支,并增加指令級并發。
3.4 傳輸驅動的循環展開:如果在普通的賦值中,使用了一個成本很高的內部循環,那么通常通過改變所使用的變量能夠消除這些賦值。例如:刪除賦值i=就,后面的代碼必須將j視為i。
3.5 消除無條件分支:在快速的循環中不應該包含無條件分支。通過“旋轉”循環,在底部加上一個條件分支,能夠消除循環結束處的無條件分支。
3.6 循環合并:如果兩個鄰近的循環操作作用在同一個元素集上,那么最好合并這兩個操作部分,僅僅使用一個循環控制操作。
4. 邏輯規則
4.1 利用袋鼠恒等式:如果邏輯表達式的計算非常昂貴,就使用比較廉價的代數等式表達式來替換。
4.2 簡化的單調函數:測試幾個部落的單調非遞減函數是不是超過了特定的閥值,一旦達到了這個閥值就不需要計算任何變量。該規則的一個更加復雜的應用就是一旦達到了循環的目的就退出循環。
4.3 重新排序測試:在組織邏輯測試的時候,應該將廉價的經常成功的測試放在昂貴的很少成功的測試前面。
4.4 預計算邏輯函數:可以使用表示域的表的查找替代一個小的有限域中的邏輯函數。
4.5 消除布爾變量:我們可以通過用if-else語句替代對布爾變量的v賦值來消除布爾變量,在if-else語句中的一個分支表示v為真的情況,其它的表示v為假的情況。
5. 過程規則
5.1 壓縮函數層次:通常,重寫函數并綁定過去的變量能夠減少調用本身(非遞歸)函數集合元素的運行時間。
5.2 利用常用情況:一個組織函數正確處理所以情況并高效處理普通情況。
5.3 協同程序:通常,使用協同程序能夠將multiple-pass算法轉換為single-pass算法。
5.4 遞歸函數變化:通過下面的轉換能夠減少遞歸函數的運行時間:將遞歸重寫為迭代,通過使用棧來將遞歸轉換為迭代。如果函數的最后一步是遞歸調用自身,那么使用一個到其第一條語句的分支來替換該調用,這通常叫做尾遞歸。
5.5 并發:在基本的硬件條件下,構建的程序應該能夠盡可能地利用并發。
6. 表示規則
6.1 初始化編譯時間:在程序執行之前,盡可能初始化變量。
6.2 利用代數恒等式:如果表達式的計算非常昂貴,就應使用開銷較小的代數恒等表達式替換它。通常我們可以是向左或向右移位來實現冪的乘或除;盡量減少數組元素上的迭代循環,使用加法替代乘法。
6.3 消除通用子表達式:如果連續兩次計算了同一個表達式,并且它的所有變量都沒有任何改動,那么就應該避免第二次計算,只需要排序第一次計算結果并將它用于第二次計算中。現在的編譯器一般都能消除不包含函數調用的常用子表達式。
6.4 配對計算:如果總是同時計算兩個類似的表達式,那么就應該建立一個新的過程并將它們成對計算。
6.5 利用單詞并發:充分使用基本計算機體系結構的數據總線寬度來計算昂貴的表達式。
文章來源:http://blog.csdn.net/happyhippy/archive/2006/10/29/1355425.aspx
浙公網安備 33010602011771號