一種基于序列模式挖掘的trace探測(cè)方法

潘 龍 廖湖聲 蘇 航

1(北京工業(yè)大學(xué)計(jì)算機(jī)學(xué)院 北京 100124) 2(北京工業(yè)大學(xué)軟件學(xué)院 北京 100124)

0 引 言

即時(shí)編譯技術(shù)JIT compilation(just in-time compilation)是一種在程序運(yùn)行時(shí)刻識(shí)別出其中頻繁運(yùn)行的程序片段，并將其編譯為目標(biāo)代碼然后執(zhí)行的程序優(yōu)化技術(shù)，可以有效地提升程序執(zhí)行效率，最早可追溯至20世紀(jì)60年代McCarthy提出的在運(yùn)行時(shí)刻翻譯的函數(shù)。即時(shí)編譯技術(shù)可以分為基于方法和基于蹤跡(trace)兩種，其中基于方法的即時(shí)編譯對(duì)頻繁執(zhí)行的整個(gè)方法進(jìn)行編譯，粒度較大；基于trace的即時(shí)編譯在運(yùn)行時(shí)動(dòng)態(tài)地識(shí)別出頻繁執(zhí)行的代碼序列，并將其作為編譯的基本單元，粒度較小，可以減少整體編譯時(shí)間并提高目標(biāo)代碼質(zhì)量。

數(shù)據(jù)挖掘是從大量數(shù)據(jù)中挖掘有價(jià)值的模式的核心過(guò)程，旨在提取有效的、新穎的、潛在有用的、易被理解的知識(shí)。序列模式挖掘作為數(shù)據(jù)挖掘的一個(gè)重要研究方向，是一種在序列數(shù)據(jù)庫(kù)中挖掘頻繁出現(xiàn)的子序列作為模式的知識(shí)發(fā)現(xiàn)過(guò)程。序列模式挖掘在基因序列分析、購(gòu)物行為分析，商業(yè)分析等實(shí)際領(lǐng)域得到了廣泛應(yīng)用。應(yīng)用序列模式挖掘，能夠發(fā)現(xiàn)潛在的知識(shí)，幫助決策者進(jìn)行更好的決策和規(guī)劃，從而獲得巨大的經(jīng)濟(jì)效益與社會(huì)效益。程序解釋執(zhí)行過(guò)程中，按順序執(zhí)行的基本塊便可以看作是序列數(shù)據(jù)。

服務(wù)器端程序運(yùn)行于網(wǎng)絡(luò)環(huán)境下，服務(wù)器響應(yīng)用戶請(qǐng)求的解釋型語(yǔ)言程序通常是動(dòng)態(tài)生成或用戶提交的，無(wú)法事先進(jìn)行編譯優(yōu)化處理，可以使用即時(shí)編譯技術(shù)提高程序執(zhí)行效率。同時(shí)，服務(wù)器端程序具有并發(fā)執(zhí)行的特點(diǎn)，并發(fā)執(zhí)行的解釋型程序可以看作是多個(gè)基本塊序列，通過(guò)對(duì)這些基本塊序列應(yīng)用序列模式挖掘，可以識(shí)別服務(wù)端程序中的熱點(diǎn)代碼序列，即熱點(diǎn)trace。服務(wù)器端的trace探測(cè)能夠利用服務(wù)器端并發(fā)的特點(diǎn)，更為高效地識(shí)別trace，從而提升程序執(zhí)行效率，提高用戶請(qǐng)求的響應(yīng)速度。

為了更好地識(shí)別服務(wù)器端程序中的熱點(diǎn)trace，提高服務(wù)器端程序的請(qǐng)求處理速度，本文提出了一種基于序列模式挖掘的trace探測(cè)方法，將并發(fā)執(zhí)行的服務(wù)器端程序產(chǎn)生的多個(gè)基本塊序列作為序列數(shù)據(jù)庫(kù)，通過(guò)識(shí)別其中的序列模式來(lái)發(fā)現(xiàn)程序中的熱點(diǎn)trace，解決了現(xiàn)有的trace探測(cè)方法無(wú)法針對(duì)服務(wù)器端程序進(jìn)行高效探測(cè)的問(wèn)題。該方法主要分為基本塊數(shù)據(jù)準(zhǔn)備、序列模式挖掘和序列模式去重與合并三個(gè)部分，在序列模式挖掘部分設(shè)計(jì)并提出了Pisat算法，用于識(shí)別熱點(diǎn)trace。實(shí)驗(yàn)結(jié)果表明這種方法有效地提高了熱點(diǎn)trace的探測(cè)效率。

1 相關(guān)工作

1.1 基于trace的即時(shí)編譯

基于trace的即時(shí)編譯是一種在運(yùn)行時(shí)動(dòng)態(tài)地識(shí)別出頻繁執(zhí)行的代碼序列，并將其作為編譯的基本單元的技術(shù)。第一個(gè)實(shí)現(xiàn)基于trace的即時(shí)編譯系統(tǒng)是Dynamo[1]，它是一個(gè)能提高指令流執(zhí)行效率的動(dòng)態(tài)優(yōu)化系統(tǒng)。DynamoRIO[2]對(duì)Dynamo進(jìn)行了擴(kuò)展，它能夠動(dòng)態(tài)地減少解釋過(guò)程中的開銷，然而DynamoRIO的trace仍然在機(jī)器指令層面，沒有包含解釋器層面的高級(jí)信息，一些編譯優(yōu)化在這一層面也無(wú)法進(jìn)行。

2006年，Gal等[3]開發(fā)了第一個(gè)針對(duì)高級(jí)語(yǔ)言的基于trace的虛擬機(jī)HotpathVM，它將字節(jié)碼作為探測(cè)對(duì)象。該虛擬機(jī)動(dòng)態(tài)地探測(cè)頻繁運(yùn)行的字節(jié)碼，將這些字節(jié)碼編譯為SSA(Static Single Assignment)作為中間表示，并將其翻譯為機(jī)器碼。

H?ubl等[4]基于HotSpot虛擬機(jī)，開發(fā)基于trace的即時(shí)編譯系統(tǒng)。但該解決方案不能跨越函數(shù)，trace都很短小，節(jié)約了探測(cè)和編譯的時(shí)間，但增大了環(huán)境切換的開銷。

2015年，陶勝召等[5]提出了基于trace的CMinus語(yǔ)言即時(shí)編譯技術(shù)，在該技術(shù)中，CMinus程序經(jīng)過(guò)詞法分析和語(yǔ)法分析之后得到抽象語(yǔ)法樹，并按照一定的規(guī)則將其轉(zhuǎn)換為基本塊流圖。解釋執(zhí)行將針對(duì)基本塊流圖進(jìn)行，在解釋執(zhí)行過(guò)程中，采用基于計(jì)數(shù)的熱點(diǎn)trace探測(cè)策略。雖然該研究較好地實(shí)現(xiàn)了基于trace的即時(shí)編譯技術(shù)，但是對(duì)于trace的探測(cè)是針對(duì)程序的單次執(zhí)行，無(wú)法利用服務(wù)器端程序的運(yùn)行特點(diǎn)來(lái)高效進(jìn)行trace探測(cè)。

1.2 序列模式挖掘

設(shè)I={x1,x2,…,xn}為所有數(shù)據(jù)項(xiàng)的集合。元素e是由各種數(shù)據(jù)項(xiàng)組成的數(shù)據(jù)項(xiàng)集。序列s=就是若干元素的有序列表，元素之間是有順序的，但元素內(nèi)的數(shù)據(jù)項(xiàng)是無(wú)序的。設(shè)有兩個(gè)序列α=，β=，如果存在一組正整數(shù)1≤i1

序列模式挖掘最早由R.Agrawal和R.Srikant在1995年提出，是數(shù)據(jù)挖掘一個(gè)重要的研究領(lǐng)域。經(jīng)典的靜態(tài)序列數(shù)據(jù)庫(kù)的序列模式挖掘算法主要有兩種類型。第一種是類apriori算法，例如：R.Agrawal和R.Srikant提出的AprioriAll算法、GSP算法[6]；F.Masseglia等[7]提出的PSP算法；Zaki[8]提出的SPADE算法和J.Ayres[9]提出的SPAM算法，都需要?jiǎng)?chuàng)建候選集并多次掃描整個(gè)序列數(shù)據(jù)庫(kù)以得到序列模式。第二種是基于模式增長(zhǎng)的方法，例如FreeSpan算法[10]、PrefixSpan算法[11]等，這些算法在挖掘過(guò)程中不產(chǎn)生候選序列，通過(guò)分而治之的思想把搜索空間劃分成更小的空間，通過(guò)連接實(shí)現(xiàn)序列模式的增長(zhǎng)。

在許多實(shí)際應(yīng)用中，數(shù)據(jù)通常是動(dòng)態(tài)變化的，傳統(tǒng)的靜態(tài)序列數(shù)據(jù)庫(kù)的序列模式挖掘算法難以適用于這種情況。Huang等[12]提出了漸進(jìn)式序列模式挖掘算法Pisa，支持在挖掘過(guò)程中對(duì)序列數(shù)據(jù)庫(kù)進(jìn)行增加和刪除。Pisa算法的基本思想是構(gòu)造一棵PS-tree，來(lái)保存滑動(dòng)窗口內(nèi)的序列信息。在PS-tree中，節(jié)點(diǎn)代表了序列中的元素，其數(shù)據(jù)結(jié)構(gòu)如圖1所示。Pisa算法根據(jù)序列數(shù)據(jù)庫(kù)中新到來(lái)的數(shù)據(jù)和PS-tree中記錄的序列id和時(shí)間戳，逐步地更新PS-tree節(jié)點(diǎn)。同一序列中先后出現(xiàn)的元素，在PS-Tree中表現(xiàn)為父子節(jié)點(diǎn)關(guān)系，作為候選序列模式。PS-tree不僅存儲(chǔ)了序列中的元素和時(shí)間戳，而且有效地計(jì)算了每個(gè)候選序列模式的發(fā)生頻率。雖然Pisa算法解決了數(shù)據(jù)動(dòng)態(tài)變化的問(wèn)題，但該算法在識(shí)別序列模式的過(guò)程中忽略了同一序列中的頻繁子序列，并且在序列數(shù)據(jù)庫(kù)Db只包含一條序列時(shí)無(wú)法正常工作。

圖1 PS-Tree一般節(jié)點(diǎn)

2 基于序列模式挖掘的trace探測(cè)

設(shè)所有的基本塊對(duì)象的集合為I={x1,x2,…,xn}，數(shù)據(jù)項(xiàng)xi(1≤i≤n)為基本塊ID。元素e代表某一時(shí)刻執(zhí)行的基本塊集合。程序執(zhí)行產(chǎn)生的序列s=是一系列不斷到來(lái)的基本塊的集合。設(shè)有兩個(gè)序列α=、β=，如果存在一組正整數(shù)1≤i1

在解釋執(zhí)行每個(gè)基本塊時(shí)都會(huì)觸發(fā)如圖2所示的trace探測(cè)執(zhí)行過(guò)程，如果解釋執(zhí)行遇到的基本塊已經(jīng)編譯，直接執(zhí)行已編譯版本。如果解釋執(zhí)行遇到的基本塊未被編譯，則進(jìn)行解釋執(zhí)行并收集基本塊(數(shù)據(jù)準(zhǔn)備)。收集一定數(shù)量的基本塊后利用序列模式挖掘的方法識(shí)別trace，并進(jìn)行trace編譯。

圖2 trace探測(cè)執(zhí)行流程

基于序列模式挖掘的trace探測(cè)主要分為3個(gè)步驟，分別是數(shù)據(jù)準(zhǔn)備、序列模式挖掘算法和序列模式的去重與合并。數(shù)據(jù)準(zhǔn)備階段接收解釋器發(fā)送來(lái)的基本塊數(shù)據(jù)，并轉(zhuǎn)換為序列數(shù)據(jù)庫(kù)，序列數(shù)據(jù)庫(kù)作為序列模式挖掘算法的輸入生成序列模式，通過(guò)序列模式生成熱點(diǎn)trace返回并請(qǐng)求即時(shí)編譯系統(tǒng)編譯trace。

2.1 數(shù)據(jù)準(zhǔn)備階段

數(shù)據(jù)準(zhǔn)備工作在基于序列模式挖掘的trace探測(cè)任務(wù)中所占的工作量比較大，是保證數(shù)據(jù)挖掘成功先決條件，主要工作有基本塊數(shù)據(jù)采集和通過(guò)數(shù)據(jù)預(yù)處理生成序列數(shù)據(jù)庫(kù)。若有表1中的示例程序和如圖3所示的按照基本塊轉(zhuǎn)換規(guī)則生成的基本塊流圖，數(shù)據(jù)準(zhǔn)備工作就是針對(duì)程序執(zhí)行過(guò)程中產(chǎn)生的這些基本塊進(jìn)行的。

表1 示例程序

圖3 基本塊流圖

數(shù)據(jù)準(zhǔn)備階段負(fù)責(zé)收集服務(wù)器端程序執(zhí)行過(guò)程中產(chǎn)生的基本塊數(shù)據(jù)。每次程序執(zhí)行對(duì)應(yīng)一個(gè)基本塊數(shù)據(jù)緩沖區(qū)，緩沖區(qū)具有固定長(zhǎng)度，程序解釋執(zhí)行過(guò)程中發(fā)送基本塊數(shù)據(jù)到對(duì)應(yīng)的緩沖區(qū)中，以固定的時(shí)間間隔將緩沖區(qū)中的數(shù)據(jù)轉(zhuǎn)換為序列數(shù)據(jù)庫(kù)發(fā)送至序列模式挖掘模塊。緩沖區(qū)中只保留最近一個(gè)時(shí)間間隔的基本塊數(shù)據(jù)，當(dāng)基本塊數(shù)據(jù)個(gè)數(shù)大于緩沖區(qū)大小時(shí)舊的基本塊數(shù)據(jù)將會(huì)溢出，其中基本塊數(shù)據(jù)包括基本塊標(biāo)識(shí)、執(zhí)行基本塊的程序的標(biāo)識(shí)等信息。處理所有緩沖區(qū)中的數(shù)據(jù)，按照基本塊產(chǎn)生的順序轉(zhuǎn)換生成基本塊序列數(shù)據(jù)庫(kù)，為了實(shí)現(xiàn)方便，設(shè)置同一時(shí)刻的基本塊集合只包含一個(gè)基本塊?；緣K序列數(shù)據(jù)庫(kù)是序列模式挖掘的輸入數(shù)據(jù)。由于在程序執(zhí)行過(guò)程中基本塊的解釋執(zhí)行存在先后關(guān)系，所以整個(gè)序列數(shù)據(jù)庫(kù)也按照邏輯上的時(shí)間先后關(guān)系創(chuàng)建。

本文采用CMinus語(yǔ)言作為基于序列模式挖掘的trace探測(cè)的中間語(yǔ)言，使任何可以翻譯為CMinus的程序設(shè)計(jì)語(yǔ)言都能利用本文提供的技術(shù)提升效率。以表1中程序?yàn)槔?，?dāng)程序輸入數(shù)據(jù)為5 947，且有3個(gè)程序?qū)嵗谕瑫r(shí)執(zhí)行，也就是3條基本塊序列S1、S2和S3?？梢陨扇绫?所示的序列數(shù)據(jù)庫(kù)。

表2 序列數(shù)據(jù)庫(kù)

2.2 序列模式挖掘算法

我們提出了一種序列模式挖掘算法Pisat(Progressive Mining of Sequential Patterns for Trace)，用來(lái)識(shí)別基本塊序列數(shù)據(jù)庫(kù)中的序列模式。Pisat算法改進(jìn)了Pisa算法，使其支持單序列的序列模式挖掘，并修改了子序列頻繁程度的判定方法。

2.2.1 PST-tree

PST-tree通過(guò)存儲(chǔ)序列數(shù)據(jù)庫(kù)中各序列的信息來(lái)幫助Pisat算法識(shí)別序列模式。PST-tree是一顆多叉樹，父子節(jié)點(diǎn)表示同一序列中元素出現(xiàn)的先后關(guān)系。與PS-tree一樣，PST-tree也分為根節(jié)點(diǎn)和一般節(jié)點(diǎn)，除根節(jié)點(diǎn)外的所有其他節(jié)點(diǎn)都是普通節(jié)點(diǎn)。根節(jié)點(diǎn)只包含指向其孩子節(jié)點(diǎn)的指針。一般節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如圖4所示，存儲(chǔ)了三種信息，節(jié)點(diǎn)的標(biāo)簽(label)，序列列表(seq_list)，以及序列列表中每個(gè)序列id(sequenceID)對(duì)應(yīng)的時(shí)間戳集合(timestampSet)。時(shí)間戳集合表示同一個(gè)元素多次出現(xiàn)，Pisat算法通過(guò)時(shí)間戳集合解決了pisa算法無(wú)法有效識(shí)別同一序列中序列模式，以及單一序列無(wú)法識(shí)別序列模式的問(wèn)題。

labelsequenceID…sequenceIDtimestampSet…timestampSet

圖4 PST-tree一般節(jié)點(diǎn)結(jié)構(gòu)

2.2.2 Pisat算法

Pisat算法利用PST-Tree存儲(chǔ)所有序列的信息，Pisat算法接收最新時(shí)刻的所有序列的元素，后序遍歷PST-Tree并更新PST-Tree信息，直到?jīng)]有新的元素到來(lái)。遍歷PST-Tree的算法如表3所示，其主要思想是將新到來(lái)的元素插入到PST-Tree中。后序遍歷PST-Tree過(guò)程中，如果處理的是根節(jié)點(diǎn)，對(duì)于新到來(lái)的元素，如表2(t1)時(shí)刻序列S1，S2和S3對(duì)應(yīng)的元素E，E和B，如果該元素之前出現(xiàn)過(guò)，即新到來(lái)的元素中的基本塊id與根節(jié)點(diǎn)的某個(gè)孩子節(jié)點(diǎn)標(biāo)簽一致，那么檢查新到來(lái)元素的所屬序列是否在該孩子節(jié)點(diǎn)的序列列表中，如果存在，算法為節(jié)點(diǎn)中該序列添加一個(gè)當(dāng)前時(shí)間戳，表示多次出現(xiàn)，如果不存在，算法為節(jié)點(diǎn)中序列列表添加這個(gè)序列，并對(duì)應(yīng)當(dāng)前時(shí)間戳。如果新到來(lái)的元素之前沒有出現(xiàn)過(guò)，算法為新到來(lái)的元素創(chuàng)建一個(gè)新的孩子節(jié)點(diǎn)，包含其所屬序列和當(dāng)前時(shí)間戳。處理一般節(jié)點(diǎn)時(shí)，如果新到來(lái)元素所屬序列在節(jié)點(diǎn)的序列列表中，并且新到來(lái)元素不存在于根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑上，開始處理一般節(jié)點(diǎn)，過(guò)程類似于對(duì)根節(jié)點(diǎn)的處理。處理完一般節(jié)點(diǎn)之后，如果節(jié)點(diǎn)的序列列表長(zhǎng)度不小于支持度閾值support1×|Db|或者節(jié)點(diǎn)中某個(gè)序列對(duì)應(yīng)的所有時(shí)間戳數(shù)量不小于支持度閾值support2時(shí)，根節(jié)點(diǎn)到該節(jié)點(diǎn)的候選序列模式為序列模式，support2是新增加的支持度閾值，目的是幫助算法識(shí)別同一序列中的序列模式。

算法1traverse

輸入： 當(dāng)前時(shí)間戳ct

需要遍歷的PST-Tree PS

新到來(lái)的所有序列的元素集合ES

序列數(shù)量sn

支持度1 support1

支持度2 support2

輸出：序列模式集合SP

算法traverse

1. foreach n of PS in post order

2. if(n is root)

3. foreach e of every seq in ES

4. if(e==label of one of node.child)

5. if(seq is in n.child.seq_list)

//添加時(shí)間戳

6. addTimestamp(n.child, seq, ct)

7. else

//創(chuàng)建序列

8. createSeq(n.child, seq, ct)

9. else

//創(chuàng)建孩子節(jié)點(diǎn)

10. createNode(n, e, seq, ct)

11. else

//節(jié)點(diǎn)是一般節(jié)點(diǎn)

12. foreach seq in n.seq_list

13. if(e=hasNewEle(ES, seq) && isNotOnPathFromRoot(e, n))

//ES中seq序列有新元素e，且e不在從根節(jié)點(diǎn)開始的路//徑上

14. if(e==label of one of node.child)

15. if(seq is in n.child.seq_list)

//添加時(shí)間戳

16. addTimestamp(n.child, seq, getLatestTimestamp(n,seq))

17. else

//創(chuàng)建序列

18. createSeq(n.child, seq,getLatestTimestamp(n, seq))

19. else

//創(chuàng)建孩子節(jié)點(diǎn)

20. createNode(n, e, seq, getLatestTimestamp(n, seq))

21. if(節(jié)點(diǎn)n的序列列表中序列數(shù)量≥sn*support1‖n.seq_list中某序列對(duì)應(yīng)的所有時(shí)間戳數(shù)量≥support2)

22. 根節(jié)點(diǎn)到該節(jié)點(diǎn)的標(biāo)簽作為序列模式,收集序列模式至集合SP

輔助函數(shù)：

addTimestamp(n, seq, ts): 為節(jié)點(diǎn)n的seq序列添加一個(gè)時(shí)間戳ts

createSeq(n, seq, ts): 為節(jié)點(diǎn)n創(chuàng)建一個(gè)sequenceID為seq且對(duì)應(yīng)時(shí)間戳為ts的序列

createNode(n, e, seq, ts): 為節(jié)點(diǎn)n創(chuàng)建一個(gè)label為e的子節(jié)點(diǎn)，包含一個(gè)sequenceID為seq且時(shí)間戳為ts的序列

hasNewEle(ES, seq): ES中seq序列是否存在新元素，存在則返回新到來(lái)的元素e

isNotOnPathFromRoot(e, n): 元素e包含的基本塊是否不在n到root的路徑上

getLatestTimestamp(n, seq): 返回節(jié)點(diǎn)n中seq序列對(duì)應(yīng)的時(shí)間戳集合中，最新的時(shí)間戳

如果有如表1所示的CMinus程序及轉(zhuǎn)換成的基本塊序列數(shù)據(jù)庫(kù)表2，可以對(duì)應(yīng)如圖5所示的建樹過(guò)程，若support1設(shè)置為1.5，support2設(shè)置為2，在(t5)時(shí)刻最左側(cè)的標(biāo)簽為C的節(jié)點(diǎn)，其序列列表長(zhǎng)度

圖5 建樹過(guò)程

2.3 模式合并

挖掘得到的序列模式是程序中頻繁執(zhí)行的基本塊，但可能存在序列模式之間互相包含、有部分相同的情況，需要進(jìn)行一些去重與合并的處理，將處理后的序列模式作為trace發(fā)送至即時(shí)編譯系統(tǒng)。如果不進(jìn)行模式的去重與合并，會(huì)導(dǎo)致重復(fù)的trace被多次編譯，增加編譯開銷。對(duì)序列模式的處理包含以下幾種情況：

1) 當(dāng)前序列模式包含其他已存在的序列模式，則將已存在的序列模式合并至當(dāng)前序列模式。

2) 已存在的序列模式包含當(dāng)前序列模式，則將當(dāng)前序列模式合并至已存在的序列模式。

3) 已存在的序列模式包含當(dāng)前序列模式的一部分，且起點(diǎn)一致，則將當(dāng)前序列模式去重合并到已存在的序列模式中。

如圖 5所示PST-Tree中，若support1設(shè)置為0.5，support2設(shè)置為2，可以識(shí)別出序列模式SP1：{B，C，E}和SP2：{C，E，B}，對(duì)SP2中的元素按照基本塊id排序后為{B，C，E}，與SP1一致，將SP2合并至SP1：{B，C，E}，對(duì)序列模式進(jìn)行去重與合并之后可以有效地減少需要編譯的trace數(shù)量。

3 實(shí) 驗(yàn)

本文使用CMinus程序作為即時(shí)編譯系統(tǒng)的輸入，輸出是計(jì)算后的結(jié)果。首先對(duì)服務(wù)器端響應(yīng)用戶請(qǐng)求的CMinus語(yǔ)言程序進(jìn)行分析并生成基本塊流圖，生成基本塊流圖之后，即可對(duì)基本塊進(jìn)行解釋執(zhí)行。解釋執(zhí)行過(guò)程中，不斷將處理的基本塊發(fā)送至服務(wù)器端共用的基于序列模式挖掘的trace探測(cè)器。trace探測(cè)器識(shí)別的trace存放至trace集合，并通知JIT編譯器編譯trace。編譯完成后如解釋器再運(yùn)行到熱點(diǎn)trace，即可直接運(yùn)行編譯好的代碼。

為了驗(yàn)證本文提出的基于序列模式挖掘的trace探測(cè)方法的性能，實(shí)現(xiàn)了一個(gè)即時(shí)編譯系統(tǒng)，并設(shè)計(jì)了一組實(shí)驗(yàn)程序來(lái)比較基于計(jì)數(shù)的熱點(diǎn)trace探測(cè)策略與基于序列模式挖掘的熱點(diǎn)trace探測(cè)方法的效率。測(cè)試環(huán)境為：Windows 10操作系統(tǒng)，Intel(R) Core(TM) i5-4590 CPU@3.30 GHz，8.00 GB內(nèi)存，2 000 GB硬盤。開發(fā)環(huán)境為IntelliJ IEDA+jdk1.8。

本文在實(shí)驗(yàn)中使用的測(cè)試程序均為自定義用例，測(cè)試程序中包含了循環(huán)與分支等情況，并分別測(cè)試了程序在基于計(jì)數(shù)的熱點(diǎn)探測(cè)策略與基于序列模式挖掘的trace探測(cè)方法，比較識(shí)別第一條trace的耗時(shí)。識(shí)別第一條trace的耗時(shí)代表著trace探測(cè)策略效率的高低，trace探測(cè)策略的效率決定基于trace的即時(shí)編譯技術(shù)的優(yōu)化效果。

第一組測(cè)試程序如表3所示，圖6為測(cè)試結(jié)果，在程序只有單重循環(huán)的情況下，程序1-程序5無(wú)分支語(yǔ)句或只有一層分支語(yǔ)句，基于計(jì)數(shù)的策略耗時(shí)遠(yuǎn)小于基于序列模式挖掘的策略。程序6具有兩層分支語(yǔ)句，基于計(jì)數(shù)的策略耗時(shí)略高于基于序列模式挖掘的策略。程序7具有四層分支語(yǔ)句，基于計(jì)數(shù)的策略耗時(shí)遠(yuǎn)高于基于序列模式挖掘的策略。在程序具有雙重循環(huán)的情況下，程序8、程序9無(wú)分支語(yǔ)句，基于計(jì)數(shù)的策略耗時(shí)大于單重循環(huán)的情況，但仍小于基于序列模式的策略。程序10-程序13具有一層或兩層分支語(yǔ)句，基于計(jì)數(shù)的策略耗時(shí)接近或高于基于序列模式挖掘策略。在程序具有三重循環(huán)的情況下，程序14無(wú)分支語(yǔ)句，基于計(jì)數(shù)的策略耗時(shí)小于基于序列模式挖掘策略。程序15具有一層分支語(yǔ)句，基于計(jì)數(shù)的策略耗時(shí)略高于基于序列模式挖掘策略。

表3 第一組測(cè)試程序

圖6 識(shí)別第一條trace消耗的時(shí)間

為了更好地分析識(shí)別第一條trace的耗時(shí)與程序結(jié)構(gòu)的關(guān)系，本文設(shè)計(jì)了如表4所示的第二組實(shí)驗(yàn)。測(cè)試結(jié)果如圖7所示，程序在循環(huán)嵌套層數(shù)一定的情況下，基于計(jì)數(shù)的策略耗時(shí)隨著分支語(yǔ)句嵌套層數(shù)的增加而增加，而基于序列模式挖掘的策略耗時(shí)相對(duì)穩(wěn)定，一般情況下，基于序列模式挖掘的策略比基于計(jì)數(shù)的策略在效率上有所提升。

表4 第二組測(cè)試程序

圖7 識(shí)別第一條trace消耗的時(shí)間

實(shí)驗(yàn)結(jié)果表明：分支語(yǔ)句嵌套層數(shù)固定時(shí)，循環(huán)嵌套層數(shù)越多，基于計(jì)數(shù)的策略耗時(shí)越多。在循環(huán)層數(shù)固定時(shí)，程序內(nèi)分支語(yǔ)句的嵌套層數(shù)越多，基于計(jì)數(shù)的策略耗時(shí)越多，而基于序列模式挖掘的策略耗時(shí)相對(duì)穩(wěn)定，可以帶來(lái)效率上的提升。

4 結(jié) 語(yǔ)

為了更高效地識(shí)別服務(wù)器端程序的熱點(diǎn)trace，本文提出了一種基于序列模式挖掘的trace探測(cè)方法，解決了現(xiàn)有的trace探測(cè)方法無(wú)法針對(duì)服務(wù)器端程序進(jìn)行高效探測(cè)的問(wèn)題。本方法收集程序解釋執(zhí)行過(guò)程中的基本塊，并轉(zhuǎn)換為基本塊序列數(shù)據(jù)庫(kù)，以固定的時(shí)間間隔發(fā)送至序列模式挖掘模塊。針對(duì)基本塊序列的特點(diǎn)，本文提出并使用Pisat算法作為序列模式挖掘模塊的核心算法。為了減少編譯開銷，本方法對(duì)識(shí)別出的序列模式進(jìn)行去重與合并作為熱點(diǎn)trace，最后對(duì)熱點(diǎn)trace進(jìn)行編譯。

通過(guò)實(shí)驗(yàn)證明，程序復(fù)雜程度足夠高時(shí)，該方法與基于計(jì)數(shù)的熱點(diǎn)trace探測(cè)方法相比，切實(shí)有效地提高了trace識(shí)別的效率。在今后的工作中，我們將對(duì)針對(duì)trace探測(cè)的序列模式算法Pisat進(jìn)行并行優(yōu)化，以期進(jìn)一步提高trace探測(cè)效率。