程式分析與優化 - 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
  • 用例演示 - 創建實體 本節將演示一些示例用例並討論可選場景。 創建實體 從實體/聚合根類創建對象是實體生命周期的第一步。聚合/聚合根規則和最佳實踐部分 建議為Entity類創建一個主構造函數,以保證創建一個有效的實體。因此,無論何時我們需要創建實體的實例,我們都應該使用那個構造函數 參見下麵的問題 ...
  • 領域邏輯 & 應用邏輯 如前所述,領域驅動設計中的業務邏輯分為兩部分(層):領域邏輯和應用邏輯: 領域邏輯由系統的核心領域規則組成,應用邏輯實現應用特定的用例 雖然定義很明確,但實現起來可能並不容易。您可能無法決定哪些代碼應該位於應用程式層,哪些代碼應該位於領域層。本節試圖解釋其中的差異 多個應用程 ...
  • 表弟大學快畢業了,學了一個學期Python居然還不會寫學生管理系統,真的給我丟臉啊,教他又不肯學,還讓我直接給他寫,我真想兩巴掌上去,最終還是寫了給他,誰讓他是我表弟呢,關鍵時候還是得幫他一把! 寫完了放在那也是放著,所以今天分享給大家吧! 話不多說,咱們直接開始吧! 代碼解析 一、登錄頁面 1、定 ...
  • Zookeeper3.7源碼剖析 能力目標 掌握Zookeeper中Session的管理機制 能基於Client進行Debug測試Session創建/刷新操作 能搭建Zookeeper集群源碼配置 掌握集群環境下Leader選舉啟動過程 能說出Zookeeper選舉過程中的概念 能說出Zookeep ...
  • 前言 今天給大家分享一下我自己寫的筆記,純純的都是乾貨,關於字好像也能看。這是我學python整理出來的一些資料,希望對大家 有用。想要更多的資料那就的給一個關註了… python學習交流Q群:903971231### #導入Counter from collections import Count ...
  • Hi,大家好,我是Mic 一個工作5年的粉絲找到我。 他說: “Mic老師,你要是能回答出這個問題,我就佩服你” 我當場就懵了,現在打賭都這麼隨意了嗎? 我問他問題是什麼,他說“Kafka如何避免重覆消費的問題!” 下麵看看普通人和高手的回答! 普通人: Kafka怎麼避免重覆消費就是我們可以通過 ...
  • 前言 Steam是由美國電子游戲商Valve於2003年9月12日推出的數字發行平臺,被認為是電腦游戲界最大的數位發行平臺之一,Steam平臺是全球最大的綜合性數字發行平臺之一。玩家可以在該平臺購買、下載、討論、上傳和分享游戲和軟體。 而每周的steam會開啟了一輪特惠,可以讓游戲打折,而玩家就會 ...
  • 本篇內容將在上一篇已有的內容基礎上,進一步的聊一下項目中使用JPA的一些高階複雜場景的實踐指導,覆蓋了主要核心的JPA使用場景,可以讓你在需求開發的時候對JPA的使用更加的游刃有餘。 ...
  • 1.路徑處理 1.找模塊:sys.path import sys print(sys.path) - 1.理解 - 1.是python去查找包或模塊 - 2.項目開始根目錄,python內置的目錄 - 3.雖然說python的安裝目錄下也可以存放我們寫的模塊,但是不建議(太多了,不大好找) - 4. ...
  • Go 語言入門練手項目系列 01 基於命令行的圖書的增刪查改 02 文件管理 持續更新中... > 本文來自博客園,作者:Arway,轉載請註明原文鏈接:https://www.cnblogs.com/cenjw/p/gobeginner-proj-bookstore-cli.html 介紹 這是一 ...