本系列目錄 《來做個網路瀏覽器吧!》文章列表
今天研究論文: Fast and Parallel Webpage Layout
論文作者為 Leo A. Meyerovich 和 Rastislav Bodík,於 2010 年發表。
本篇文章圖片來自原始論文
這篇論文滿早的,我想大概也算是瀏覽器開發以平行化技術為主體的先鋒了。裡面很多概念我都有在最新的 Firefox 看到影子。像是計算資源調配、計算 tree 的平行化,雖然說一些實作方式都不難想到,但我想早期的研究對後來的發展仍有影響。
不過這一篇在演算法的部分有特別著墨,有很多虛擬碼,此外關於字體顯示算是獨創,講了很多實作的細節。以下就來介紹這篇論文,多半是論文中的觀點,經過我的理解後重新詮釋。
今天要談的論文的核心概念:
這張圖顯示了這個研究平行化的流程,其中分為四大點:
這邊幫大家複習一下本系文章,選擇器匹配可以看這篇,關於佈局可以看這篇&這篇,畫面輸出看這篇。這些都是「簡易版」的實作,看懂了再來看論文,會有更深的體會。
首先是選擇器匹配的部分,作者針對「一般的」CSS 進行優化,「一般」定義在下圖(6)的(a),例如 <div id="account" class="first,on"/>
會對應 div.first
,當運算子為 s1 < s2
,代表 s2 在 s1 之下,這類型的 CSS 約莫佔網站的 99%,也就是幾乎包含所有了,然後會被轉換成(b)的形式
接著作者在處理匹配的演算法用到幾個技巧:
div #id1
,會先找 div
再去找 #id1
。但作者認為通常從右邊找起可以直接找到對象,反而比較快。(可能可以做機器學習,讓我們決定哪些狀況從左邊,哪些狀況從右邊)div { color }
和 div { padding }
這兩個都是針對 div
,如果合併的話可以減少查詢匹配的次數。經過以上幾點處理。作者得到結論:
這邊作者有討論到平行化的方法不同的優缺點,但差別只是他用不同的套件,不是重點就不討論了。
作者的實驗數據,用 Safari on the 2.4GHz Intel Core 2 Duo MacBook Pro 原本要 204 ms 現在只要花 3.5 ms。他估計,手機原本要 3.5s 的話,現在只要 50ms。不過這只是他猜測而已,事實上我不認為手機會有這麼好的效果,手機處理器計算能力仍然不強,此外有沒有完全支援平行處理也有待確認。
希望有幫到大家,大家明天見!
關於作者
劉安齊
軟體工程師,熱愛寫程式,更喜歡推廣程式讓更多人學會