優化 C 程式碼

    前言

    寫程式有幾個層次:

    • 正確地使用語法和函式庫
    • 程式運行正確,沒有邏輯錯誤
    • 使用軟體工程的原則改善程式碼
    • 程式運行快速

    在這幾個層次中,第三項和第四項是選擇性的,所以不應耗費過多時間在無謂的調整上。

    所謂的優化,就是用各種手法讓程式運行更快速。這是在程式運行正確後,進一步改善程式的方式。在本文中,我們從 C 的觀點在看如何優化程式碼。

    通用概念

    先求好再求快

    我們在前文提過,優化程式碼的前提是該程式碼是正確的。如果我們直接對錯誤的程式碼進行優化,之後還是得把錯誤的程式碼改掉,這樣的優化只是無意義的操作。當然,我們不會刻意寫出有 bug 的程式碼,但我們應該要先檢查程式碼,儘可能地確認程式碼是正確的,然後才開始優化程式碼。

    只在必要時優化程式碼

    由於優化程式碼是選擇性的工作,我們只應在感受到效能瓶頸時才優化程式碼。客戶較願意為程式的 feature 買單,但不太會為優化過的程式多付錢。所以,我們應該分配較多的時間在寫新的程式和增加程式的 feature 上面,只有在必要時才去優化程式碼。

    此外,優化程式碼這件事並沒有明確的結束點。我們總是有辦法找出程式中可以優化的地方。但耗費過多時間在一些不重要的優化上其實只是在浪費程式設計師的時間和金錢。

    先優化關鍵步驟

    優化程式碼的手法很多,但有些手法只會對程式有少量的改善。由於開發者的時間是有限的,應該先找出影響程式的關鍵步驟,並對該步驟進行優化。行有餘力才去優化比較枝微末節的部分。

    比起自行觀察和優化程式碼,使用剖析器 (profiler) 更能有效率地找出程式的瓶頸步驟。以 C 語言來說,可以使用 GNU Profiler 等軟體來剖析程式碼。但剖析程式碼這個動作本身會拖慢程式效能,所以最後程式要上線前,要關掉和剖析器相關的參數後重新編譯一次程式。

    優化程式碼時要有明確的方向

    優化程式碼時,要有明確的方向。因為不同的優化方向會對程式造成不同的改變。

    根據優化的方式,有可能會加快程式執行速度、縮減程式體積、節約程式所用的記憶體量,但很難三者兼具。所以,所謂的優化,其實是在效能、體積、記憶體用量等面向做權衡。沒有最好的優化,只有最適合專案的優化。

    優化和可讀性有時無法兼得

    有些優化程式碼的方式會使得程式碼的可讀性變差。例如,軟體工程告訴我們將程式碼切成函式會比較易讀,但函式呼叫這個動作本身會有一些額外的開銷 (overhead)。將代數運算轉為二進位運算會改善效能,但二進位運算的可讀性比代數運算較差。

    由此可知,優化程式碼不是硬科學,程式設計者要自己在程式效能及程式碼可讀性間做裁量。

    編譯器會自動幫我們優化

    編譯器是很聰明的軟體,除了將程式碼轉為機械碼外,在這個過程中還為我們做了許多額外的優化。GCC 和 Clang 等 C 編譯器經過許多程式設計師投入大量時間來改善,新的編譯器要追上這些成熟穩健的編譯器相當困難。

    有些程式語言不自己寫編譯器,而是將該語言的程式碼轉為等效的 C 程式碼,然後再由 GCC 或 Clang 去編譯出機械碼。因為自己優化程式碼還不如直接使用 C 編譯器來得有效率。

    巨觀的優化

    改用有效率的資料結構或演算法

    使用有效率的資料結構或演算法會對程式的效能產生巨大的差異,這就是為什麼我們要學資料結構、演算法等理論性的課程。比起其他的優化手法,誤用不良的資料結構或演算法對程式的效能影響更顯著。反之,即使我們不刻意去優化程式碼,使用了有效率的資料結構或演算法,效能也不會太差。

    了解程式的特性

    程式運行時,有可能會在運算、操作記憶體、輸出入等步驟間交替進行。要了解自己的程式主要在進行那一類型的步驟:

    • CPU bound
    • I/O bound
    • memory bound

    之後就可以根據程式的特性來優化程式碼。

    選擇硬體

    程式進行運算時,有可能使用以下硬體:

    • CPU
    • GPU,即顯示卡內的晶片
    • 微控制器
    • FGPA

    對於兼具軟硬體的產品來說,可藉由選擇合適的硬體來增進程式的效能、節省電力用量、節省運算成本等。

    選擇作業系統

    現代處理器不能辨識 16 位元模式,所以,不應該使用 16 位元的作業系統。相對來說,目前 64 位元系統是主流,但仍然有些程式是以 32 位元運行。通常 64 位元系統會比 32 位元系統快一些,應優先使用。

    在 64 位元系統中,對於多參數函式而言,使用 GNU/Linux 或 BSD 會比 Windows 快一些,因為 Windows 只會把四個函式參數存到暫存器 (register)。應對的方式是使用 static 函式、使用 inline 函式等。

    選擇程式語言

    在相同的運算步驟下,以下是使用不同語言的效能排名:

    • 組合語言
    • C 或 C++
    • Rust、Golang
    • Java、C#
    • Perl、Python、Ruby

    對於有能力的程式設計者來說,使用組語寫程式仍然會比使用 C 或 C++ 來得快。但組語比較難上手,而且組語無法跨平台。非資訊相關科系的程式設計者不太會去碰組語。所以,在一般情境下,我們還是可以把 C 或 C++ 視為最快的語言。

    C 和 C++ 的效能算是伯仲之間,並不是 C 比 C++ 快。兩者的差別在於 C 程式所需的運算資源較少、程式體積較小,所以在嵌入式程式中,仍會使用 C 而非 C++。對於桌面環境或伺服環境等系統資源充足的環境中,選擇 C 或 C++ 則僅是個人偏好。

    Rust 或 Golang 等新興編譯語言會比 C 或 C++ 慢一些些,因為這些語言的程式會做安全性檢查。實際上,Rust 的效能會比 Golang 好,而且 Rust 沒有垃圾回收器而 Golang 有。將這兩者放在一起只是因為兩者的目標市場有一些重疊。

    Java 或 C# 會把程式碼編譯成位元碼 (bytecode) 而非機械碼,再由虛擬機器去執行位元碼。這類語言的缺點是運行環境肥大,而且啟動速度會略慢。當我們想用靜態型別語言,但效能不是最重要的考量時,就可以考慮用這類語言來實作。

    當我們使用動態型別語言時,就不要想程式的效能了。這類語言的目的就是可以在短時間內產出可用的電腦程式。如果使用動態型別語言卻斤斤計較程式的效能,基本上是選錯工具。

    不過,也有少數動態型別語言可以達到很好的效能。一些實例就是 LuaJIT 和 Julia。如果真的有這方面的需求,可以注意一下這兩個語言。

    雖然選錯了語言,還是可以用新的語言移植程式。但有時候,移植的代價會過大,變得實務上不可行。臉書 (Facebook) 網站為了快速開發,使用了 PHP。但用新語言重寫臉書這種大型網站是不切實際的作法。最後臉書公司只好做了一個新的語言和虛擬機器 (見 Hack) 來改善臉書網站的效能。

    由前文可知,我們最好一開始就選好適合專案的語言,以避免日後移植或重寫專案所耗費的心力。

    選擇 C 編譯器

    對於相同的 C 程式碼,使用不同的 C 編譯器來編譯,有時候會有一些效能上的差別。這是因為不同 C 編譯器在編譯程式時,內部使用了不同的優化方式。一般來說,GCC 或 Clang 所編譯出來的程式會比 Visual C++ 所編譯出來的桯式的效能會好一些。

    使用不同 C 編譯器編譯不同檔案

    承上,我們可以在同一份 C 專案中,使用不同 C 編譯器編譯不同的 C 程式碼。C 的物件檔 (object file) 有很高的機會可以交叉使用。

    相對來說,C++ 的物件檔往往不能交叉使用,因為不同 C++ 編譯器很有可能使用不同的 name mangling 規則。

    選擇函式庫

    常見的任務,會寫在標準函式庫中。但標準函式庫往往不是效能最好的,只是這些函式放在標準函式庫中,取用比較方便。如果很在意效能的話,可以考慮將其中一些函式用效能較好的社群方案取代。

    同理,當我們在選擇社群函式庫時,效能也是考量點之一。現在許多社群函式庫都是以自由軟體的形式來發佈,我們有機會看到這些函式庫的內部實作。若在意效能的話,可以在數個同質函式庫間比較一下。

    靜態連結比動態連結快

    動態連結的好處是可以共享程式碼、可單獨更新函式庫等。相對來說,使用動態函式庫會有一點點額外的開銷。如果很在意效能的話,可將一部分函式庫改用靜態連結。例如,標準函式庫和圖形函式庫等公共函式庫保持動態連結,但專案內的私有函式庫則用靜態連結。

    觀看編譯器轉換出來的組語程式碼

    雖然 C 語言給人的感覺比較低階,但 C 仍然是高階語言,只是抽象化的程度比其他高階語言少。只有組合語言才是低階語言。在編譯時,C 編譯器會先把 C 程式碼轉成等效的組語程式碼,然後才將這些組語程式碼轉為機械碼。

    所以,當對程式的實作有疑問時,觀看 C 編譯器轉換出來的組語程式碼是最直接的方式。C 編譯器有將 C 程式碼轉為組語程式碼的參數。讀者可以查閱一下自己使用的 C 編譯器手冊。

    將關鍵的步驟改用組合語言寫

    承上,既然 C 編譯器是幫程式設計師寫組語的軟體,程式設計師也可以自己手動寫組語。為了節省開發時間,我們不會將所有的程式碼都用組語來寫,而會將關鍵步驟用組語改寫。C 程式碼中也可以用 inline assembly 的方式插入組語程式碼。

    對於有能力的程式設計師來說,手動寫組語的確會比較快。但若組語寫得不好,反而會比寫 C 來得慢。這是因為現在的 C 編譯器發展多年,常見的優化手法已經寫進編譯器中。對於一般使用情境來說,寫 C 其實就足夠了。

    簡化程式安裝和更新的時間

    程式安裝和更新不會影響程式的效能,但會消耗程式使用者的時間。所以,讓程式易於安裝和更新,也是改善程式的一環。

    不同系統使用不同的方式來安裝程式。傳統上,Windows 系統使用安裝精靈來安裝程式。但也可以用 Chocolatey 或 Scoop 等套件管理軟體來包裝程式。

    macOS 上正統的程式發佈方式是 DMG 或 PKG 格式,但自由軟體可用 Homebrew 等套件管理軟體來包裝程式。

    GNU/Linux 則差異性較大。一般來說,會提供 RPM 和 DEB 兩種格式的套件。Snap 格式可跨越多種 GNU/Linux 發行版,但尚未普及。

    耗費時間的步驟

    以下是相對耗時的指令:

    • 存取檔案
    • 存取資料庫
    • 連結網路
    • 建立行程
    • 輸出資料到終端機
    • 動態配置記憶體
    • 字串操作

    相對來說,運算的速度會比較快。所以,想要優化程式時,可以先從這些指令來下手。如果不確定那段程式碼比較耗時,則可以使用剖析器。

    C 程式碼的註解和空白和程式效能無關

    當我們發佈 JavaScript 程式時,我們會用 minifier 刻意把 JavaScript 程式碼的註解和不必要的空白拿掉。這是因為 JavaScript 是直譯語言,每次執行時都得重新解析程式碼,拿掉不必要的程式碼中可以省下一些解析程式碼的時間。

    但在 C 語言中,不需要刻意這樣做。因為 C 編譯器會將 C 程式碼編譯成機械碼,之後執行程式時不需要重新解析一次程式碼。所以對 C 程式碼用 minifier 是無意義的行為。

    細部的優化

    加減法比乘法快,乘法比除法快

    在代數運算中,加減法最快,乘法次之,除法和取餘數最慢。

    由於代數運算是基本語法,如果要改善效能的話,就要把一部分運算改為二元運算。但二元運算的可讀性較差,所以平常的運算不需刻意用二元運算取代。

    前置遞增減比後置遞增減快

    前置遞增會比後置遞增快,所以在迴圈中使用計數器時,用前置遞增可些微地改善程式的效能。

    無號整數比帶號整數快

    在進行整數運算時,無號整數會比帶號整數快一些,因為無號整數在運算時不需要檢查數值的正負號。所以,在迴圈中使用計數器時,使用無號整數來迭代會些微地改善程式效能。

    floatdouble

    在進行浮點數運算時,float 型態會比 double 型態來得快。若運算時不需在意小數點精確度,可考慮用 float 取代 double 型態。

    布林運算的順序

    在布林運算中,運算的順序會有細微的差距,因為布林運算會走捷徑。

    以 AND 運算來說,在 a && b 中,當 a 為偽 (false) 時,可知該布林運算一定為偽,故不會運算 b,省下一些運算的時間。同理,以 OR 運算來說,在 a || b 中,當 a 為真 (true) 時,可知該布林運算一定為真,故不會運算 b

    由此可知,藉由改變布林運算的順序,可以省下一些運算時間。

    if 敘述的順序

    在執行 if 敘述時,會由上至下逐一檢查條件,當符合條件時就結束檢查的動作。所以,在不影響程式邏輯正確性的前提下,刻意地將常見的情境往 if 敘述的上方擺,可以稍稍改善程式效能。

    switchif

    若比較的對象是整數型態,建議將 if 敘述改寫成等效的 switch 敘述,因為 if 敘述和 switch 運行的方式會有一些差異。if 敘述會由上而下逐行檢查,但 switch 敘述會直接跳躍到符合條件的區塊,故 switch 敘述會比等效的 if 敘述效能好一些些。

    迭代 (iteration) 比遞迴 (recursion) 快

    由於遞迴牽涉到函式呼叫,而函式呼叫會有語境轉換所帶來的額外開銷,所以遞迴在先天上會比等效的迭代來得慢一點。此外,C 編譯器在編譯程式時不保證尾遞迴優化 (tail call optimazation),故不需要刻意用這種手法寫遞迴程式。

    使用 lookup table 比控制結構快

    所謂的查表法,就是將原本需要即時運算的值預先運算後,將計算結果儲存在查找表中,之後不需運算,可直接透過查表快速取得值。

    在 C 或其他 C 家族語言中,會用靜態陣列來做為尋找表 (lookup table) 的資料結構。由於查表的演算法效率是 O(1),而且沒有複雜的運算,所以查表法取值相當快速。是典型用空間換取時間的例子。

    例如,一般的程式會用分支條件來區隔不同的值:

    #define  SUNDAY    0
    #define  MONDAY    1
    #define  TUESDAY   2
    #define  WEDSDAY   3
    #define  THURSDAY  4
    #define  FRIDAY    5
    #define  SATURDAY  6
    
    char * day_of_week(unsigned wday)
    {
        assert(wday < 7);
    
        switch (wday) {
        case WEDSDAY:
            return "Hump Day";
        case FRIDAY:
            return "Thanks God. It's Friday";
        case SATURDAY:
        case SUNDAY:
            return "Weekend";
        case MONDAY:
        case TUESDAY:
        case THURSDAY:
            return "Week";
        }
    }
    

    但我們改用查找表時,就把分支條件省略掉了:

    static char *_day_of_week[] = {"Weekend", "Week", "Week", "Hump Day", "Week", 
        "Thanks God. It's Friday", "Weekend"};
    
    char * day_of_week(unsigned wday)
    {
        assert(wday < 7);
    
        return _day_of_week[wday];
    }
    

    在這個例子中,沒有複雜的運算,所以兩段程式的效能差距不大。對於複雜的運算,即時運算和查表的效能差距會更大。

    查找表等於是把計算結果預先儲存在程式中,算是典型的用空間換取時間的例子。

    將簡短的函式改為 inline 函式或巨集

    C99 後,我們可以使用 inline 保留字來建議 C 編譯器特定函式視為 inline 函式。所謂的 inline 函式,相當於把函式的程式碼複製貼上到函式呼叫處,所以不會有函式呼叫時的開銷。

    由於 inline 只是對編譯器的建議,沒有強制性,若需要強制使用 inline 函式,可以使用 C 編譯器的延伸語法。以下 forceline 巨集摘自維基百科:

    #ifdef _MSC_VER
        #define forceinline __forceinline
    #elif defined(__GNUC__)
        #define forceinline inline __attribute__((__always_inline__))
    #elif defined(__CLANG__)
        #if __has_attribute(__always_inline__)
            #define forceinline inline __attribute__((__always_inline__))
        #else
            #define forceinline inline
        #endif
    #else
        #define forceinline inline
    #endif
    

    C89 時,沒有 inline 保留字。替代的方式是把函式改寫成等效的巨集。實際上的效果也是把巨集程式碼複製貼上巨集呼叫處,所以不會有函式呼叫的開銷。

    不論使用 inline 函式或是巨集,都會使程式體積變大,因為這兩種手法相當於在 C 專案中重覆複製貼上程式碼。如果程式體積很重要時,就不要使用這種手法。

    此外,濫用類函式巨集 (function-like macro) 會使得程式的可維護性變差。我們應該將巨集保留在簡單的任務上。

    傳遞指標而非資料

    當我們將較大的資料做為函式的參數來傳遞時,應該傳遞指向該資料的指標而非資料本身。因為傳遞函式參數時,C 語言會將參數拷貝一份。當我們傳遞指標時,只需拷貝指標,比起拷貝整個資料來說,會有效率得多。

    使用一維陣列儲存矩陣

    在實作矩陣時,會將矩陣元素以一維陣列儲存,而非多維陣列。參考以下結構體宣告:

    typedef struct matrix_t matrix_t;
    
    struct matrix_t {
        size_t row;
        size_t col;
        double *elements;
    };
    

    要存取矩陣元素時,會即使運算出相當應的索引值後,再將該索引值代入內部陣列,以存取值:

    size_t matrix_col(const matrix_t *self)
    {
        assert(self);
    
        return self->col;
    }
    
    size_t matrix_row(const matrix_t *self)
    {
        assert(self);
    
        return self->row;
    }
    
    double matrix_at(const matrix_t *self, size_t col, size_t row)
    {
        assert(col < matrix_col(self));
        assert(row < matrix_row(self));
    
        return self->elements[col + row * matrix_col(self)];
    }
    

    這是因為一維陣列在記憶體中是連續的區塊,但多維陣列則不一定。所以,存取一維陣列的元素會比較快一些。

    由於文章長度限制,我們在這裡不展示矩陣的實作。如果對實作矩陣有興趣的讀者,可參考這篇文章

    結語

    在本文中,我們介紹了一些常見的優化 C 程式碼的方式。由於優化程式碼不是強制性的任務,讀者不需要在撰寫 C 程式時刻意地使用所有網路上能查到的優化手法。反之,我們只需在必要時才進行優化,而且只優化關鍵的步驟即可。

    電子書籍

    如果讀者想要複習 C 程式設計相關的內容,可以參考以下書籍:

    現代 C 語言程式設計

    【分享本文】
    Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Yahoo
    【追蹤本站】
    Facebook Facebook Twitter Plurk