iT邦幫忙

第 12 屆 iT 邦幫忙鐵人賽

DAY 29
1
Mobile Development

Why Flutter why? 從表層到底層,從如何到為何。系列 第 29

days[28] = "為什麼Flutter的渲染樹這麼複雜?(下)"

上一篇我們講到RenderObject layout和Widget/Element build的演算法是如何幫助Flutter迅速的處理節點數量龐大的渲染樹,以支援Flutter激進式複合的設計理念。今天就讓我們繼續介紹渲染樹中,其它同樣能夠增進整體效能的演算法和機制。

線性調和(Linear reconciliation)

Reconcilation這個用法據我所知應該也是從React來的,代表的是Virtual DOM改變時,使DOM和Virtual DOM同步的過程。至於在Flutter中,我們指的是當Widget Tree改變後,如何更新它背後對應的Element Tree。首先我們當然不會想要重建整個Element Tree,畢竟它和它背後的RenderObject Tree都相對昂貴,因此我們必須盡可能重複使用原有的Element Tree。也就是說,如何從舊有的Element Tree,經過最少的步驟,最小的改動,達到和新Widget Tree匹配的新Element Tree,就是這一節要探討的問題。

一般而言,在不考慮現實應用的情境下,這類問題會採用tree-diff演算法。但這類型的演算法經常是O(N³)或O(N²logN),對於widget數量龐大的Flutter來說,顯然不是可行的作法。幸好,在現實應用中,tree的變化絕對不是完全隨機的,而我們也就可以根據最常見的情境來設計我們的演算法。

Flutter最後選擇的策略是,對於每一個Element,只考慮重複利用自己的child,而不去判斷是否能從別的地方挪用別人的child。我們會在下一節看到Flutter如何處理後面這個情境(劇透:GlobalKey)。

https://ithelp.ithome.com.tw/upload/images/20200929/20129053EtBwjbylsR.png
也就是說,一般最簡單的tree-diff演算法可能會看到New Tree的藍色部份,就在整棵Old Tree中尋找,然後說「嘿!我只要把藍色部份移過來就好了。」聽起來很美好,但你可以想像在整棵樹中找到這樣剛好匹配的子樹,並不是一件容易的事。而且,在現實應用程式UI中,Element更換parent也不是最常發生的事。因此,Flutter的reconciliation只考慮sibling Element間的重複利用,並採用O(N)的演算法走過每個Element的child list來決定是否重用。

如果你還沒發現的話,這裡描述的其實就是"key是如何影響updateChildren的?"一文中,那個有著六大迴圈的可怕演算法。上次已經非常詳細的講解了它的原始碼,這次就讓我們用幾張精美示意圖來稍微複習一下:
https://ithelp.ithome.com.tw/upload/images/20200929/2012905394reftA6CB.png
首先來看看新舊children發生了什麼變化:

  1. 藍色和黃色位置互換了
  2. 多了一個紅色
  3. 綠色代表沒變的child

Flutter Reconcilation演算法一開始會試著從頂部和底部開始匹配child,也就是判斷Widget.canUpdate==true,能夠匹配的就直接更新,不重建Element。最後停在第一個不匹配的child,留下中間包含所有不匹配child的部份,但注意中間也有可能包含可以匹配的child。

https://ithelp.ithome.com.tw/upload/images/20200929/20129053vY8dWEhGxh.png
接下來把old children的中間部份,根據key做成hash table,並把沒有key的捨棄。如此一來,之後就可以用O(1)的時間,查找可以重複利用的child。

https://ithelp.ithome.com.tw/upload/images/20200929/20129053r1oi2iuNTf.png
最後走過new children的中間部份,根據key查詢hash table,取得可以重複利用的child。這裡新增的紅色child因為沒有匹配,就會建立新的Element。值得注意的是,剩下的綠色child雖然理論上是可以匹配的,但它的舊Element在上一步被捨棄了,因此也必須重建。這就是Flutter Reconcilation演算法,為了達到O(N)的時間複雜度,並針對常見情境最佳化,所做出的小小犧牲。事實上我們也可以想像,兩個有key的widget中間包含一個沒有key的widget,真的是非常少見的情境。

具體上來說,整個演算法是針對以下情境進行了最佳化:

  • old children是空的(建立一整個新的list)
  • 新舊list完全一樣(可能只有widget設定改變)
  • 只在同一個位置發生一個以上widget的新增或刪除
  • 新舊list包含帶有相同key的widget

我們可以看到,這些的確是涵蓋了現實應用中最常發生的幾個情境。

樹木手術(Tree surgery)

對樹木動手術,在樹學上指的是把一段樹枝剪下來,嫁接到樹的其它地方。而在數學上,指的是移動整個subtree到不同的parent底下。上一節提到,在現實應用中,subtree更換parent的情境是比較少見的,但也不是完全沒有。例如其中一個應用是Hero Transition,或其它任何在多個頁面重複使用同一個widget的情境。

當然,如果你有看之前的"為什麼要有key?"一文,應該已經知道,我們是透過在這些須要被重複使用的Widget上插入GlobalKey,來保存它的Element, State以及RenderOject。

具體上來說,Element.mount時會檢查它的widget有沒有GlobalKey,如果有的話就將key和Element註冊到一個全域的static map中,以供後續重複使用。當我們把帶有相同GlobalKey的Widget從一個parent移動到另一個parent,就會去查詢GlobalKey map中有沒有對應的Element,如果有的話就可以直接搬過來重用。不僅如此,因為在layout時從parent傳到child的唯一參數就是constraints,如果新parent傳下來的constraints沒有變,搬家的整個RenderObject subtree也就不須要重新進行layout。

常數因子最佳化(Constant-factor optimizations)

從上一篇到這篇的Tree surgery,都是會影響演算法整體時間複雜度的設計,也就是隨著n(widget數量)越大,它們的效果也就越顯著。除此之外,為了能夠更全面的支援激進式複合,Flutter還有一些雖然不會影響時間複雜度,但也相當重要的最佳化機制。

  • Child-model agnostic:依常理來說,絕大多數的tree資料結構,要嘛是child保有parent reference,不然就是parent保有children list。然而Flutter卻在RenderObject Tree的實作上,採取了一個相當奇葩的作法,也就是讓不同的RenderObject自己定義parent要怎麼保存child。例如說在RenderStack(和其它使用ContainerRenderObjectMixin的RenderObject)中,children是透過雙向鍊結串列(Doubly LinkedList)來保存的,但在RenderPadding(和其它只有單一child的RenderObject)中,child是直接作為一個成員變數來保存,因此在進行layout時可以更快速的存取和計算。

  • RenderParagraph:在各種layout系統中,文字的layout往往是比較麻煩的,因為我們很難事先知道這些文字的字體、粗細、各種修飾,會讓它layout出來之後變成幾行,佔據多少空間。因此在"Flutter Web是怎麼運作的?(上)"一文中,我們看到web上有個layout文字的小技巧。而在"為什麼Flutter的渲染樹這麼複雜?(上)"一文中,我們也看到Android的View base class包含了一些文字相關的屬性,也就是說所有View都有可能須要依賴subtree中文字layout的結果,再去調整自己的layout。幸好,Flutter的激進式複合讓我們可以避免這種問題。我們把最純粹的文字渲染部份獨立出來,打造一個特殊的RenderParagraph來處理,而整個tree上的其它RenderObject,完全不需要在乎它的子樹中,有沒有文字的渲染。再加上我們特殊的layout演算法,只要parent傳下去的constraints沒變,RenderParagraph就不須要重新計算它的文字layout,即使是在進行tree surgery的時候。

  • Observable objects:雖然Flutter中絕大部分都是採用響應式的設計,但有時候為了進行一些最佳化,也會採用觀察者模式。舉例來說,Animation就是一個可以被監聽它的變化的物件。這樣的物件可以從我們的Widget tree被傳遞到RenderObject Tree中,讓RederObject直接監聽變化,並根據變化的類型來決定只進行render pipeline的其中一部份。例如當Animation是顏色或透明度的變化時,RenderObject就不需要重新進行layout,只須要進行paint就好了。

這些機制雖然看起不是那麼起眼,但在龐大的widget tree中累積起來,對於渲染效能的影響也是相當可觀的。

結語

我們從最一開始,為了解釋Flutter的渲染樹為什麼有這麼多複雜的演算法和機制,先介紹了Flutter採取激進式複合設計理念的前因後果,接著說明了激進式複合的龐大Widget可能帶來的效能影響,最後介紹了Flutter在三顆渲染樹中,為了增進效能所設計的各種演算法和機制。

其實,這三篇的小系列主要內容都是來自Flutter官方文件中的Inside Fluter - Aggressive Composibility這節。當年剛開始學Flutter的時候,好奇的看了兩三遍,但總是看到一半就因為太難懂而放棄了。後來認真的從頭開始,把渲染樹的各種運作機制搞懂之後,才終於真正瞭解這份文件的內容。因此三篇文章裡面除了官方的內容,也加入了大量我自己的理解和解釋,包含第一篇追根究底的討論,到底為什麼要有Aggressive Composibility。如果你剛好也有看這份官方文件,並且發現我的理解有誤的地方,請務必提出指正。

明天就是最後一篇了,讓我看看會不會作夢夢到什麼好題目吧。


上一篇
days[27] = "為什麼Flutter的渲染樹這麼複雜?(中)"
下一篇
days[29] = "為什麼要瞭解底層實作?為什麼要問為什麼?"
系列文
Why Flutter why? 從表層到底層,從如何到為何。30

尚未有邦友留言

立即登入留言