程式分析與優化 - 6 迴圈優化

来源:https://www.cnblogs.com/zhouronghua/archive/2022/06/12/16367397.html
-Advertisement-
Play Games

本章是系列文章的第六章,介紹了迴圈的分析方法。迴圈優化的邏輯相對簡單,但對性能提升的效果卻非常明顯。迴圈優化的分析還產生了一個圖靈獎。 本文中的所有內容來自學習DCC888的學習筆記或者自己理解的整理,如需轉載請註明出處。周榮華@燧原科技 6.1 迴圈的重要性 90/10定律,90%的算力消耗在10 ...


本章是系列文章的第六章,介紹了迴圈的分析方法。迴圈優化的邏輯相對簡單,但對性能提升的效果卻非常明顯。迴圈優化的分析還產生了一個圖靈獎。

本文中的所有內容來自學習DCC888的學習筆記或者自己理解的整理,如需轉載請註明出處。周榮華@燧原科技

 

6.1 迴圈的重要性

  • 90/10定律,90%的算力消耗在10%的代碼上,這些代碼絕大多數都是各種迴圈
  • 迴圈的優化對獲得更高的性能非常重要
  • 基於迴圈的迭代空間轉換的優化(本章不涉及)
  • 維持迴圈的迭代空間不變進行的優化(本章重點):
    • 代碼提升(code hoisting)
    • 強度削減(strength reduction)
    • 迴圈展開(loop unrolling)
    • 等等

6.2 分解控制流圖

對於下麵的C代碼,分析一下有幾重迴圈?怎麼從控制流圖中定義迴圈?

 1 #include <stdio.h>
 2 int main(int argc, char **argv) {
 3   int sum = 0;
 4   int i = 1;
 5   while (i < argc) {
 6     char *c = argv[i++];
 7     while (*c != '\0') {
 8       c++;
 9       sum++;
10     }
11   }
12   printf("sum = %d\n", sum);
13 }

 

 

控制流圖的生成方法就不多說了,忘記的同學可以回過頭去看看第二章(2.1.3 LLVM),生成的svg圖如下:

 

 

 

控制流圖中的自然迴圈是具有下列屬性的節點的集合S:

  • 存在一個頭結點h
  • S中的任意一個元素都存在路徑到頭結點h
  • S外不存在任何節點有邊指向S中除h意外的其他節點

編譯器中說的迴圈(loop)和拓撲意義上的環(cycle)是不同的。編譯器領域中的環只能有一個入口,多個入口的環在編譯器領域不叫做迴圈,因為絕大多數對迴圈的優化在多入口的環中都不適用。

多個入口的環在編碼過程中也非常罕見,所以也不是編譯器需要關心的場景。

6.2.1 控制流圖的簡化過程

如果對於邊(n1, n2),n1是n2的唯一前驅,或者n1和n2是強連通圖的一部分,可以用下麵的方法簡化:

  • 刪除邊(n1, n2)
  • 新建節點n12
  • 將所有n1的前驅改成n12的前驅
  • 將所有n2的後繼改成n12的後繼
  • 刪除節點n1和n2

重覆上述操作,直到控制流圖保持不變。

例如下麵的控制流圖:

 

 

簡化流程是這樣的:

 

 

 

 

為什麼要簡化控制流圖:

  • 入口單一,可以在優化過程中在頭結點處增加 冗餘代碼
  • 簡化後的圖數據流分析速度更快
  • 常規的迴圈語法,例如for,while,repeat,continue和break都會產生可簡化的控制流圖
  • goto會產生不可簡化的流圖

6.3 自然迴圈

6.3.1 支配節點(Dominators)

節點d是節點n的支配節點,當且僅當所有從控制流圖入口到n的所有路徑都經過d。

D[s0] = {s0} D[n] = {n∪ (∩ p∈ pred[n]D[p]), for n ≠ s0
支配節點的計算:

 

 

6.3.2 直接支配節點(Immediate Dominators)

每個階段n都 只有唯一一個直接支配節點idom(n),定義如下:

  • idom(n) 不是n
  • idom(n)是n的支配節點
  • idom(n)不是n的其他支配節點的支配節點

6.3.3 支配節點樹(Dominator Tree)

把每個節點的直接支配節點畫一條邊到該節點,就形成了圖的支配節點樹:

 

 


嵌套迴圈中優先優化記憶體迴圈。

迴圈的頭節點h:在迴圈的節點集中,存在一個節點n,h是它的支配節點,並且存在邊(n, h)。

如果兩個迴圈的頭結點存在支配關係,則被支配的頭節點所在的迴圈稱為內迴圈,支配的頭節點所在的迴圈稱為外迴圈。

6.4 安全的不變代碼提升(SAFE INVARIANT CODE HOISTING)

6.4.1 迴圈不變性

如果某個計算在迴圈的每次迭代中都產生同樣的值,則該計算時迴圈不變的。

迴圈不變表達式的通常優化方法是將該表達式提升到迴圈外。

滿足下麵任意一條要求的表達式是迴圈不變表達式:

  • 表達式的參數是常量
  • 表達式的參數定義在迴圈外
  • 表達式的參數是迴圈不變表達式,並且在該表達式之前沒有其他定義

將迴圈不變表達式提升到迴圈外的做法稱為代碼提升。

6.4.2 安全的不變代碼提升

在程式點d,如果滿足下麵3個條件,可以對錶達式t = a + b 安全的進行代碼提升:

  • d是所有t生效區域內節點的支配節點
  • t在迴圈內只有一個定義
  • t在迴圈的頭結點外沒有使用

6.4.3 迴圈倒置(Loop Inversion)

將常規的while迴圈轉換成repeat-util迴圈的做法稱為迴圈倒置。倒置後的迴圈可以安全的進行不變代碼提升。

repeat-utill迴圈在迴圈過程中每次迭代只需要進行一次跳轉,所以性能也比常規的while迴圈要好。

6.5 因變數(INDUCTION VARIABLES)

6.5.1 基本概念

基本因變數(Basic induction variable):如果一個變數i在迴圈內部僅定義一次,並且每次定義都是在原有值基礎上增加或者減少迴圈不變數的值。

派生因變數(Derived induction variables):如果一個變數k在迴圈內部僅定義一次,並且k是一個因變數與迴圈不變數的乘積或者和。

i系列的派生因變數(a derived induction variable in the family of i):如果一個變數k定義中使用的因變數j僅定義一次,並且定義在迴圈內部,在j和k之間沒有i的定義。

6.5.2 強度削減

將乘法運算換算成加法運算。例如下麵的優化:

 

 

強度削減的演算法基本上就是將派生因變數轉換成基本因變數。演算法過程一般如下:

  • 對所有j = i * c, 假定變數i每個迭代增加b,i 初始化為a,那j每個迭代就要增加 b*c。
  • 在迴圈外新增一個變數j'為第一次迭代時的j的值, j' = a*c
  • 在迴圈外新增一個變數k,用來保存每個迭代j需要增加的值b*c
  • 這樣迴圈內部就可以優化成
  • j = j'
  • j' += k

6.5.3 無用代碼刪除(Dead Code Elimination)

首先刪除的是j',因為k'已經完成了類似的功能:

 

 

由於i除了定義就只有和迴圈不變數的比較,所以實際上i也是可以刪除的:

 

 

刪除冗餘拷貝:

 

 

迴圈倒置:

 

 

初始版本和最終優化版本的對比:

 

 

 

6.5.4 迴圈展開

迴圈展開是通過減少迴圈次數並增加迴圈內部的計算來優化的一種方式。例如對下麵的代碼:

 

 

以2為因數進行迴圈展開之後的結果是這樣的:

 

 

 

6.5.5 指針分析簡史

  • Lowry, E. S. and Medlock, C. W. "Object Code Optimization". CACM 12(1), 13-22 (1969) 引入因變數優化和支配節點的概念
  • Allen, F. E. "Control Flow Analysis". SIGPLAN Notices 23(7) 308-317 (1970)引入控制流圖的化簡,並因此獲得圖靈獎

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 通過在互聯網上收集及微軟官方網站等途徑獲取相關資料進行整理彙總出Microsoft SQL Server各個版本(SQL Server 2008 R2、SQL Server 2012、SQL Server 2014、SQL Server 2016、SQL Server 2017、SQL Server ...
  • Redis常見使用場景,緩存、數據共用分散式、分散式鎖、全局 ID、計數器、限流、位統計、購物車、時間線 Timeline、消息隊列、抽獎、點贊、簽到、打卡、商品標簽、商品篩選、用戶關註、推薦模型、排行榜. ...
  • **導讀:**本文是OPPO商業數據研發負責人&技術專家邱盛昌老師帶來的“OPPO商業化數據體系建設實踐”的分享。整體內容圍繞著下圖中垂直劃分的六個部分展開,分別為:數據平臺、數據接入、數據開發、數據治理、數據應用和數據分析,這個圖也概括了典型的數據體系的所有內容。 -- 01 數據平臺 數據平臺由 ...
  • 第一步:下載資料庫 通過shell工具,採用xftp功能 第二步:解壓數據包 mkdir mysql (在解壓之前創建文件夾) tar -xvf mysql-8.0.28-1.el8.x86_64.rpm-bundle.tar -C mysql 可以將解壓的文件放入到mysql文件夾中 第三步:安裝 ...
  • 1.下載安裝包 1.1 下載elasticsearch 7.13.3 curl -L -O https://artifacts.elastic.co/downloads/elasticsearch/elasticsearch-7.13.3-linux-x86_64.tar.gz 1.2 解壓文件 t ...
  • 開始我們後臺篇的內容,前面處理了一些事情,去學校完成授位儀式,由校長授位合影,青春不留遺憾,然後還換了一個電腦,征戰了四年的神船終於退役了,各種各樣的小毛病是真的煩人。 現在正式開始後臺篇的內容,做了今天總體的感覺後臺部分大難度沒有,但是要考慮一點就是對於elementUI的熟練程度,要把這個練得比 ...
  • theme: mk-cute highlight: arduino-light 一、開發背景 產品出設計稿要求做一個仿原生app簡訊驗證碼組件,花了兩小時搞出來一個還可以的組件,支持屏幕自適應,可以用於彈出框,或自己封裝的vue組件里,希望可以幫助那些被產品壓榨的同學,哈哈。😄 其核心思想就是利用 ...
  • ​網址:https://parcel.passerma.com/ GitHub:GitHub - passerma/parcel-doc: 🌎 Parcel 中文文檔 本文檔持續翻譯中,有想幫忙(希望有人)翻譯的小伙伴也可參與哦 使用 Parcel 構建 Web 應用程式 安裝 在開始之前,您需要 ...
一周排行
    -Advertisement-
    Play Games
  • 1.部署歷史 猿友們好,作為初來實習的我,已經遭受社會的“毒打”,所以請容許我在下麵環節適當吐槽,3Q! 傳統部署 ​ 回顧以往在伺服器部署webapi項目(非獨立發佈),dotnet環境、守護進程兩個逃都逃不掉,正常情況下還得來個nginx代理。不僅僅這仨,可能牽扯到yum或npm。node等都要 ...
  • 隨著技術的進步,跨平臺開發已經成為了標配,在此大背景下,ASP.NET Core也應運而生。本文主要基於ASP.NET Core+Element+Sql Server開發一個校園圖書管理系統為例,簡述基於MVC三層架構開發的常見知識點,前一篇文章,已經簡單介紹瞭如何搭建開發框架,和登錄功能實現,本篇... ...
  • 這道題只要會自定義cmp恰當地進行排序,其他部分沒有什麼大問題。 上代碼: 1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,s,h1,h2,cnt; 4 struct apple{ 5 int height,ns;//height為蘋 ...
  • 這篇文章主要描述RPC的路由策略,包括為什麼需要請求隔離,為什麼不在註冊中心中實現請求隔離以及不同粒度的路由策略。 ...
  • 簡介: 中介者模式,屬於行為型的設計模式。用一個中介對象來封裝一系列的對象交互。中介者是各對象不需要顯式地相互引用,從而使其耦合鬆散,而且可以獨立地改變他們之間的交互。 適用場景: 如果平行對象間的依賴複雜,可以使用中介者解耦。 優點: 符合迪米特法則,減少成員間的依賴。 缺點: 不適用於系統出現對 ...
  • 【前置內容】Spring 學習筆記全系列傳送門: Spring學習筆記 - 第一章 - IoC(控制反轉)、IoC容器、Bean的實例化與生命周期、DI(依賴註入) Spring學習筆記 - 第二章 - 註解開發、配置管理第三方Bean、註解管理第三方Bean、Spring 整合 MyBatis 和 ...
  • 簡介: 享元模式,屬於結構型的設計模式。運用共用技術有效地支持大量細粒度的對象。 適用場景: 具有相同抽象但是細節不同的場景中。 優點: 把公共的部分分離為抽象,細節依賴於抽象,符合依賴倒轉原則。 缺點: 增加複雜性。 代碼: //用戶類 class User { private $name; fu ...
  • 這次設計一個通用的多位元組SPI介面模塊,特點如下: 可以設置為1-128位元組的SPI通信模塊 可以修改CPOL、CPHA來進行不同的通信模式 可以設置輸出的時鐘 狀態轉移圖和思路與多位元組串口發送模塊一樣,這裡就不給出了,具體可看該隨筆。 一、模塊代碼 1、需要的模塊 通用8位SPI介面模塊 `tim ...
  • AOP-03 7.AOP-切入表達式 7.1切入表達式的具體使用 1.切入表達式的作用: 通過表達式的方式定義一個或多個具體的連接點。 2.語法細節: (1)切入表達式的語法格式: execution([許可權修飾符] [返回值類型] [簡單類名/全類名] [方法名]([參數列表]) 若目標類、介面與 ...
  • 測試一、虛繼承與繼承的區別 1.1 單個繼承,不帶虛函數 1>class B size(8): 1> + 1> 0 | + (base class A) 1> 0 | | _ia //4B 1> | + 1> 4 | _ib //4B 有兩個int類型數據成員,占8B,基類邏輯存在前面 1.2、單個 ...