本系列目錄 《來做個網路瀏覽器吧!》文章列表

今天研究論文: Fast and Parallel Webpage Layout

論文作者為 Leo A. Meyerovich 和 Rastislav Bodík,於 2010 年發表。
本篇文章圖片來自原始論文

這篇論文滿早的,我想大概也算是瀏覽器開發以平行化技術為主體的先鋒了。裡面很多概念我都有在最新的 Firefox 看到影子。像是計算資源調配、計算 tree 的平行化,雖然說一些實作方式都不難想到,但我想早期的研究對後來的發展仍有影響。

不過這一篇在演算法的部分有特別著墨,有很多虛擬碼,此外關於字體顯示算是獨創,講了很多實作的細節。以下就來介紹這篇論文,多半是論文中的觀點,經過我的理解後重新詮釋。


今天要談的論文的核心概念:

這張圖顯示了這個研究平行化的流程,其中分為四大點:

  • 選擇器匹配(selector matching:1
  • box 和 text 佈局: 2, 4~6
  • 字形處理: 3
  • 上色和渲染: 7

這邊幫大家複習一下本系文章,選擇器匹配可以看這篇,關於佈局可以看這篇這篇,畫面輸出看這篇。這些都是「簡易版」的實作,看懂了再來看論文,會有更深的體會。


首先是選擇器匹配的部分,作者針對「一般的」CSS 進行優化,「一般」定義在下圖(6)的(a),例如 <div id="account" class="first,on"/>會對應 div.first,當運算子為 s1 < s2,代表 s2 在 s1 之下,這類型的 CSS 約莫佔網站的 99%,也就是幾乎包含所有了,然後會被轉換成(b)的形式

接著作者在處理匹配的演算法用到幾個技巧:

  • 雜湊:他在 CSS 的選擇器使用雜湊表分類,例如有關 img 的 CSS分為一類,碰到有 img 的 node,只要去找 img 類別的 stylesheet。
  • 從右邊找:一般是從左邊找起,例如 div #id1,會先找 div 再去找 #id1。但作者認為通常從右邊找起可以直接找到對象,反而比較快。(可能可以做機器學習,讓我們決定哪些狀況從左邊,哪些狀況從右邊)
  • 預處理:CSS 不會做語法檢查。所以可以先排除一些冗程式碼。例如,多個選擇器其實可以合併,像是 div { color }div { padding } 這兩個都是針對 div,如果合併的話可以減少查詢匹配的次數。
  • 雜湊平鋪(hash tiling):似乎是把雜湊表重新劃分。因為快取大小有限,避免無意義的查詢,將要處理的東西先分配好,確定在當下的快取大小下可以完成工作,以此為前提進行重新劃分。
  • 序號化:把 DOM 的屬性和 CSS 同樣名稱的換成一樣的數字,匹配速度會加快,而且之後如果要進行比大小的判斷,會更容易。
  • 平行處理樹:樹有很多樹枝,所以可以同時跑好幾個樹枝。這跟我們之前文章提到概念一樣。
  • 調整資源:哪個執行緒被分配的選擇器看起來比較多工作,就分少一點其他選擇器給他。這個概念我們之前也提到過。
  • 預先留記憶空間:一般都是需要才叫空間,現在先保留。(減少I/O時間,但很吃資源)
  • 延遲插入 rules:等數量到一定程度才一次插入。
  • 不使用 STL:STL 似乎不是平行的樣子,所以作者自己寫了一個來做資料處理

經過以上幾點處理。作者得到結論:

  • 雜湊平鋪可以快 3倍
  • 平行處理樹+預處理可以快 4~13 倍之間
  • 把上面所有的方法加進來最快可以到 25 倍

這邊作者有討論到平行化的方法不同的優缺點,但差別只是他用不同的套件,不是重點就不討論了。
作者的實驗數據,用 Safari on the 2.4GHz Intel Core 2 Duo MacBook Pro 原本要 204 ms 現在只要花 3.5 ms。他估計,手機原本要 3.5s 的話,現在只要 50ms。不過這只是他猜測而已,事實上我不認為手機會有這麼好的效果,手機處理器計算能力仍然不強,此外有沒有完全支援平行處理也有待確認。


希望有幫到大家,大家明天見!