王峰 閻娟 張浩軍

關(guān)鍵詞：編譯原理；代碼優(yōu)化；實(shí)踐教學(xué)

1引言

“編譯原理”是一門重要的計(jì)算機(jī)專業(yè)課程，通過(guò)該課程的學(xué)習(xí)和實(shí)踐，既可加深學(xué)生對(duì)程序設(shè)計(jì)語(yǔ)言的設(shè)計(jì)與實(shí)現(xiàn)等知識(shí)的綜合理解，又可多角度地提高實(shí)踐動(dòng)手能力及綜合應(yīng)用能力[1-3]。特別是，“編譯原理”課程與計(jì)算思維具有緊密的聯(lián)系，為培養(yǎng)學(xué)生的計(jì)算思維能力提供了一個(gè)良好的平臺(tái)[4]。但“編譯原理”具有內(nèi)容多、概念多、理論性強(qiáng)、高度抽象等特點(diǎn)，被普遍認(rèn)為是一門既難教又難學(xué)的課程。

該課程中的代碼優(yōu)化主要是針對(duì)編譯器，但大部分由編譯器執(zhí)行的優(yōu)化僅涉及控制流程的簡(jiǎn)化和變量的訪問(wèn)方式等，并且由于大部分學(xué)生畢業(yè)后并不會(huì)從事編譯器的設(shè)計(jì)工作，因此很多學(xué)生會(huì)覺得相關(guān)理論知識(shí)的作用不大。同時(shí)，隨著計(jì)算機(jī)硬件技術(shù)的飛速發(fā)展，計(jì)算機(jī)的計(jì)算能力日益增強(qiáng)，因此學(xué)生在學(xué)習(xí)程序設(shè)計(jì)語(yǔ)言的時(shí)候?qū)⒏嗟木Ψ旁诹顺绦蜻壿嫷膶?shí)現(xiàn)上，而忽略了代碼優(yōu)化，從而導(dǎo)致學(xué)生對(duì)優(yōu)化相關(guān)知識(shí)的重要性認(rèn)識(shí)不足。實(shí)際上，代碼優(yōu)化在軟件開發(fā)過(guò)程中，特別是在嵌入式等對(duì)實(shí)時(shí)性要求較高的系統(tǒng)開發(fā)中的作用是非常大的。本文針對(duì)工程型和應(yīng)用型人才培養(yǎng)的目標(biāo)，以圖像處理中將RGB格式的彩色圖像轉(zhuǎn)換為灰度圖像為例，探討編譯原理中代碼優(yōu)化相關(guān)技術(shù)在實(shí)際工程中的應(yīng)用，以加深學(xué)生對(duì)編譯理論知識(shí)的理解，建立理論和實(shí)際的聯(lián)系，強(qiáng)化實(shí)踐動(dòng)手能力，從而提高學(xué)生的編程能力和綜合素質(zhì)。

2代碼優(yōu)化概述

代碼優(yōu)化是編譯程序中的一個(gè)重要環(huán)節(jié)，其實(shí)質(zhì)是對(duì)代碼進(jìn)行等價(jià)變換，目的是提高由編譯程序生成的目標(biāo)程序的質(zhì)量，即加快目標(biāo)程序的運(yùn)行速度或減少目標(biāo)程序所占的存儲(chǔ)空間，或兩者兼具[5-7]。

代碼優(yōu)化是為了編寫出更高效的代碼，故在進(jìn)行代碼優(yōu)化時(shí)須遵循三個(gè)原則：（1）等價(jià)原則，即優(yōu)化不能改變程序的運(yùn)行結(jié)果；（2）有效原則，即優(yōu)化后的代碼應(yīng)比未優(yōu)化代碼具有更高的時(shí)空效率；（3）盈利或合算原則，即優(yōu)化帶來(lái)的利益應(yīng)大于優(yōu)化工作所付出的代價(jià)。

按照與機(jī)器的關(guān)系，代碼優(yōu)化可分為與機(jī)器無(wú)關(guān)的優(yōu)化和與機(jī)器相關(guān)的優(yōu)化，二者在編譯程序中所處的階段是不一樣的，前者是在源程序或中間代碼上進(jìn)行優(yōu)化：后者是在目標(biāo)代碼上進(jìn)行優(yōu)化。在與機(jī)器無(wú)關(guān)的優(yōu)化中，根據(jù)它所涉及的程序范圍可分為局部?jī)?yōu)化、循環(huán)優(yōu)化和全局優(yōu)化三個(gè)不同的級(jí)別。局部?jī)?yōu)化是在基本塊內(nèi)的優(yōu)化，循環(huán)優(yōu)化是對(duì)循環(huán)中的代碼進(jìn)行優(yōu)化，而全局優(yōu)化則是在整個(gè)程序范圍內(nèi)的優(yōu)化。優(yōu)化方法包括數(shù)據(jù)流分析、控制流分析和程序變換等。代碼優(yōu)化的不同分類及相關(guān)優(yōu)化技術(shù)如表1所列。

3代碼優(yōu)化實(shí)踐教學(xué)

“編譯原理”課程中的代碼優(yōu)化都是針對(duì)編譯程序的中間代碼和目標(biāo)代碼進(jìn)行的，而學(xué)生平常接觸更多的是源代碼，并且將來(lái)也更多的是從事源代碼的開發(fā)工作。因此，學(xué)生對(duì)相關(guān)理論知識(shí)在實(shí)際工程中的應(yīng)用缺乏了解，從而對(duì)相關(guān)優(yōu)化知識(shí)的掌握不夠深入，也較難將相關(guān)優(yōu)化知識(shí)應(yīng)用于實(shí)際編程中。實(shí)際上，在嵌入式系統(tǒng)等實(shí)時(shí)性要求較高的應(yīng)用中，代碼優(yōu)化是一個(gè)非常重要的環(huán)節(jié)。本節(jié)以圖像處理中最基本的彩色圖像轉(zhuǎn)換為灰度圖像為例，討論相關(guān)編譯優(yōu)化知識(shí)在實(shí)際工程中的應(yīng)用，以增進(jìn)學(xué)生對(duì)編譯優(yōu)化知識(shí)的了解，提高學(xué)生的編程能力。

3.1問(wèn)題描述

在圖像模式識(shí)別工程中，為了便于處理和識(shí)別，經(jīng)常需要將RGB格式的彩色圖像轉(zhuǎn)換為灰度圖像，圖像轉(zhuǎn)換公式[8]為：

其中，R，G，B分別代表每個(gè)像素在RGB顏色空間中的紅、綠和藍(lán)三個(gè)顏色分量，Y為變換后所得灰度圖像中像素的灰度級(jí)，其取值均為[0，255]的整數(shù)。本節(jié)中圖像大小為720*576*24bit。

3.2優(yōu)化實(shí)踐

為實(shí)現(xiàn)上述功能，首先，定義如下數(shù)據(jù)結(jié)構(gòu)：

步驟1：變換循環(huán)控制條件

上述代碼是按照“先列后行”的順序來(lái)對(duì)二維數(shù)組進(jìn)行遍歷的，而在C語(yǔ)言中，一個(gè)二維數(shù)組在計(jì)算機(jī)中存儲(chǔ)時(shí)，是按照“先行后列”的順序依次存儲(chǔ)的。因此，“先列后行”遍歷發(fā)生的頁(yè)面交換次數(shù)要比“先行后列”多，且cache命中率相對(duì)較低。所以，通過(guò)調(diào)整語(yǔ)句順序，變換循環(huán)控制條件，可以將上述函數(shù)修改為：

步驟2：數(shù)據(jù)結(jié)構(gòu)優(yōu)化

因圖像為二維數(shù)據(jù)，故直接采用二維數(shù)組來(lái)存儲(chǔ)圖像數(shù)據(jù)，代碼較直觀、可讀性強(qiáng)。但編譯器處理二維數(shù)組的效率低于一維數(shù)組，因此可改用一維數(shù)組來(lái)存儲(chǔ)圖像數(shù)據(jù)，即將變量定義為：

經(jīng)上述優(yōu)化后，函數(shù)的運(yùn)行時(shí)間下降為9.80ms。

步驟3：合并已知量，刪除無(wú)用代碼

上述代碼循環(huán)內(nèi)存在無(wú)用賦值的情況，刪除多余變量和對(duì)應(yīng)的賦值語(yǔ)句，合并已知量，即得：優(yōu)化后函數(shù)的運(yùn)行時(shí)間變?yōu)?.06ms。

步驟4：代數(shù)變換

上述代碼中最主要的運(yùn)算在于對(duì)每個(gè)像素點(diǎn)利用公式（1）進(jìn)行的浮點(diǎn)數(shù)運(yùn)算。顯然，計(jì)算機(jī)對(duì)整數(shù)的運(yùn)算速度要快于浮點(diǎn)運(yùn)算，因此應(yīng)用代數(shù)變換可將此操作改為整數(shù)運(yùn)算，經(jīng)此優(yōu)化后，函數(shù)的運(yùn)行日寸間進(jìn)一步縮短為3.37ms。

步驟5：強(qiáng)度削弱（移位實(shí)現(xiàn)除法）

由于計(jì)算機(jī)的移位操作速度快于除法，因此可以利用移位操作來(lái)實(shí)現(xiàn)上述除法運(yùn)算，從而降低運(yùn)算強(qiáng)度，即將上述代碼改為：經(jīng)此優(yōu)化后，函數(shù)的運(yùn)行時(shí)間進(jìn)一步減少為2.82ms。

步驟6：強(qiáng)度削弱（查表）

在上述代碼中，每個(gè)像素的R，G和B值都需要進(jìn)行乘法運(yùn)算，由于這三個(gè)變量的取值范圍均為[0，255]，因此可以通過(guò)在外定義查找表的方法來(lái)減少計(jì)算量，即將此范圍內(nèi)的值分別乘以306、601和1 17并進(jìn)行移位操作，然后將計(jì)算得到的值用三個(gè)數(shù)組分別加以存儲(chǔ)．即：

在此基礎(chǔ)上，循環(huán)內(nèi)的每個(gè)像素不須計(jì)算便可直接通過(guò)查找表的方法快速實(shí)現(xiàn)灰度轉(zhuǎn)換

顯然，這也是一種以犧牲內(nèi)存為代價(jià)節(jié)省計(jì)算時(shí)間的方法，經(jīng)過(guò)此優(yōu)化后，函數(shù)運(yùn)行時(shí)間進(jìn)一步降低為1.93ms。

步驟7：循環(huán)展開

在上述代碼的循環(huán)體內(nèi)，因各像素的轉(zhuǎn)換是獨(dú)立進(jìn)行的，不存在數(shù)據(jù)依賴，故可以進(jìn)行循環(huán)展開，減少循環(huán)迭代次數(shù)，有利于CPU的流水線工作，從而提高運(yùn)行速度。比如，將函數(shù)改為：

上文各步驟優(yōu)化后的函數(shù)運(yùn)行時(shí)間變化如圖1所示。從圖1可以看出，經(jīng)過(guò)上述各步驟的優(yōu)化后，函數(shù)運(yùn)行時(shí)間從優(yōu)化前的21.96ms下降為1.63ms，優(yōu)化效果非常明顯。

上述優(yōu)化實(shí)例中包含局部?jī)?yōu)化、循環(huán)優(yōu)化、與機(jī)器無(wú)關(guān)的優(yōu)化和與機(jī)器相關(guān)的優(yōu)化等知識(shí)。同時(shí)，為進(jìn)一步增強(qiáng)學(xué)生的工程應(yīng)用能力，在教學(xué)中還補(bǔ)充了對(duì)相關(guān)程序分析工具的介紹。在大型實(shí)際開發(fā)項(xiàng)目中，可以利用GProf和dotTrace等工具來(lái)發(fā)現(xiàn)程序中的瓶頸，并有針對(duì)性地進(jìn)行代碼優(yōu)化，從而提高系統(tǒng)的運(yùn)行效率。

4結(jié)束語(yǔ)

針對(duì)“編譯原理”課程教學(xué)中的代碼優(yōu)化，本文在簡(jiǎn)要介紹其原理和相關(guān)優(yōu)化技術(shù)的基礎(chǔ)上，重點(diǎn)從實(shí)踐教學(xué)的角度，以圖像模式識(shí)別工程中的圖像格式轉(zhuǎn)換為例，探討了相關(guān)編譯優(yōu)化技術(shù)在實(shí)際工程中的應(yīng)用。通過(guò)面向?qū)嶋H應(yīng)用的優(yōu)化實(shí)踐教學(xué)，有助于提高學(xué)生對(duì)課程的重視程度，調(diào)動(dòng)學(xué)生的積極性和主動(dòng)性，培養(yǎng)學(xué)生的實(shí)踐創(chuàng)新能力，幫助學(xué)生在深入了解編譯器工作原理和優(yōu)化技術(shù)的基礎(chǔ)上，提高代碼編寫的質(zhì)量。同時(shí)，也能將編譯原理和程序設(shè)計(jì)語(yǔ)言、操作系統(tǒng)等課程的相關(guān)知識(shí)聯(lián)系起來(lái)，從而可以從多角度提高學(xué)生的綜合應(yīng)用能力，切實(shí)有效地提高學(xué)生的專業(yè)素質(zhì)，并在實(shí)踐中取得較好的教學(xué)效果。