大規(guī)模C++工程單元測試性能優(yōu)化研究

劉堂臣,王雅文,宮云戰(zhàn)

(北京郵電大學(xué) 網(wǎng)絡(luò)與交換技術(shù)國家重點實驗室，北京 100876)

0 引言

隨著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，軟件的規(guī)模迅速膨脹，軟件測試的困難與代價也變得越來越大。軟件測試的基礎(chǔ)是單元測試，它可以在軟件的初期就發(fā)現(xiàn)很多故障，并且修改它們的成本也很低[1]。單元測試的效果會在很大程度上影響到后階段的測試，會進一步影響到產(chǎn)品的開發(fā)時間、費用和質(zhì)量[2]。

作者所在實驗室一直從事著軟件測試的研究工作，現(xiàn)有的代碼測試系統(tǒng)(CTS-CPP， code testing system for c plus plus)是一款基于JAVA語言編寫的測試C++工程的自動化單元測試工具，它可以對被測工程進行以函數(shù)為單元的模塊劃分，進而對各單元進行自動測試并生成測試用例，依據(jù)語句、分支和修訂條件判定覆蓋準(zhǔn)則統(tǒng)計出覆蓋率。CTS-CPP可以測試單個文件和小規(guī)模的C++工程，但是在測試大規(guī)模C++工程(含有多個 C++文件的工程，一般超過20個總代碼行數(shù)超過5 000行)時總是會出現(xiàn)內(nèi)存溢出故障。經(jīng)分析，CTS-CPP在測試C++工程時會為每一個CPP文件生成一個分析文件類對象(下文中簡稱被測對象)，當(dāng)生成的被測對象過多時將會消耗掉虛擬機所有內(nèi)存從而導(dǎo)致內(nèi)存溢出故障。如果將生成的被測對象全部序列化到磁盤中，需要用到的時候再進行反序列化操作，這樣是可以解決內(nèi)存溢出的故障，但是對每一個CPP文件都會對應(yīng)一對I/O操作，頻繁的I/O操作將會大大增加系統(tǒng)的測試時間[2]。

為了解決自動化單元測試工具中存在的以上問題，在測試流程中引入了緩存優(yōu)化[3-7]技術(shù)，通過將部分被測對象存儲到內(nèi)存中以提升訪問的速度。為了保證緩存的高命中率和高效性，提出了一種面向不同測試方式的緩存優(yōu)化方法。當(dāng)用戶直接對整個工程進行測試時，采用緩存預(yù)取的方法增加緩存的命中率；當(dāng)用戶對單個文件進行測試時，采用改進的GDSF算法(GDSF-UT， GDSF for unit test)進行緩存的替換。實驗表明，面向不同測試方式的緩存優(yōu)化方法能夠有效避免內(nèi)存溢出故障，提升緩存的命中率，減少測試所需的時間。

本文第1節(jié)對國內(nèi)外系統(tǒng)性能優(yōu)化的相關(guān)工作進行概述；第2節(jié)介紹緩存預(yù)取模型設(shè)計；第3節(jié)設(shè)計并實現(xiàn)GDSF-UT緩存替換算法；第4節(jié)介紹方法應(yīng)用后的實驗結(jié)果分析；第5節(jié)總結(jié)全文。

1 相關(guān)工作

隨著新技術(shù)的不斷發(fā)展，軟件規(guī)模也日益增大[8]，軟件的性能優(yōu)化研究已成為國內(nèi)外許多學(xué)者的重點研究方向，其中通過緩存優(yōu)化技術(shù)來提升系統(tǒng)整體的性能已經(jīng)成為主流的優(yōu)化方式之一。

目前國內(nèi)外有很多學(xué)者都在從事緩存優(yōu)化的研究工作。楊冬菊[9]等人為了保證在高并發(fā)、大用戶流量的場景下身份認(rèn)證系統(tǒng)能夠穩(wěn)定高效的運行，提出了基于緩存的分布式統(tǒng)一身份認(rèn)證機制。它通過將熱點數(shù)據(jù)預(yù)存到緩存中以提高響應(yīng)的速度，并結(jié)合復(fù)雜多樣的用戶行為提出了基于 Hybrid的多因素緩存替換算法。胡森森[10]等人通過總結(jié)超長指令字處理器發(fā)射寬度動態(tài)變化的特點，并利用其動態(tài)特征來驅(qū)動緩存的重構(gòu)，從而達(dá)到合并處理器核或動態(tài)分離的目的。王永功[11]等人分析了信息中心網(wǎng)絡(luò)的架構(gòu)，指出多跳LRU緩存中“緩存退化”的問題，提出一種基于預(yù)過濾的O(1)復(fù)雜度的改進算法，極大的增強了內(nèi)容分發(fā)效率。張艷[12]等人比較并分析傳統(tǒng)緩存模型MRM和IRM的思想，基于字節(jié)代價以及相對流行度的概念，提出滿足延遲時間、命中率和字節(jié)命中率等多種性能指標(biāo)要求的緩存優(yōu)化模型，并給出相關(guān)算法。劉磊[13]等人在研究緩存技術(shù)的過程中，提出了一種最小駐留價值的緩存替換算法，該算法結(jié)合對象大小和訪問頻率進行駐留價值的計算，優(yōu)先選取價值最小的對象進行替換，但是其忽略了緩存的使用時間和物理資源的使用情況。

綜上所述，針對緩存的研究，一方面是對緩存內(nèi)容和實現(xiàn)方法的研究，另一方面是對緩存替換算法的研究[14-15]。作者對單元測試工具的優(yōu)化也將從以上兩方面進行。

2 緩存預(yù)取模型的設(shè)計

當(dāng)用戶選擇直接對整個工程進行測試時，為了盡量減少I/O等待的時間，本節(jié)設(shè)計了一種緩存預(yù)取的模型，它借助一個緩存隊列將緩存預(yù)取模塊和文件測試模塊徹底解耦，使得原來只能串行執(zhí)行的兩個模塊現(xiàn)在可以并行執(zhí)行。

2.1 模型構(gòu)成

結(jié)合生產(chǎn)者-消費者的思想，本文設(shè)計的緩存預(yù)取模型如圖1所示。

圖1 緩存預(yù)取模型的基本構(gòu)成

該模型主要由以下6部分組成：

1)控制器主要負(fù)責(zé)各部件之間的任務(wù)調(diào)度和操作控制，并且負(fù)責(zé)與文件測試模塊之間的交互，使各部件有序穩(wěn)定的運行。

2)協(xié)調(diào)器主要負(fù)責(zé)接收對象生產(chǎn)部件和對象消費部件發(fā)送過來的數(shù)據(jù)，通過數(shù)據(jù)協(xié)調(diào)雙方的運行，并在參數(shù)對象中記錄數(shù)據(jù)。

3)對象生產(chǎn)部件主要負(fù)責(zé)預(yù)先批量的從磁盤中讀取對象放入緩存隊列中，并記錄讀取對象的個數(shù)和所消耗的時間，將數(shù)據(jù)發(fā)送給協(xié)調(diào)器。

4)對象消費部件主要負(fù)責(zé)從緩存隊列中讀取對象交給控制器處理，并記錄讀取對象的個數(shù)和測試所花的時間。

5)緩存隊列主要是用來存放預(yù)取出來的對象，其大小支持配置，避免對虛擬機內(nèi)存的過度使用從而導(dǎo)致內(nèi)存溢出故障。同時，它還支持同步阻塞，例如緩存隊列為空時，消費方將一直處于阻塞狀態(tài)，直到生產(chǎn)方調(diào)入下一批預(yù)取對象。

6)異常處理器主要負(fù)責(zé)對各部件運行過程中出現(xiàn)的異常進行捕捉處理。

2.2 預(yù)取機制

2.2.1 相關(guān)定義及符號表示

定義1:預(yù)取對象的總個數(shù)：指在測試C++工程時，需要生成的被測對象的總個數(shù)，記為CT。由于一個CPP文件對應(yīng)一個被測對象，所以該參數(shù)等于被測工程中CPP文件的個數(shù)。

定義2:緩存隊列的大小：指緩存隊列中最多能存放的被測對象的個數(shù)，記為QS。此參數(shù)限制了虛擬機內(nèi)存的使用量，避免發(fā)生內(nèi)存溢出故障。

定義3:生產(chǎn)總批次：指從磁盤中批量預(yù)取被測對象的總次數(shù)，記為PT。為了盡量減少I/O的次數(shù)，約定當(dāng)磁盤中未取被測對象個數(shù)大于等于QS時，按QS大小來預(yù)取。因此在數(shù)量上PT可以表示為：

(1)

定義4:每批生產(chǎn)被測對的數(shù)量：指每批從磁盤中預(yù)取到緩存隊列中被測對象的個數(shù)，記為QSi，其中，i表示生產(chǎn)批次(1≤i≤PT)。在數(shù)量上，QSi可以表示為：

(2)

定義5:每次消費的被測對象個數(shù)：指每次從緩存隊列中取出的被測對象的個數(shù)，記為CO。由于每次都是從緩存隊列中取出一個被測對象用于測試，測試完畢后再取下一個，所以該參數(shù)的大小恒為1，可以表示為：

CO=1

(3)

定義6:生產(chǎn)一批被測對象的開始時間和結(jié)束時間：指每次批量從磁盤中讀取被測對象的開始時間和結(jié)束時間，分別記為TPSi和TPEi，其中，i表示生產(chǎn)批次(1≤i≤PT)。

定義7:生產(chǎn)一批被測對象所消耗的時間：指從磁盤預(yù)取一批被測對象到緩存隊列中所消耗的時間，記為ΔTPi，其中，i表示生產(chǎn)批次(1≤i≤PT)。在數(shù)量上，該參數(shù)等于每批生產(chǎn)的結(jié)束時間與每批生產(chǎn)的開始時間的差值，可以表示為：

ΔTPi=TPEi-TPSi

(4)

定義8:消費一個被測對象的開始時間和結(jié)束時間：指從緩存隊列中取出一個被測對象的時間和被測對象測試完畢的時間，分別記為TCSi,j和TCEi,j，其中，i表示生產(chǎn)批次(1≤i≤PT),j表示緩存隊列中的第j個元素(1≤j≤QSi)。

定義9:消費一個被測對象所需的時間：指消費方從緩存隊列中取出被測對象到測試完畢所消耗的時間，記為ΔTCi,j，其中，i表示生產(chǎn)批次(1≤i≤PT),j表示緩存隊列中的第j個元素(1≤j≤QSi)。在數(shù)量上，該參數(shù)等于消費一個被測對象的結(jié)束時間與開始時間的差值，可以表示為:

ΔTCi,j=TCEi,j-TCSi,j

(5)

定義10:消費一批被測對象所需的時間：指從緩存隊列中取出第一個被測對象開始到同一批被測對象全部測試完畢所消耗的總時間，記為ΔTCi，其中，i表示生產(chǎn)批次(1≤i≤PT)。如圖 2所示，ΔTCi,1表示消費第i批第1個被測對象所需的時間，ΔTCi,2表示消費第i批第2個被測對象所需的時間，以此類推，ΔTCi,j(1≤j≤QSi)表示消費第i批第j個被測對象所需的時間，該參數(shù)表示它們的總和。

圖2 批量消費與單個消費所需時間關(guān)系示意圖

在數(shù)量上可以表示為：

(6)

2.2.2 等待時間

緩存預(yù)取模型設(shè)計的核心目的就是盡量減少等待I/O的時間，為了達(dá)到這一目的，模型采取了兩點關(guān)鍵的設(shè)計：1)將原來串行執(zhí)行的緩存預(yù)取模塊和文件測試模塊通過一個緩存隊列實現(xiàn)解耦，使得兩模塊在一定程度上可以并行執(zhí)行；2)采用批量預(yù)取的方式，減少I/O的次數(shù)。

消費方在消費一批被測對象之前需要先等待生產(chǎn)方生產(chǎn)完畢，這一等待時間即為CPU等待I/O的時間，記為ΔTWi，其中，i表示生產(chǎn)批次(1≤i≤PT)。如圖 3所示，ΔTP1表示生產(chǎn)第1批被測對象所消耗的時間，此時，緩存隊列還為空，消費方需要等待ΔTW1的時間，然后生產(chǎn)方和消費方開始并行執(zhí)行，ΔTP2表示生產(chǎn)第2批被測對象所消耗的時間，ΔTC1表示消費第1批被測對象所需要的時間，它們的差值即為ΔTW2，如果ΔTC1≥ΔTP2，說明消費第1批比生產(chǎn)第2批花費的時間更長，此時消費完第1批第2批已經(jīng)生產(chǎn)完畢，因此ΔTW2等于0。以此類推，ΔTPi表示生產(chǎn)第i批被測對象所消耗的時間；ΔTCi-1表示消費第i-1批被測對象所需要的時間，它們的差值即為ΔTWi，如果ΔTCi-1≥ΔTPi，說明消費第i-1批比生產(chǎn)第i批花費的時間更長，此時消費完第i-1批第i批已經(jīng)生產(chǎn)完畢，因此ΔTWi等于0。

圖3 生產(chǎn)時間消費時間等待時間關(guān)系示意圖

ΔTWi在數(shù)量上可以表示為：

(7)

條件2：2≤i≤PT&&ΔTPi>ΔTCi-1；

條件3：2≤i≤PT&&ΔTPi≤ΔTCi-1；

整個測試流程等待I/O的總時間即為各批次等待I/O時間之和，記為ΔTW。在數(shù)量上，可以表示為：

(8)

2.2.3 預(yù)取流程

當(dāng)單元測試工具啟動對一個工程進行單元測試時，緩存預(yù)取模型的運行流程如下:

1)通過參數(shù)配置模塊配置緩存隊列的大小，通過控制器將配置的參數(shù)寫入到參數(shù)對象中；

2)消費方和生產(chǎn)方同時啟動，此時緩存隊列為空，消費方進入阻塞狀態(tài)，生產(chǎn)方開始預(yù)取數(shù)據(jù)，記錄開始時間和結(jié)束時間，通過公式(4)計算出生產(chǎn)當(dāng)前批被測對象所消耗的時間ΔTP1；

3)消費方阻塞ΔTW1(數(shù)值上等于ΔTP1)后被喚醒，與生產(chǎn)方開始并行執(zhí)行；

4)消費方從緩存隊列中一個一個取出被測對象并進行單元測試，記錄每一個被測對象消費的開始時間和結(jié)束時間，通過公式(5)計算出消費當(dāng)前被測對象所需的時間，通過公式(6)進一步計算出消費當(dāng)前批被測對象所需的時間ΔTCi-1(2≤i≤PT)；

5)生產(chǎn)方與步驟4)并行執(zhí)行，預(yù)取下一批的被測對象，記錄預(yù)取的開始時間和結(jié)束時間，通過公式(4)計算出生產(chǎn)下一批被測對象所消耗的時間ΔTPi(2≤i≤PT)；

6)根據(jù)公式(7)計算出當(dāng)前批的等待時間ΔTWi；

7)重復(fù)執(zhí)行步驟4)～6)，直到i=PT；

8)根據(jù)公式(8)計算出整個流程中等待I/O的時間。

3 緩存替換算法的設(shè)計

當(dāng)用戶選擇對工程下的單個文件進行測試時，如果選中文件的被測對象恰好在緩存中，將會少一次I/O操作，從而節(jié)省測試的時間。所以一個高命中率的緩存替換算法就顯得尤為重要。本節(jié)在目前廣泛被使用的GDSF緩存替換算法的基礎(chǔ)上，進一步考慮了單元測試的空間局部性特征和測試結(jié)果等因素的影響，提出了GDSF-UT緩存替換算法。

3.1 GDSF算法

GDSF算法[16-18]是緩存替換算法中考慮影響因素相對比較全面的一種算法，相對傳統(tǒng)考慮影響因素比較單一的算法具有較高的命中率，因此也被廣泛的使用。它綜合考慮了對象的大小、對象訪問頻率、時間和引入對象到緩存所需的代價的影響[19]，通過這些影響因素計算緩存中對象的權(quán)重，當(dāng)緩存空間滿時，替換出緩存中權(quán)重最小的對象[20]。計算公式為：

(9)

式中，O為緩存對象；W(O)代表緩存對象的權(quán)重；L為膨脹因子，初始值為0，每次需要緩存替換時，L被重新賦值為當(dāng)前緩存中最小的權(quán)重值；Ffreq(O)為緩存對象的訪問頻次，初始值為1，之后每命中一次其值加1；Size(O)為緩存對象的大小；Cost(O)為將對象從磁盤取回到緩存所需的代價。

雖然GDSF算法考慮了比較多的影響因素，且容易實現(xiàn)，計算開銷也比較小，但是用在單元測試工具中就缺乏對測試結(jié)果、測試行為特征等因素的考慮，接下來將在此算法的基礎(chǔ)上設(shè)計面向單元測試工具的緩存替換算法GDSF-UT。

3.2 GDSF-UT算法

3.2.1 相關(guān)概念

設(shè)S={O1，O2，O3，…，Om，…，On}表示被測對象的集合，其下標(biāo)1…n表示在文件系統(tǒng)中的相對位置。

定義1:對象距離：指兩個被測對象在文件系統(tǒng)中相對位置的差值，記為Dmn，其中，m、n分別表示兩個被測對象在文件系統(tǒng)中的相對位置。在數(shù)值上，該參數(shù)等于m與n差值的絕對值，可以表示為：

Dmn=|m-n|

(10)

定義2:分支覆蓋率：指程序中被測試執(zhí)行的判定和分支數(shù)占判定和分支總數(shù)的比率，記為BCR。

定義3:語句覆蓋率：指程序中被測試執(zhí)行的語句數(shù)占可執(zhí)行的語句總數(shù)的比率，記為SCR。

定義4:修訂條件/判定覆蓋率：簡稱MC/DC，它是一種特殊的分支覆蓋率，它不但會使用分支覆蓋率報告復(fù)雜條件下的TRUE和FALSE輸出，同時也會報告復(fù)雜條件下的全部分支條件輸出，記為MDCR。

3.2.2 算法描述

用戶在對單個被測對象進行測試時的行為特征包括：所測試的對象具有很強的空間局部性，即一段時間內(nèi)連續(xù)多次的測試行為通常只發(fā)生在相鄰的一些對象中，也就是對象距離越小，被選中測試的概率就越大；測試結(jié)果的好壞也將會影響再次被選中測試的概率(測試結(jié)果的好壞由定義2、3、4給出的覆蓋率來評判)，測試結(jié)果越好，再次被選中測試的概率就越小，測試結(jié)果越差，再次被選中測試的概率就越大。此部分的影響因素用P來表示，計算方式如下：

(11)

式中，Oi為緩存權(quán)重計算對象，Oj為訪問對象。

結(jié)合用戶測試行為特征的影響，改進后的算法GDSF-UT的權(quán)重計算公式為：

(12)

GDSF-UT算法在原有算法基礎(chǔ)上進一步考慮了用戶測試行為特征的影響，由此進一步優(yōu)化了緩存權(quán)重的計算公式，可以看出改進后的算法在單元測試工具中具有較強的適應(yīng)性。

3.2.3 算法流程

GDSF-UT算法的請求處理流程如圖 4所示。

圖4 GDSF-UT算法的請求處理流程圖

由圖 4可以看出，當(dāng)用戶發(fā)出對象請求時，首先判斷緩存中是否有該對象。如果有，更新緩存對象的權(quán)重并返回對象；如果沒有，則需要從磁盤中反序列化出對象，然后判斷緩存是否已滿。如果已滿，替換出權(quán)重最小的對象并更新緩存對象的權(quán)重，然后返回對象；如果緩存沒有滿，則直接將對象放入緩存并更新緩存對象的權(quán)重，然后返回對象。

4 實驗及實驗結(jié)果分析

為了驗證緩存預(yù)取模型和GDSF-UT替換算法的有效性，本文選取了5個不同規(guī)模的開源C++工程在CTS-CPP中進行測試實驗，它們的工程屬性如表1所示。

表1 C++代碼工程的屬性列表

4.1 實驗環(huán)境

本文實驗中，CTS-CPP運行在lenovo臺式機上，CPU型號為Intel(R) Core(TM) i5-1038NG7，CPU頻率為3.80 GHz，物理內(nèi)存為8 GB，操作系統(tǒng)為Windows 10 專業(yè)版，編譯器為VC14，開發(fā)平臺為Eclipse，開發(fā)語言為Java，虛擬機最大內(nèi)存設(shè)置為512 M。

4.2 實驗結(jié)果及分析

4.2.1 緩存預(yù)取模型對性能的影響

為了評估緩存預(yù)取模型對CTS-CPP性能的影響，本文對5個不同規(guī)模的測試工程進行了工程級別的測試，分別記錄了優(yōu)化前、每次從磁盤讀取和采用預(yù)取機制3種情況下對整個工程進行模塊劃分所需的時間，同時也統(tǒng)計出了每次從磁盤讀取和采用預(yù)取機制2種情況下CPU等待I/O 的總時間，具體實驗結(jié)果如表2所示，表中的OOM代表發(fā)生內(nèi)存溢出故障。為了避免緩存隊列大小對實驗結(jié)果的影響，本文實驗將其設(shè)置為60。

從表2可以發(fā)現(xiàn)：當(dāng)被測工程規(guī)模較小，即內(nèi)存中能存放下所有被測對象，優(yōu)化前的方案模塊劃分的速度是最快的；當(dāng)被測工程規(guī)模越來越大，優(yōu)化前的方案將會發(fā)生內(nèi)存溢出故障，采用每次從磁盤讀取和預(yù)取機制可以有效避免內(nèi)存溢出故障，但模塊劃分的時間也越來越長，采用預(yù)取機制相比每次從磁盤讀取平均節(jié)約15%左右的時間；CPU等待I/O的總時間

表2 緩存預(yù)取模型對性能的影響評估

方面，每次從磁盤讀取等待的總時間隨著工程規(guī)模增大而變長，而采用預(yù)取機制的等待總時間穩(wěn)定在第一批被測對象預(yù)取完成所需的時間附近，因為由實驗結(jié)果發(fā)現(xiàn)，測試完上一批所需的時間遠(yuǎn)大于下一批的預(yù)取時間，因此測試完上一批后不需要等待I/O，即ΔTWi=0(2≤i≤PT)，隨著被測工程規(guī)模的增大，兩種方案等待I/O總時間的差值就越大，采用預(yù)取機制節(jié)省的時間就越多。

4.2.2 GDSF-UT替換算法對性能的影響

為了評估GDSF-UT替換算法對CTS-CPP性能的影響，本文對5個不同規(guī)模的測試工程進行了文件級別的測試，分別記錄了優(yōu)化前、每次從磁盤讀取、采用GDSF算法和采用GDSF-UT算法4種情況下抽樣測試單個文件的平均響應(yīng)時間，同時也統(tǒng)計出了采用GDSF算法和采用GDSF-UT算法2種情況下的緩存命中率，具體實驗結(jié)果如表3所示。

表3 GDSF-UT替換算法對性能的影響評估

從表3可以發(fā)現(xiàn)：當(dāng)被測工程規(guī)模較小，即內(nèi)存中能存放下所有被測對象，此時的緩存命中率都為100%，優(yōu)化前、采用GDSF算法和采用GDSF-UT算法測試單個文件的平均響應(yīng)時間幾乎相等；針對同一被測工程，在緩存放不下所有被測對象前提下，每次從磁盤讀取、采用GDSF算法和采用GDSF-UT算法測試單個文件的平均響應(yīng)時間依次減小；隨著被測工程規(guī)模越來越大，由于緩存的大小一定，所以緩存命中率越來越低，但GDSF-UT算法的命中率比GDSF算法的命中率平均高出4～5個百分點。

5 結(jié)束語

針對單元測試工具無法測試大規(guī)模C++工程且耗時較長這一問題，在測試流程中引入了緩存優(yōu)化技術(shù)，并提出了一種面向不同測試方式的緩存優(yōu)化方法。對于工程級別的測試，本文提出了一種緩存預(yù)取模型；對于文件級別的測試，本文提出了改進的GDSF緩存替換算法。實驗結(jié)果表明，該方法使得被測工程規(guī)模從5 000多行擴大至十幾萬行，大大提升了單元測試工具的性能，使其在軟件規(guī)模迅速膨脹的今天具有更強的適用性。同時，該方法提升了單元測試工具的響應(yīng)速度，縮短了測試所需要的時間，為單元測試工作節(jié)省了人力成本和時間成本，具有較高的應(yīng)用價值。在下一步研究工作中，由于被測工程規(guī)模較大，生成的測試用例數(shù)量將會急劇增加，要執(zhí)行所有的測試用例幾乎是不可能的，因此，接下來將重點研究測試用例約簡方法。