今天討論一下瀏覽器的平行化。像是 Servo 瀏覽器引擎其終旨就是希望做一個平行化的瀏覽器,而 Servo 最早開始是從 2012 起開發。

大家可以看一下 2009 年的論文:Parallelizing the Web Browser,時間在 Servo 之前,有種倒敘的味道。而這篇論文被引用 89 次,近幾年相關研究幾乎都會在參考中看到。或多或少也影響後來的瀏覽器開發。 Firefox 和 Chrome 未來勢必也會將平行化技術完善的實踐在瀏覽器裡面。

這篇論文主要都是討論概念的可行性,技術千奇百怪,永遠都在進步,又是同個概念,「沒有絕對,只有相對」,針對不同領域會各有選擇。總之我認為這篇論文滿有啟發性的,整理一些重點加上心得與大家分享。

首先來了解一下什麼是平行化(Parallelism)和並行化(Concurrency):

如果兩個任務分配到一個CPU核心,在取得的時間片段中交互執行,稱之為並行。如果有兩個核心,兩個任務各分配到其中之一同時執行,稱之為平行。現今開發者對於並行設計應不陌生,利用並行運算處理多個流程,讓客戶端以為任務「同時」執行,或者是某任務被阻斷(Block)之時,切換另一任務執行,避免等待而浪費CPU執行時間,用以提升整體任務執行效率。
過去十年多以來,處理器著重在多核心的發展,就連個人電腦、智慧型手機等,多核心處理器的搭載已經是基本配備,在提升整體任務執行效率這方面,越來越多開發者注意到,設法將任務分配至多個核心上平行執行,成為另一個可行途徑。 (來源)

平行化卻容易有資料競奪的衝突發生,因為大家同時都在做事,一不小心就順序錯亂了。舉個例子今天媽媽生日,爸爸買了蛋糕回來,但是你不知道所以你也買了一個,結果最後才發現兩個人都買了。記憶體也是差不多的情況,一隻程式和另一隻程式可能不小心重複讀寫到同一個位置。想了解更多可以看一下這篇

幫大家複習一下歷史,所以後來就開發出沒有資料競奪問題的程式語言 — Rust。然後,能充分體現細緻平行處理優勢的新瀏覽器引擎 — Servo 就誕生了!


一切又要回到根本:
Q:我們想解決什麼問題?
A:我們希望「速度快」且「省資源」。在電腦可能不明顯,但行動裝置不管是處理速度,或是能源節省,就顯得特別重要。舉了例子,在電腦開 Google Doc 都是用瀏覽器,可是用手機、平板我們反而會開 APP。不就是因為慢嗎?若是一味追求速度,一下子就沒電了,那比慢還要更慘(現代人沒手機會死)。所以兩個條件都要滿足,當然也會有所取捨。

想要速度快大概有幾種做法:Effective Caching、Parallelization、Prefetching、Speculative Loading、Cloud-Based Optimizations。這邊不特別解釋這些,查一下就會知道了。

而今天我們就想要從 Parallelization 著手!


關於平行,也不是切成越多執行緒越好。我們之前提到過 DOM tree、Style Tree、Layout Tree,平行處理聽起來一定會比較快,但想像一下,阿基師做菜時可能會需要兩個助手,這時候大家彼此配合剛剛好,但是硬是塞十個助手給阿基師,還規定十個人都要做事,那這下豈不是反而成了礙手礙腳。程式執行實際情況大概也會像是這樣。

至於省資源方面,平行話只是把原本長度的工作份量切成好幾份執行,自然就不會有太多的變化,即使因為要平行化演算法可能會改動,但影響微乎其微。


來看看瀏覽器的解頗分析圖(這個系列下來已經出現第 n 遍了 XD)


這篇論文提到說可以將 lexing(見上圖)拆成好幾個片段進行解析。每隔一段字串,當演算法認為是「穩定的」,代表這邊可以切開獨立運算,於是就可以同時算然後再整合。適用圖片解析、文法檢查等等,有就是單一片段與整體程式碼可以互為獨立。

此外除了論文提到的方法,還有做法是在解析 tree 的時候,進行平行處理。一般處理 tree 的時候,要不最大深度,要不最大廣度(可以參考這個)。但不論哪種,只有單一執行緒的時候還是很慢。不過我們也可以同時走好幾個樹枝,也就快多了,就像好幾個人同時探索一個地圖一樣。甚至樹枝份量不一樣大的時候,還可以協調執行緒(避免有人一堆事,有人閒閒沒事幹),讓大家的運算量盡量一樣,這也是目前 Firefox 的做法。如下圖所示(取自 Mozilla)而這篇有針對這部份細節實作有更深多解說。


Javascript 語言本身就是異步處理,沒有 lock 也沒有 thread,但可以並行化處理很多事件。不過論文中也提出一些擔憂,例如點擊按鈕讓目前視窗會漸漸消失,而點另個按鈕可以讓視窗漸漸出現,要是先點第一個在消失的過程中,在點第二個,就會出問題了!這是因為 JS 沒有 lock,無法處理 race 的問題。


此外在渲染的時候,如果我們在解析 layout 的時候就能分析好哪些區塊會怎樣變,就可以將變化個別處理。舉個例子,畫面左半邊有一個 event 控制一個A區塊的顏色變化,畫面右半邊有另一個 event 控制另一個B區塊的文字變化,並且兩個區塊沒有重疊。如果我們沒辦法預先知道兩個區塊沒有相干,我們就要先算A的顏色變化,再算B的顏色變化,最後才能重新將畫面渲染。但這樣就浪費太多時間了!所以如果能知道哪些區塊彼此獨立,也就可以平行化處理。


以上就是一些瀏覽器可以平行化的部分,當然都只是講個概念,實際執行就會發現問題很多,例如想要區分區塊是不是不相干牽扯到好幾個 tree 還要有搭配 JS 計算,做起來並不容易。此外平行化本身就容易產生錯誤,任何一點小錯誤都不被允許,如此一來設計也困難多了。

我相信還有很多地方可以用平行化改善,甚至如何實作每個部分的平行化就可能有好幾種方法。可以預見未來的瀏覽器都會慢慢加入這些優化的方式,網路的範圍很廣,但我們瀏覽的速度更快!


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


關於作者

劉安齊

軟體工程師,熱愛寫程式,更喜歡推廣程式讓更多人學會