潘 龍 廖湖聲 蘇 航

1(北京工業(yè)大學計算機學院 北京 100124) 2(北京工業(yè)大學軟件學院 北京 100124)

0 引 言

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

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

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

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

1 相關(guān)工作

1.1 基于trace的即時編譯

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

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

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

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

1.2 序列模式挖掘

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

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

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

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

2 基于序列模式挖掘的trace探測

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

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

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

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

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

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

表1 示例程序

圖3 基本塊流圖

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

本文采用CMinus語言作為基于序列模式挖掘的trace探測的中間語言，使任何可以翻譯為CMinus的程序設計語言都能利用本文提供的技術(shù)提升效率。以表1中程序為例，當程序輸入數(shù)據(jù)為5 947，且有3個程序?qū)嵗谕瑫r執(zhí)行，也就是3條基本塊序列S1、S2和S3。可以生成如表2所示的序列數(shù)據(jù)庫。

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

2.2 序列模式挖掘算法

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

2.2.1 PST-tree

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

labelsequenceID…sequenceIDtimestampSet…timestampSet

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

2.2.2 Pisat算法

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

算法1traverse

輸入： 當前時間戳ct

需要遍歷的PST-Tree PS

新到來的所有序列的元素集合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)

//添加時間戳

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

7. else

//創(chuàng)建序列

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

9. else

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

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

11. else

//節(jié)點是一般節(jié)點

12. foreach seq in n.seq_list

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

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

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

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

//添加時間戳

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é)點

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

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

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

輔助函數(shù)：

addTimestamp(n, seq, ts): 為節(jié)點n的seq序列添加一個時間戳ts

createSeq(n, seq, ts): 為節(jié)點n創(chuàng)建一個sequenceID為seq且對應時間戳為ts的序列

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

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

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

getLatestTimestamp(n, seq): 返回節(jié)點n中seq序列對應的時間戳集合中，最新的時間戳

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

圖5 建樹過程

2.3 模式合并

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

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

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

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

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

3 實 驗

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

為了驗證本文提出的基于序列模式挖掘的trace探測方法的性能，實現(xiàn)了一個即時編譯系統(tǒng)，并設計了一組實驗程序來比較基于計數(shù)的熱點trace探測策略與基于序列模式挖掘的熱點trace探測方法的效率。測試環(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。

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

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

表3 第一組測試程序

圖6 識別第一條trace消耗的時間

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

表4 第二組測試程序

圖7 識別第一條trace消耗的時間

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

4 結(jié) 語

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

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