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

劉秀秀　潘　梁　郭志川　胡琳琳

1(中國科學院大學　北京 100190)2(中國科學院聲學研究所國家網絡新媒體工程技術研究中心　北京 100190)

?

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

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

1(中國科學院大學北京 100190)2(中國科學院聲學研究所國家網絡新媒體工程技術研究中心北京 100190)

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

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

0　引　言

層疊樣式表CSS是由W3C定義和維護的標準，一種用來為結構化文檔如HTML文檔或XML應用添加樣式(字體、間距和顏色等)的計算機語言[1]。

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

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

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

1　CSS引擎結構

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

圖1　CSS引擎結構

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

圖2　內部樣式結構

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

樣式匹配是將每個樣式規則映射到DOM樹上各個節點的過程。樣式匹配在網頁解析過程中調用次數非常多，匹配過程也較為復雜，需要消耗大量的時間，是CSS引擎的性能瓶頸。采用合適的樣式匹配算法可以大大減少匹配的時間，優化網頁的加載。

2　并行化CSS引擎處理方法

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

2.1CSS資源預取

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

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

圖3　CSS解析中資源加載

圖4　CSS資源預取

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

2.2CSS解析

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

圖5　串行CSS解析

圖6　并行CSS解析

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

語法解析器主要進行語法檢查、并構建由詞法分析器所返回的單詞組成的數據結構，一般是語法解析樹、抽象語法樹等層次化的數據結構。例如上例中，如果網頁書寫人員將“red”寫成了“rd”，語法解析器會報語法錯誤，此條規則會失效。

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

2.3CSS選擇器匹配

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

圖7　CSS匹配示例

2.3.1根據CSS選擇符的類型并行化處理

按照瀏覽器對CSS選擇符書寫規則帶來的頁面開銷(從小到大)的順序，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]。本文的并行化方法是根據CSS解析后得到的CSS選擇器的類型，將不同的選擇器分在不同的線程中，與DOM節點進行匹配，如圖8所示。圖9為匹配算法執行的偽代碼。其中idMatch(DOM),classMatch(DOM),tagMatch(DOM)和otherMatch(DOM)分別在不同的線程中，執行遍歷DOM的操作，一直遇到匹配的DOM節點為止。

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

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

2.3.2并行DOM遍歷

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

圖10　并行DOM節點

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

3　算法分析與驗證

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

考慮到不同的網頁外部CSS樣式表和圖片的數量不同，本文基于不同的網頁做了實驗模型化，基于不同種類的網頁進行仿真測試，測試結果如表1所示。結果表明，采用并行化算法可以明顯提高加載速度，但是增加了空間的占用。而對于百度首頁這種頁面內容單一的網頁，提升的效果并不明顯。

表1　加載時間對比

4　結　語

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

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

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

[2] 羅智明.基于智能手機平臺的CSS引擎優化與實現[D].電子科技大學,2012:8-14.

[3] 劉劍,桑楠,郭文生.嵌入式瀏覽器CSS引擎的研究與改進[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].軟件導刊,2012,10(12):37-38.

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

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

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

[11] 楊際祥,譚國真,王榮生,等.并行分治計算中的一種Work-stealing策略[J].小型微型計算機系統,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。劉秀秀，碩士，主研領域：嵌入式系統。潘梁，副研究員。郭志川，副研究員。胡琳琳，助理研究員。

TP393.092

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