iT邦幫忙

第 12 屆 iT 邦幫忙鐵人賽

DAY 28
0
Mobile Development

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

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

我們在上一篇提到,Flutter之所以有三顆渲染樹,而其中的各種演算法和機制之所以如此複雜,一切都是為了支援Flutter激進式複合的設計理念,讓我們可以在開發時保有最大的彈性和方便,同時在執行時擁有最佳的效能。

今天我們就繼續來看看,這些演算法機制究竟是如何能夠以極佳的效率來處理Flutter無數的Widget和其背後的Element, RenderObject的。

Sublinear Layout

不論什麼平台、什麼框架,layout幾乎永遠是渲染過程中最花時間的一個步驟。以最粗略的直覺來看,因為畫面上的每個元素至少都需要計算它的大小和位置,因此第一次的layout至少就是O(N)起跳,後續的更新才有可能更低。再來每個元素之間還會彼此互相影響,這時如果沒有一個良好的設計,很容易一不小心就變成O(N²)甚至更糟。

例如在Android的layout系統中就有著名的Double Taxation問題,讓它的演算法有時候必須在parent-child間來回幾次,才能決定最終的layout,而當我們的層數越多時,這個問題就會越嚴重。這也就是為什麼Android後來推出了ConstraintLayout,讓我們可以更方便的用單一一層來定義以前可能須要好幾層的layout,藉此迴避Double Taxation的問題。

至於Flutter,如果你有看之前的"Layout是怎麼運作的?" ,應該就能猜到它的演算法正是在第一次layout時可以達到O(N),而後續更新還可以更低,也就是所謂的Sublinear。也就是說,隨著Widget數量的成長,layout更新時間並不會等比例成長,而是會比Widget成長的更慢一些。

讓我們來稍微複習一下整個Layout流程。首先parent RenderObject會呼叫children的layout,並將Constraints傳遞下去。以RenderBox來說Constraints是由min/max width/height四個數字組成的。child根據這個Constraints和自己的preference,來進行subtree的Layout,並決定自身的size回傳給parent。parent根據children的size和自己的layou邏輯來決定children position,最後決定自己的size再次回傳上去。一般常見的layout演算法可能會將size和position分兩次進行,但Flutter將它們結合起來,構成了不斷向下傳遞Contraints,不斷向上傳遞size的one-pass depth-first traversal。

在此之上,Flutter還添加了幾個機制,在畫面更新時避免一些不必要的layout,進一步達到sublinear的效能:

  1. 如果parent給child的constraints和上一個frame一樣,child本身也沒有mark dirty,這個child就完全不需要重新layout。因為這時候對child來說,它在layout時的input(constraints, states, childrens...)和上一個frame一樣,output(size)自然也就不會改變。
    值得注意的是,position並不是layout的一個input。child不會也無法根據它的position來進行layout,因為它是先決定了自己整個subtree的layout,再由parent決定它的position。因此當parent要移動child的時候(例如拖拉),contraints沒有改變,child就完全不需要重新layout。

第一點講的是child須不須要向下重新進行layout,而接下來的三點都是在處理向上的情境:當child可能因為被mark dirty而重新進行subtree的layout之後,必須回傳size給parent。而parent則有可能必須重新進行layout,計算自己的size,再一路回傳上去。然而,這個一路向上的重新layout,在符合某些條件的情況下是可以中斷的,而這時候的中斷點,就是Flutter中所謂的Relayout Boundary
https://ithelp.ithome.com.tw/upload/images/20200928/20129053QEND0IYSxO.png
簡單來說,因為child唯一會回傳的資訊就只有size,只要size沒有改變,或是parent不在乎child的size,就不須要重新layout。具體細節如下:

  1. 當parent呼叫child的layout函數時,可以傳遞一個parentUsesSize標籤。這是指parent會不會根據child回傳的size來決定自己的size,例如Container,在有child時會選擇盡量和child一樣大,但還是要符合Constraints。當parentUsesSize是false,也就是大多數預設情況下,即使child可能因為state改變,被mark dirty,然後改變了自己的size,這時候parent只需要重新決定child的position就好,不需要再次根據child回傳的size來決定自己的size,也就不會觸發一連串向上回傳size,讓parent重新layout的動作。
void layout(Constraints constraints, { bool parentUsesSize = false })
  1. 如果parent傳遞給child的是Constraints.Tight,以BoxConstraints來說就是minWith==maxWith && minHeight==maxHeight這樣的條件,也就是說child的size已經直接被parent決定了,那麼無論child整個subtree的layout如何改變,都只發生在它自己的那個小框框裡。這時候即使parentUsesSize==true(不符合2.),因為parent傳下去的tight constraints沒變,child傳回來的size沒變,parent也不須要重新計算自己的size。

  2. RenderObject本身有一個sizedByParent標籤,用來讓各種RenderObject宣告自己是不是只需要靠parent傳遞下來的constraints就可以決定自己的size。也就是說自己沒有會影響size的參數(width/height/flex...),也不會根據child size來決定自己的size(Container),唯一的input就是parent傳下來的constraints。
    如果child宣告了sizedByParent==true,這時候即使parent在呼叫child layout時的constraints.isTight==false(不符合3.),parentUsesSize==true(不符合2.),parent還是不需要在child改變layout後再次進行自己的layout,因為parent沒有傳遞新的constraints,child的size也還是沒有改變。

以上三點關於Relayout Boundary雖然解釋起來稍微有點囉唆,但其實合併起來程式碼就只有這樣:

    // In RenderObject.layout()
    ....
    if (!parentUsesSize || sizedByParent || constraints.isTight || parent is! RenderObject) {
      relayoutBoundary = this;
    } else {
      relayoutBoundary = (parent as RenderObject)._relayoutBoundary;
    }

可以很輕易的看出,!parentUsesSize(2.)、sizedByParent(4.)、constraints.isTight(3.)只要符合任意一個條件,這個RenderObject就會作為RelayoutBoundary,讓relayout的向上傳遞中斷在這裡,這件事情具體上發生在:

  // In RenderObject
  void markNeedsLayout() {
    if (_needsLayout) {
      return;
    }
    if (_relayoutBoundary != this) {
      markParentNeedsLayout();
    } else {
      _needsLayout = true;
      ....
    }
  }

當我們把一個RenderObject標記成須要重新layout時,會根據_relayoutBoundary,一路向上尋找哪一個節點是最近的Relayout Boundary,最後把它設成_neeedsLayout = true

整體來說,因為同時有這些向上和向下的演算法最佳化,當我們將RenderObject Tree中的某一節點markNeedsLayout時,只有它周圍的一部分會須要一起更新,藉此達到sublinear的layout效能。

Sublinear Widget Building

Widget Tree和Element Tree的整個build流程我想就不用再複習了,如果你有看之前的渲染樹系列的話應該都有留下深刻的印象。另外我們應該也很容易想像,Widget Building演算法同樣是第一次進行時O(N),而之後的更新可以透過幾個最佳化機制來達到sublinear。具體細節如下:

  1. 當我們呼叫setState(),而對應的Element被mark dirty時,系統會額外把它加入一個dirty Element list。當build流程開始時,系統會直接從這個list裡面的Element開始一個個進行rebuild,而不是從Root開始遞迴的rebuild下來。
      // 
      // In BuildOwner.scheduleBuildFor
      ....
      _dirtyElements.add(element);
      element._inDirtyList = true;
      ....

      // In BuildOwner.buildScope
      int dirtyCount = _dirtyElements.length;
      int index = 0;
      while (index < dirtyCount) {
        ....
        try {
          _dirtyElements[index].rebuild();
        } catch (e, stack) {
        ....
  1. 上面講的是Element把自己mark dirty而被rebuild的情況。若Element沒有mark dirty,而是由其parent向下呼叫了它的build,這時候因為Widget本身是immutable,Element只需要確認它拿到的new Widget和之前是不是同一個instance,如果是的話就可以直接跳過build,因為一切都沒有改變。這個機制也衍生出了被稱為reprojection的技巧,也就是把一個StatefuleWidget Tree中一部分不會改變的subtree作為成員變數保留下來,每次build時都使用同一個subtree的instance,藉此避免不必要的rebuild。例如Provider中的Consumer,就是一個很常見的例子:
    https://ithelp.ithome.com.tw/upload/images/20200929/20129053DNErJauxln.png

  2. 我們知道我們可以透過InheritedWidget來提供底下的Widget一些資訊,反過來說,就是底層的Widget必須依賴這些資訊來build。例如說整個App最上層的Theme Data,如果每個Widget都要從parent, grandparent, grandgrandparent一路找上去才能拿到theme data,想必就是個O(N²)的演算法。因此Flutter採取了常見的以空間換取時間的策略,也就是在每一個Element中建立一個Hash Table,儲存它上面所有InheritedWidget相關的資訊,藉此達到O(1)的查詢效率。

abstract class Element extends DiagnosticableTree implements BuildContext {
  ....
  // Custom implementation of hash code optimized for the ".of" pattern used
  // with `InheritedWidgets`.
  //
  // `Element.dependOnInheritedWidgetOfExactType` relies heavily on hash-based
  // `Set` look-ups, putting this getter on the performance critical path.
  //
  // The value is designed to fit within the SMI representation. This makes
  // the cached value use less memory (one field and no extra heap objects) and
  // cheap to compare (no indirection).
  //
  // See also:
  //
  //  * https://dart.dev/articles/dart-vm/numeric-computation, which
  //    explains how numbers are represented in Dart.
  @nonVirtual
  @override
  // ignore: avoid_equals_and_hash_code_on_mutable_classes
  int get hashCode => _cachedHash;
  final int _cachedHash = _nextHashCode = (_nextHashCode + 1) % 0xffffff;
  static int _nextHashCode = 1;
}

結果最後還是沒有講完,我們還剩下一點點關於children在列表中移動,或是改變parent時的優化,以及其它和整體演算法無關,主要發生在葉節點的各種小技巧。我們下次見!


上一篇
days[26] = "為什麼Flutter的渲染樹這麼複雜?(上)"
下一篇
days[28] = "為什麼Flutter的渲染樹這麼複雜?(下)"
系列文
Why Flutter why? 從表層到底層,從如何到為何。30

尚未有邦友留言

立即登入留言