顯示具有 Code Optimized 標籤的文章。 顯示所有文章
顯示具有 Code Optimized 標籤的文章。 顯示所有文章

2024年10月2日 星期三

From120s to 0.5s Programming Optimization

程式算法本身的複雜度

CPU的速度和設計架構

CPU的位元帶寬

自己的程式的寫法




將一個照片RGB格式的彩色圖像轉換成黑白照片。

轉換的公式如下:
  Y = 0.299 * R + 0.587 * G + 0.114 * B; 

圖像尺寸640*480*24bit,RGB圖像已經按照RGBRGB順序排列的格式了。


以下是輸入和輸出的定義:

已經完成了第一個最佳化
看得出來最佳化在哪裡嗎?


優化原則: 圖像是一個2D資料,我用一個1維陣列來存儲。 編譯器處理1維陣列的效率高過2維陣列

這大概是能想得出來的最簡單的寫法了,實在看不出有什麼毛病,好了,編譯一下跑一跑吧。

這個代碼分別用VC6.0和GCC編譯,產生2個版本,分別在PC上和embedded system上面跑。

速度多少?說出來嚇死你!


第一次試跑的成績

在PC上,因為有硬體浮點運算處理器,CPU頻率也夠高,計算速度為20秒

embedded system ,沒有以上2個優勢,浮點操作被編譯器分解成了整數運算,運算速度為120秒左右
這只是一副圖像的運算速度!!

上面這個代碼還沒有跑,就已經知道會很慢了,因為這其中有大量 的浮點運算。只要能不用浮點運算,一定能快很多。

那這個公式怎麼能用定點的整數運算替代呢?

可以如何化簡?
我們就先簡化算式D吧!

RGB的取值範圍都是0~255,都是整數,只是這個係數比較麻煩, 不過這個係數可以表示為:
這一下,能快多少呢?

化簡後的成績


PC上的速度2秒

Embedded system
上的速度45秒


這個代碼編譯後,又快了20%
還是太慢!

雖然快了不少,還是太慢了一些,
20秒處理一幅圖像,地球人都不能 接受!

仔細看一下這個式子!

RGB的取值有文章可做,RGB的取值永遠都大於等於0,小於等於
255,我們能不能將D,E,F都預先計算好呢?然後用查表算法計 算呢?
我們使用3個數組分別存放DEF的256種可能的取值,然後。。。


查表數組初始化



突破音障!
這一次的成績把我嚇出一身冷汗,執行時間居然從30秒一下提高到 了2秒!在PC上測試這段代碼,眼皮還沒眨一下,代碼就執行完了。

一下提高15倍,爽不爽?
下一程,幾 秒?

120秒 ->45秒 -> 30秒 -> 2秒
還能再 快嗎?

很多embedded sysytem 的32bitCPU,都至少有2個ALU,能不能讓2個ALU都跑起來?

2個ALU處理的數據不能有數據依賴,也就是說:
某個ALU的輸入條件不能是別的ALU的輸出,這樣
才可以並行
到這裡,似乎已經足夠快了,但是我們反覆實驗,發現,還有辦法再快!

Int D[256],E[256],F[256]; //查表數組 更改為:
Unsigned short D[256],E[256],F[256]; //查表數組

這是因為編譯器處理int類型和處理unsigned short類型的效率不一樣
將函數聲明為inline,這樣編譯器就會將其
嵌入到母函數中,可以減少CPU調用子函 數所產生的開銷
這2個小小的改進帶來的效益!


一次的成績是: 0.5秒

現在,我們已經達到了客戶的要求!

如果加上以下措施,應該還可以更快:

把查表的數據放置在CPU的高速數據CACHE
裡面

把函數calc_lum()用組合語言來寫

同樣的需求,寫法不一樣,速度可以從120秒 變化為0.5秒,說明CPU的潛能是很大的!看你 如何去挖掘。










2021年12月20日 星期一

程式優化寫法

 

  1. unsigned/signed
    一般情況下,在使用signed類型時compiler會考慮其為正數和負數的情況,因此在不會出現負數的環境中,使用unsigned會避免負數的開銷,從而節省ROM。


  2. 資料形態選擇適當範圍的資料類型,助於產生更精簡的指令。


  3. 浮點常數浮點常數默認為double類型,如果計算所需要的精度不需太高,可以將它強制轉為float,如:(float)3.14


    編譯器不會給浮點運算常量折叠,所以,如果有兩個浮點常數需要計算,可以把結果先算出來:


  4. const陣列把const陣列定義成全域會比局域的節省RAM:


  5. 算術運算
    位與運算(&)代替取模運算(%)一般情況下,“&”操作比“%”操作簡單,在某些特殊情況下,如果可以使用“&”代替“%”,則會降低指令的開銷。


  6. 程式結構
    switch語句代替if else語句當程式中存在多層嵌套的if  else語句,如果多重判斷可轉為switch語句,可以試著轉為switch語句,以便節省ROM
  7. 重複多次的運算可以用迴圈代替當程式中存在多次重複的運算,而且都有規律性,可以用迴圈代替。



  8. 使用預處理命令維護原始程式碼有時候為了維護的方便,希望同一份源碼滿足不同環境的要求,如果用硬編碼的方式,可能會消耗很多的ROM,此時若利用條件編譯的特性,就能輕鬆的實現:



  9. 函式呼叫
    避免不必要的函式呼叫若某函式被多次調用,但其返回值並無差異,應考慮用變數接收函式返回值,使用時做為替代。



  10. 封裝頻繁使用的代碼為函式如果在程式中存在某段代碼被多次使用,在可能的情況下,應將這段代碼封裝起來獨立成為函式,以便節省指令



  11. 如果函式只在本文檔調用,可以定義成static



  12. 全局變數的分配對無擴展指令架構的MCU,RAM  BANK0以外的地址只能用間接定址的方式訪問,下例可以看出,間接定址的指令比直接定址多出5條,所以,當RAM bank0溢出時,用戶可以選擇把較少用到的變數定義到其它bank,比較常用的變數定義在bank0。



  13. 中斷服務程式一般,如果兩個函式沒有調用關係,那它們的局域變數是可以分配到同樣的地址,但中斷服務程式不會與主函式共用局域變數的地址,所以,為了減少RAM的使用,中斷程式可以儘量簡單,不宜寫得太過複雜。


資料來源:https://www.holtek.com.tw/documents/10179/178484/Holtek_C_compiler_V3_Users_Guide(950).pdf

2021年8月13日 星期五

MISRA--作為工業標準的C編程規範(1)

 MISRA (The Motor Industry Software Reliability Association汽車工業軟件可靠性聯會)是位於英國的一個跨國汽車工業協會,其成員包括了大部分歐美汽車生產商。

其核心使命是為汽車工業提供服務和協助,幫助廠方開發安全的、高可靠性的嵌入式軟件。
這個組織最出名的成果是所謂的MISRA C Coding Standard,這一標準中包括了127條C語言編碼標準,通常認為,如果能夠完全遵守這些標準,則你的C代碼是易讀、可靠、可移植和易於維護的。
最近很多嵌入式開發者都以MISRA C來衡量自己的編碼風格,比如著名的uC/OS-II就得意地宣稱自己99%遵守MISRA標準。
而《嵌入式開發雜誌》也專門載文號召大家學習。編碼規範通常是一個公司自定的“土政策”,居然有人去做標準,而且還得到廣泛的認可,這不禁引起我強烈的興趣。
可惜這份標準的文本需要花錢去買,而且短短幾十頁,要價非常昂貴。 MISRA在網上公佈了一些文檔,其中有關於MISRA C Coding Standard的Clarification報告,從中間你可以大致猜到MISRA標準本身是什麼。
我仔細閱讀了這些文檔,並且通過閱讀其他一些介紹性文檔,大致了解了MISRA標準的主要內容。這些條款確有過人之處,對於C/C++語言工程項目的代碼質量管理能夠起到良好的指導性作用,對於大部分軟件開發企業來說,在MISRA的基礎上適當修改就可以形成自己的規範。
當然其中也有一些過於嚴苛的東西,這就需要各個開發部門靈活處理了。我個人的體會,編碼規範雖然很簡單,但是要完全執行,不折不扣,需要開發部門有很高的組織性和紀律性,並且有很好的代碼評審機制。因此,如果能夠嚴格地遵守編碼規範,本身就是一個開發部門實力的證明。

這裡不可能將所有規則一一列出(事實上正式文本我一條也沒看到),只列出一些比較有意思的條款,讓大家有機會了解MISRA的風格。
具體的內容,感興趣的朋友可以自己到www.misra.org.uk去了解。

Rule 1.嚴格遵循ANSI C89標準,不允許任何擴展。


Rule 3.如果要嵌入彙編語言,則必須將所有彙編語句包裝在C函數里,而且這些函數中只有彙編語句,沒有常規C語句。

    Rule 7.不得使用三元操作符(? : )

Rule 10.不得殘留被註釋掉的廢代碼。

Rule 11.所有標識符不超過31字符。

Rule 12.不同名空間中的變數名不得相同。
        例如:
             typedef struct MyStruct {... } MyStruct; (違規)

             struct Person {
               char* name;
               ...
             };

             char name[32]; (違規)

Rule 13.不得使用char, int, float, double, long等基本類型,應該用自己定義的類型顯示表示類型的大小,如CHAR8, UCHAR8, INT16, INT32, FLOAT32, LONG64, ULONG64等。
Rule 14.不得使用類型char,必須顯示聲明為unsigned char或者signed char。

Rule 18.所有數字常數應當加上合適的後綴表示類型,例如51L, 42U, 34.12F等。

Rule 19.禁止使用八進制數。 (因為086U這樣的常數很容易引起誤解)。

Rule 21.不得定義與外部作用域中某個標識符同名的對象,以避免遮蓋外部作用域中的標識符。

Rule 23.具有文件作用域的對象盡量聲名為static的。

Rule 24.在同一個編譯單元中,同一個標識符不應該同時具有內部鏈接和外部鏈接的聲名。


        這裡我略作說明:

                我們通常將一些放在頭文件裡的變數聲名為“外部鏈接”的,如:
         extern UINT32 g_count; //俗話叫變數聲明(對應於變數定義,不分配實際空間)

        對於“使用”這個變數的.c文件來說,這很好,因為g_count始終保持外部鏈接性質。可是對於定義g_count(實際分配空間)的.c文件來說,如果包含了上述的頭文件,則在這個編譯單元里就發生了內部鏈接和外部鏈接的衝突。
 解決辦法是,定義g_count的文件盡量不要包含聲名g_count的頭文件。個人感覺這不是任何時候都做得到的,尤其是在對付遺留代碼的時候。

Rule 25.具有外部鏈接性質的標識符應該只聲明一次。

Rule 27.外部對像不得在多個文件中聲名。

Rule 28.禁止使用register關鍵字。

Rule 29.自動對象(棧對象)使用前必須賦初值。

Rule 33.操作符&&和||的右側表達式不得具有副作用(side-effect)。
        也就是說,象if (x == 20 && ++y == 19)這樣的表達式被禁止。

Rule 35.在返回布林值的表達式中不得出現賦值操作。
        也就是說,我們常用的if (!(fp = fopen("fname", "r"))) { /* error */ }
        被禁止。

Rule 37.不得對有符號數施加位操作,例如1 << 4將被禁止,必須寫1UL << 4;

Rule 39.不得對有符號表達式施加一元"-"操作符。

Rule 40.不得對有副作用的表達式施加sizeof操作符。

Rule 42.除了循環控制語句,不得使用逗號表達式。

Rule 44.禁止冗餘的顯式轉型。比如: double pi = (double) 3.1416F;

Rule 45.禁止從任意類型到指標的強制轉型,禁止從指標到任意類型的強制轉型。
        例如:void* p = (void*)0xFFFF8888UL;

Rule 49.顯示測試值是否為零。

Rule 50.不得顯式判斷浮點數的相等性和不等性。

Rule 52.不得遺留“永遠不會用到”的代碼。

Rule 53.所有非空語句必須具有副作用。

Rule 55.除了switch語句,不得使用標號(label)。

Rule 56.不得使用goto.

Rule 57.不得使用continue。

Rule 58.除了switch語句,不得使用break.

Rule 59. if, else if, else, while, do..while, for語句塊必須使用{}括起。
Rule 60.任何if..else if語句,最後必須有一個收尾的else。例如:
         if (ans == 'Y') {
           ...
         }
         else if (ans == 'N') {
           ...
         }
         else if (ans == 'C') {
           ...
         }
         else {
           ;
         }

Rule 67.循環計數器的值不得在循環體內修改。

Rule 70.禁止任何直接和間接的遞歸函數呼叫。

Rule 82.每個函數只能有一個推出點。

Rule 86.如果一個函數可能返回錯誤信息,則呼叫後必須加以測試。

Rule 92.不應該使用#undef

Rule 95.不得將巨集作為參數傳給巨集函數

Rule 98.在一個巨集定義中,#或##符號只能出現一次。

Rule 101.禁止指標運算(代之以陣列下標運算)。

Rule 102.禁止超過兩級的指標。

Rule 104.禁止使用指向函數的非常量指標。

Rule 106.不得將棧對象的地址傳給外部作用域的對象。

************************************************** ******************
後面的規則針對實時嵌入式系統,對其他類型的開發未必適用,如:

Rule 118.禁止使用動態記憶體分配(也就是不得使用malloc, calloc和realloc)。

Rule 119.禁止使用errno。

Rule 120.禁止使用offsetof.

Rule 121.禁止使用<locale.h>

Rule 122.禁止使用setjmp, longjmp.

Rule 123.禁止使用<signal.h>

Rule 124.禁止使用<stdio.h>(不能用printf, scanf了!)

Rule 125.禁止使用atoi, atof, atol。 (這個我很贊成,建議使用strtol, strtod等函數)

Rule 126.禁止使用abort, exit, getenv。

Rule 127.禁止使用<time.h>

資料來源:https://b8807053.pixnet.net/blog/post/3612211