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

今天研究論文： 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。不過這只是他猜測而已，事實上我不認為手機會有這麼好的效果，手機處理器計算能力仍然不強，此外有沒有完全支援平行處理也有待確認。

希望有幫到大家，大家明天見！