劉秀秀　潘　梁　郭志川　胡琳琳

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)

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

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

0　引　言

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

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

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

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

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

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

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

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

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

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

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

2　并行化CSS引擎處理方法

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

2.1CSS資源預(yù)取

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

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

圖3　CSS解析中資源加載

圖4　CSS資源預(yù)取

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

2.2CSS解析

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

圖5　串行CSS解析

圖6　并行CSS解析

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

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

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

2.3CSS選擇器匹配

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

圖7　CSS匹配示例

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

按照瀏覽器對(duì)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é)點(diǎn)進(jìn)行匹配，如圖8所示。圖9為匹配算法執(zhí)行的偽代碼。其中idMatch(DOM),classMatch(DOM),tagMatch(DOM)和otherMatch(DOM)分別在不同的線程中，執(zhí)行遍歷DOM的操作，一直遇到匹配的DOM節(jié)點(diǎn)為止。

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

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

2.3.2并行DOM遍歷

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

圖10　并行DOM節(jié)點(diǎn)

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

3　算法分析與驗(yàn)證

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

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

表1　加載時(shí)間對(duì)比

4　結(jié)　語

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

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

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

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

[3] 劉劍,桑楠,郭文生.嵌入式瀏覽器CSS引擎的研究與改進(jìn)[J].計(jì)算機(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] 葛春良.嵌入式瀏覽器多線程機(jī)制的研究與實(shí)現(xiàn)[D].電子科技大學(xué),2012:38-39.

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

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

[11] 楊際祥,譚國真,王榮生,等.并行分治計(jì)算中的一種Work-stealing策略[J].小型微型計(jì)算機(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