我們在上一篇提到，Flutter之所以有三顆渲染樹，而其中的各種演算法和機制之所以如此複雜，一切都是為了支援Flutter激進式複合的設計理念，讓我們可以在開發時保有最大的彈性和方便，同時在執行時擁有最佳的效能。
今天我們就繼續來看看，這些演算法機制究竟是如何能夠以極佳的效率來處理Flutter無數的Widget和其背後的Element, RenderObject的。
不論什麼平台、什麼框架，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的效能：
第一點講的是child須不須要向下重新進行layout，而接下來的三點都是在處理向上的情境：當child可能因為被mark dirty而重新進行subtree的layout之後，必須回傳size給parent。而parent則有可能必須重新進行layout，計算自己的size，再一路回傳上去。然而，這個一路向上的重新layout，在符合某些條件的情況下是可以中斷的，而這時候的中斷點，就是Flutter中所謂的Relayout Boundary。
簡單來說，因為child唯一會回傳的資訊就只有size，只要size沒有改變，或是parent不在乎child的size，就不須要重新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 })
如果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。
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效能。
Widget Tree和Element Tree的整個build流程我想就不用再複習了，如果你有看之前的渲染樹系列的話應該都有留下深刻的印象。另外我們應該也很容易想像，Widget Building演算法同樣是第一次進行時O(N)，而之後的更新可以透過幾個最佳化機制來達到sublinear。具體細節如下：
//
// 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) {
....
上面講的是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，就是一個很常見的例子：
我們知道我們可以透過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時的優化，以及其它和整體演算法無關，主要發生在葉節點的各種小技巧。我們下次見！
iThome鐵人賽
看影片追技術