基于嵌入式瀏覽器CSS引擎并行化技術(shù)的研究

劉秀秀　潘　梁　郭志川　胡琳琳

1(中國科學(xué)院大學(xué)　北京 100190)2(中國科學(xué)院聲學(xué)研究所國家網(wǎng)絡(luò)新媒體工程技術(shù)研究中心　北京 100190)

?

基于嵌入式瀏覽器CSS引擎并行化技術(shù)的研究

劉秀秀1,2潘梁2郭志川2胡琳琳2

1(中國科學(xué)院大學(xué)北京 100190)2(中國科學(xué)院聲學(xué)研究所國家網(wǎng)絡(luò)新媒體工程技術(shù)研究中心北京 100190)

針對嵌入式瀏覽器CSS(CascadingStyleSheets)解析效率低下的問題，提出一種CSS引擎并行化處理方法。通過對CSS引擎資源預(yù)取、樣式解析和選擇器匹配功能的描述，分別介紹如何將資源預(yù)取、樣式解析與網(wǎng)頁解析并行執(zhí)行，以及CSS選擇器并行匹配。該并行處理方法可以克服嵌入式瀏覽器邊解析邊加載帶來的網(wǎng)絡(luò)延時以及串行處理帶來的用戶等待時間長的問題。通過對多種網(wǎng)頁加載時間的仿真測試，頁面的加載速度提高了很多，實驗結(jié)果驗證了該方法的可行性。

層疊樣式表引擎并行化資源預(yù)取樣式解析選擇器匹配

0　引　言

層疊樣式表CSS是由W3C定義和維護(hù)的標(biāo)準(zhǔn)，一種用來為結(jié)構(gòu)化文檔如HTML文檔或XML應(yīng)用添加樣式(字體、間距和顏色等)的計算機語言[1]。

相對于傳統(tǒng)HTML的表現(xiàn)而言，CSS能夠?qū)W(wǎng)頁中對象的位置排版進(jìn)行像素級的精確控制[2]。CSS規(guī)范的廣泛使用和嵌入式瀏覽器的廣泛使用，使CSS引擎成為嵌入式瀏覽器中必不可少的部分。CSS引擎完成的功能是將網(wǎng)頁中的CSS樣式描述準(zhǔn)確無誤地解析出來，并對每個DOM節(jié)點(文檔對象模型，DOM樹是由結(jié)構(gòu)文檔生成的樹結(jié)構(gòu)，DOM節(jié)點是DOM樹中的節(jié)點)進(jìn)行樣式匹配、樣式運用，最終使樣式效果得以實現(xiàn)[3]。

隨著互聯(lián)網(wǎng)的發(fā)展，嵌入式瀏覽器的響應(yīng)速度成為影響用戶體驗的一個重要因素。越來越多的廠商開始利用多核處理器，然而，當(dāng)前的嵌入式瀏覽器并沒有充分利用硬件并行化的優(yōu)勢，因此導(dǎo)致計算資源閑置問題。

為了利用多核優(yōu)勢，一些桌面瀏覽器如Chrome開始采用多進(jìn)程的方式，一個標(biāo)簽頁一個進(jìn)程，在標(biāo)簽頁很多的情況下加快了網(wǎng)頁的處理速度。然而在嵌入式設(shè)備上，更多的用戶需求體現(xiàn)在一個標(biāo)簽頁的情況下網(wǎng)頁加載速度問題，這就要求提高瀏覽器的處理速度。據(jù)統(tǒng)計CSS引擎的處理時間占瀏覽器總處理時間的近40%[4]，所以對CSS引擎的處理采用并行化，可以大大加快網(wǎng)頁的加載速度，同時可以充分利用硬件資源。本文針對目前嵌入式系統(tǒng)處理速度有限、內(nèi)存受限以及多核處理器廣泛發(fā)展的特點，提出了一種CSS引擎并行處理的方法。

1　CSS引擎結(jié)構(gòu)

從整體上看，CSS引擎的輸入是文檔對象模型(DOM樹)和一個CSS樣式集，經(jīng)過CSS引擎的處理，輸出標(biāo)注了CSS樣式的一棵渲染樹[5]如圖1(a)所示。本文將CSS引擎分為CSS樣式解析器、內(nèi)部樣式結(jié)構(gòu)、樣式分類和樣式匹配4個模塊，內(nèi)部結(jié)構(gòu)如圖1(b)所示。

圖1　CSS引擎結(jié)構(gòu)

在頁面解析過程中，HTML解析器遇到CSS樣式描述，會調(diào)用CSS樣式解析器對CSS樣式描述進(jìn)行解析，具體為經(jīng)過詞法分析、語法分析和語義處理得到內(nèi)部樣式結(jié)構(gòu)，供程序內(nèi)部使用。內(nèi)部樣式結(jié)構(gòu)依據(jù)CSS規(guī)范而設(shè)計，具有嚴(yán)格的層次關(guān)系，從最高層到最底層有樣式表(CSSStyleSheet)、樣式規(guī)則(CSSStyleRule)、樣式選擇符(CSSSelector)、樣式聲明(CSSMutalStyleDeclaration)、樣式屬性(CSSProperty)和樣式屬性值(CSSValue)等，如圖2所示，表示了將一個CSS描述進(jìn)行詞法解析的過程。其中，樣式規(guī)則由樣式選擇符和樣式聲明成對組成。

圖2　內(nèi)部樣式結(jié)構(gòu)

樣式分類部分是對已解析得到的內(nèi)部樣式規(guī)則按照樣式選擇符類型進(jìn)行分類，對于待匹配的節(jié)點，適用的樣式選擇符單元類型集是全部樣式選擇符單元類型的一個子集，在每次樣式匹配前確定最小適用樣式規(guī)則分類集，可以減少一些不相關(guān)樣式規(guī)則的匹配。

樣式匹配是將每個樣式規(guī)則映射到DOM樹上各個節(jié)點的過程。樣式匹配在網(wǎng)頁解析過程中調(diào)用次數(shù)非常多，匹配過程也較為復(fù)雜，需要消耗大量的時間，是CSS引擎的性能瓶頸。采用合適的樣式匹配算法可以大大減少匹配的時間，優(yōu)化網(wǎng)頁的加載。

2　并行化CSS引擎處理方法

CSS引擎所做的主要工作包括CSS資源預(yù)取、CSS解析、CSS選擇器匹配[6]。通過CSS引擎處理后，各個樣式才能映射到DOM節(jié)點，確定每個節(jié)點的位置顏色大小等信息。下面通過CSS引擎的工作分別描述并行化算法具體的實施方式。

2.1CSS資源預(yù)取

如果在一個CSS樣式表中引用了過多的外部CSS資源(如圖片或CSS樣式表)，用戶在請求資源下載時需要經(jīng)歷長時間的網(wǎng)絡(luò)延時，為了減少下載資源所花費的時間，盡可能地從網(wǎng)絡(luò)中預(yù)取所依賴的資源是非常必要的。

本文的方法是在HTML文檔解析開始先進(jìn)行文檔的預(yù)掃描，如果發(fā)現(xiàn)有外部資源，就利用并行算法將其預(yù)取下來，即資源預(yù)取和頁面解析是并行執(zhí)行的，此時并不影響頁面解析。如圖3是未采用并行算法時頁面解析過程中發(fā)現(xiàn)DOM節(jié)點中用到外部資源，頁面解析阻塞，開始加載資源；圖4是采用并行算法后，頁面解析不受影響。

圖3　CSS解析中資源加載

圖4　CSS資源預(yù)取

下載足夠的外部資源是非常重要的。如果加載資源過多會減慢頁面加載的速度，增大網(wǎng)絡(luò)的負(fù)擔(dān)；如果加載資源不足，在CSS樣式解析中需要重新加載外部資源，增大了網(wǎng)頁解析的延遲。本文通過HTML預(yù)掃描器確定外部資源中選擇符的ID或類屬性是否都被預(yù)掃描器發(fā)現(xiàn)了，如果外部資源CSS選擇符中所有的屬性值都被HTML預(yù)掃描部分發(fā)現(xiàn)了，就開始加載此資源。這樣經(jīng)過判定后加載的資源在頁面解析過程中會被使用，增大了加載資源的可用性。

2.2CSS解析

在本文的并行方法中，如果HTML解析過程中遇到樣式描述符就將其分發(fā)給CSS解析器，每個樣式解析分屬不同的線程，這就意味著一旦有新的CSS樣式，CSS解析會立即執(zhí)行。然而為保證所有CSS樣式規(guī)則的順序與串行CSS引擎產(chǎn)生的規(guī)則順序一致，本文中的方法是為每個解析任務(wù)分配一個獨一無二的串行ID號，用來重排最初文檔中的CSS樣式表。圖5所示是串行CSS資源解析的流程，遇新的CSS樣式時頁面解析會被中斷，圖6中所示當(dāng)采用并行算法后，HTML頁面解析不受影響。

圖5　串行CSS解析

圖6　并行CSS解析

CSS樣式解析主要是將輸入的CSS代碼經(jīng)過詞法分析、語法解析生成計算機可以識別的語言。詞法分析器，有時也被稱作tokenizer，主要是將從樣式表中輸入的字符序列轉(zhuǎn)換為單詞序列，并對單詞序列分類。詞法分析器一般以函數(shù)的形式存在，供語法解析器調(diào)用。詞法分析器通常不會關(guān)心每個單詞之間的關(guān)系。例如有一個規(guī)則集div{color：red}，當(dāng)進(jìn)行完詞法分析后，一共得到6個有效的token：“div”，“{”，“color”，“：”，“red”，“}”?？梢娫~法分析不依賴外部單詞的信息，只依靠詞法，比較簡單。

語法解析器主要進(jìn)行語法檢查、并構(gòu)建由詞法分析器所返回的單詞組成的數(shù)據(jù)結(jié)構(gòu)，一般是語法解析樹、抽象語法樹等層次化的數(shù)據(jù)結(jié)構(gòu)。例如上例中，如果網(wǎng)頁書寫人員將“red”寫成了“rd”，語法解析器會報語法錯誤，此條規(guī)則會失效。

經(jīng)過詞法分析、語法解析后，CSS解析器輸出一些CSS選擇符和樣式聲明，為選擇器匹配奠定基礎(chǔ)。

2.3CSS選擇器匹配

CSS匹配算法的功能就是將各個樣式映射到DOM節(jié)點上。對于每個節(jié)點，CSS引擎必須找到所有匹配此節(jié)點的選擇器或者規(guī)則。一個具體的CSS選擇器匹配的例子如圖5所示：ulem{color:blue}，如圖7所示是將em節(jié)點的顏色設(shè)置為藍(lán)色，為了找到em的先輩節(jié)點，必須從底向上遍歷DOM樹，直到找到ul節(jié)點，此次匹配完成。

圖7　CSS匹配示例

2.3.1根據(jù)CSS選擇符的類型并行化處理

按照瀏覽器對CSS選擇符書寫規(guī)則帶來的頁面開銷(從小到大)的順序，CSS選擇符的類型分為ID選擇符(如#top{margin-top:50px})、類選擇符(如id.x{font-size:12px})、類型選擇符(如a{text-decoration:none;})、相鄰兄弟選擇符(如h1+h2{margin-top:50px} )、子選擇符(如top>li{margin-top:50px} )和后代選擇符(如topa{后代選擇符，示例topa{}} )等[7]。本文的并行化方法是根據(jù)CSS解析后得到的CSS選擇器的類型，將不同的選擇器分在不同的線程中，與DOM節(jié)點進(jìn)行匹配，如圖8所示。圖9為匹配算法執(zhí)行的偽代碼。其中idMatch(DOM),classMatch(DOM),tagMatch(DOM)和otherMatch(DOM)分別在不同的線程中，執(zhí)行遍歷DOM的操作，一直遇到匹配的DOM節(jié)點為止。

圖8　根據(jù)選擇符類型劃分　　　　圖9　匹配偽代碼

該算法首先根據(jù)不同的選擇符類型建立哈希表，建立哈希表的具體方式利用了webkit中的策略[8-10]，表中存放ID、類、標(biāo)簽名稱或其他。如當(dāng)輸入選擇器的類型為ID時，我們用idMatch線程處理，利用從右到左的匹配方式，逐級找到DOM節(jié)點。其他類型類似。例如對于“pimg”，我們首先找到“img”節(jié)點，然后遍歷其DOM樹，當(dāng)在其祖先節(jié)點中找到“p”時才將此選擇器的屬性值應(yīng)用到此節(jié)點，否則選擇器不匹配。

2.3.2并行DOM遍歷

對于2.3.1節(jié)，我們是根據(jù)選擇器類型的不同進(jìn)行了并行化處理，如果對于選擇器的類型特別單一的網(wǎng)頁，可以對DOM樹結(jié)構(gòu)進(jìn)行并行化處理。首先將DOM樹映射到一個節(jié)點數(shù)組中，本文利用work-stealing算法[11]將不同的數(shù)組塊分給不同的核心處理。圖10示出了并行化的具體實施方式。

圖10　并行DOM節(jié)點

對于不同的選擇器不同的DOM節(jié)點，每個選擇器匹配一個節(jié)點所花費的時間是不同的。DOM樹中相鄰的節(jié)點可能有相似的屬性，所以匹配路線和處理時間也相似。相鄰節(jié)點之間的這種相似性意味著在不同的子樹上可能需要不同的處理時間，這就導(dǎo)致了靜態(tài)分配不平衡性，從而增大了動態(tài)調(diào)整時間。為解決此問題，本文通過將不同的節(jié)點隨機分配到不同的數(shù)組中，在一個并行循環(huán)中執(zhí)行work-stealing算法，減少竊取的次數(shù),加快了處理速度。

3　算法分析與驗證

采用以上并行化CSS引擎處理算法在多核處理器環(huán)境下，可以充分利用硬件資源，效果更優(yōu)。對于引用外部樣式資源比較多的情況下，可以減少網(wǎng)絡(luò)延時帶來的影響。由于利用了多線程處理，增加了線程之間的通信；對資源的預(yù)加載以及CSS解析中增加了對空間的占用。這種犧牲空間換取時間的方式對于硬件處理來說是可行的。

考慮到不同的網(wǎng)頁外部CSS樣式表和圖片的數(shù)量不同，本文基于不同的網(wǎng)頁做了實驗?zāi)Ｐ突?，基于不同種類的網(wǎng)頁進(jìn)行仿真測試，測試結(jié)果如表1所示。結(jié)果表明，采用并行化算法可以明顯提高加載速度，但是增加了空間的占用。而對于百度首頁這種頁面內(nèi)容單一的網(wǎng)頁，提升的效果并不明顯。

表1　加載時間對比

4　結(jié)　語

本文對嵌入式瀏覽器CSS引擎的功能和結(jié)構(gòu)進(jìn)行了簡要說明，主要介紹了并行化CSS選擇器的三個方面：CSS資源預(yù)取、CSS解析和選擇器匹配。另外選擇器匹配中通過CSS選擇

符并行化和DOM數(shù)據(jù)結(jié)構(gòu)的并行化，詳細(xì)介紹了并行化的實現(xiàn)方式。通過采用此方法，在多核處理器上可以大大加快網(wǎng)頁的加載速度。由于CSS引擎相對獨立，這種并行方法具有較強的可移植性。本文的研究對于將來多核處理器中CSS引擎并行化處理具有較好的參考價值。

[1]Mozilla.CSS[EB/OL].https://developer.mozilla.org/en-US/docs/CSS,Aug,2012.

[2] 羅智明.基于智能手機平臺的CSS引擎優(yōu)化與實現(xiàn)[D].電子科技大學(xué),2012:8-14.

[3] 劉劍,桑楠,郭文生.嵌入式瀏覽器CSS引擎的研究與改進(jìn)[J].計算機工程,2011,37(9):44-46.

[4]BadeaC,HaghighatMR,NicolauA,etal.Towardsparallelizingthelayoutengineoffirefox[C]//Proceedingsofthe2ndUSENIXconferenceonHottopicsinparallelism.USENIXAssociation,2010:1.

[5]MeyerovichLA,BodikR.Fastandparallelwebpagelayout[C]//Proceedingsofthe19thinternationalconferenceonWorldwideweb.ACM,2010:711-720.

[6]CascavalC,FowlerS,Montesinos-OrtegoP,etal.Zoomm:aparallelwebbrowserengineformulticoremobiledevices[C]//Proceedingsofthe18thACMSIGPLANsymposiumonPrinciplesandpracticeofparallelprogramming.ACM,2013:271-280.

[7] 田嶺.深入理解CSS選擇符的匹配方式[J].軟件導(dǎo)刊,2012,10(12):37-38.

[8] 葛春良.嵌入式瀏覽器多線程機制的研究與實現(xiàn)[D].電子科技大學(xué),2012:38-39.

[9]TheWebKitopensourceproject[EB/OL].[2011 -02 -10].http://www.Webkit.org.

[10] 趙經(jīng)緯,周余,王自強,等.基于WebKit的嵌入式瀏覽器的研究與實現(xiàn)[J].電子測量技術(shù),2009,34(3):135-138.

[11] 楊際祥,譚國真,王榮生,等.并行分治計算中的一種Work-stealing策略[J].小型微型計算機系統(tǒng),2010,31(3):408-412.

RESEARCHONCSSENGINEPARALLELISATIONTECHNIQUEBASEDONEMBEDDEDBROWSER

LiuXiuxiu1,2PanLiang2GuoZhichuan2HuLinlin2

1(University of Chinese Academy of Sciences,Beijing 100190,China)2(National Network New Media Engineering Research Center,Institute of Acoustics,Chinese Academy of Sciences,Beijing 100190,China)

TosolvethelowefficiencyproblemofCSSparsinginembeddedbrowsers,thispaperproposesaCSSengineparallelisedprocessingmethod.ThroughtheresourcesprefetchingonCSSengine,thestyleparsinganddescriptionoftheselectormatchingfunction,werespectivelyintroducehowtoparallelisetheexecutionofresourcesprefetching,styleparsingandwebpageparsing,aswellastheparallelmatchingofCSSselectors.Thisparallelprocessingmethodcanovercomethenetworkdelayincurredbytheembeddedbrowsersloadingtheresourceswhileparsing,andthelongtimewaitingproblembroughtforthbyserialiseprocessing.Byavarietyofwebpagesloadtimesimulationtests,theloadingspeedofwebpagesraisedalot.Experimentalresultverifiesthefeasibilityoftheproposedmethod.

Cascadingstylesheets(CSS)engineParallelisationResourcesprefetchingStyleparsingSelectormatching

2014-05-07。劉秀秀，碩士，主研領(lǐng)域：嵌入式系統(tǒng)。潘梁，副研究員。郭志川，副研究員。胡琳琳，助理研究員。

TP393.092

ADOI:10.3969/j.issn.1000-386x.2016.03.053