元ネタ: https://www.youtube.com/watch?v=UUfXWzp0-DU

2016年5月5日に行われた発表。
Flutterがどうやって60FPSで、ウィジェットを画面上の1ピクセルに変換しているのかを説明する動画。

※内容は適宜意訳してます。また私自身、英語が堪能ではないので誤訳などあるかもしれません。間違いなどあればご指摘ください。

DISCLAIMER

ゲストスピーカーの見方や意見はあくまで彼らのものであり、Google社としての見方や意見を表しているとは限りません。

The Flutter Rendering Pipeline

Adam Barthです。Flutterのチームリーダーです。Flutterの前は、Chromeで7年間主にChromeのレンダリングエンジンに従事し、現在は2年ほどFlutterの仕事をしています。
このトークでは、FlutterのRendering Pipelineについて話そうと思います。

話を整理するために、Flutterのアーキテクチャ全体の図を紹介します。
1番下にエンジンがあります。エンジンはとても低レイヤーのAPIを提供します。
このエンジンはテキストやベクター画像を賢く画面に描画してくれます。
その上にはフレームワークが存在します。このトークでより詳しくお話ししますが、いくつかのレイヤーから構成されます。

このトークでは、フレームワーク中でも低レベル寄りのRendering Layerについて紹介します。Rendering Layerは画面を管理する責務を持ち、画面に色々な種類のウィジェットのためのスペースを確保したり、実際にそのウィジェットを表示させたりします。

フレームワークの上には、あなたが書いたアプリケーションが乗っています。

Flutterのpipelineには、たくさんのステップがあります。
例えばユーザが画面をタッチしたら、アニメーションが走り、ウィジェットがビルドされます。
ウィジェットのビルドについてはIanが詳しく説明していますが、ビルドの後には3ステップから構成されるRendering Phaseに入ります。

初めは、Layout Stepという、画面上の位置決めとサイズ決めを行うステップです。
次はPainting Stepという、どのElementがどのような見た目になるのかを決めるステップ、
その後Composite Stepという、前のステップの結果を順序通りに描画して積むステップが実行されます。
そして最終的に、Rasterization Stepで、今まで描画した抽象的なデータを実際のピクセルに変換する処理を行い、画面上に表示させます。

この発表では、このLayout Step、Painting Step、Compositing Stepについて話していきたいと思います。

定理: シンプルは速い（Simple is Fast）

Rendering Pipelineの設計方針は”Simple is Fast"です。
シンプルで直感的でよく知られている性質のアルゴリズムを使えば、その性質も活かしやすいし最適化もしやすく、速くできます。
例えば、Layout StepもPainting Stepも、1-passの線形時間のアルゴリズムを使っています。
木構造を上から下に辿っていき、再帰的に処理をするようなアルゴリズムです。

対照的に、multi-passなレイアウトを行う他のシステムの場合は、木構造のある地点から下へ辿っていき、何かしらの情報を集めた後、もう一度下へ辿りサイズの調整を行なったりします。
このようなアルゴリズムがネストすることを考えると、N^2になることが想像つくと思います。

なのでFlutterでは、木構造を一回だけ辿り全てのノードを訪問し再帰的に処理するような1-passのレイアウトを実現したいです。
そこで、FlutterではレイアウトのためにとてもシンプルなConstraint Modelを使用します。

例えば、UIKitでは位置決めのために複雑な線形Constraint Modelをいろんな方法で使っています。この方法にはいくつかメリットがありますが、私たちは「もっとシンプルにできないか？」と考えました。
FlutterのConstraint Modelは基本的に、min/max width/heightで構成されるBoxです。これはConstraint領域がとても計算がしやすく、例えば、二つのConstraintを合成する計算はとても分かりやすいです。
そのため、Constraintソルバーもとてもシンプルになります。
そして、このシンプルなBox Constraintsで十分に様々なレイアウトを表現できました。

最後に、Flutterでは、画面上のどの四角い領域が再描画の必要があるかを追跡する方法ではなく、再描画処理を全ての構造的に行いました。
「この部分は再描画の必要がある」という判断を画面上ではなく木構造上で行うことにより、とても大きなパフォーマンスのメリットが得られました。
特に、モダンなモバイル端末上でこのアドバンテージを活かせ、Composite処理がとても有利になります。

Layout

さて、まず私が初めに話すのは、レイアウトについてです。どのように動いているのでしょうか？

LayoutやPaintなど使われる全てのオブジェクトのベースは、RenderObjectと呼ばれるクラスです。
RenderObject自体はとても抽象的な概念で、PipelineOwner(パイプラインを開始したオブジェクト)と親のRenderObjectを表します。ですが基本的に子供 childrenについては何も知りません。
RenderObjectが知っているのは、自分の子供をvisitする方法だけなので、RenderObject毎に異なる子供のモデルを持つことができます。
例えば、単一のユニークな子供を持つRenderObjectや、複数の子供のリストを持つRenderObject、いくつかの名前付きの子供を持つRenderObjectを考えることができます。
また、その他のアルゴリズム的観点から見ても子供のモデルが何かを私たちが知る必要はありません。完全にRenderObjectに委ねられています。

しかし、どのようにLayoutやPaintを抽象的に行うのでしょうか。
重要な概念として、ParentDataというRenderObjectが持つスロットがあります。このスロットは、親のRenderObjectがデータを保存することができる領域です。

// begin: この辺り翻訳自信なし

もしあなたがWebのような別の描画システムについて詳しければ、ブロック要素の中にインライン要素を配置することが禁止されていたのは、例えばブロック要素が情報を子供に持たせる必要があるのですが、インライン要素はこのスロットを持っていないためでした。
なので、このような匿名のRenderObjectをWebのRender Tree上では基本的にあるデータ構造に変換しています。

// end: この辺り翻訳自信なし

Flutterではこれを避けるため、子供側ではなく親によって管理されるこのParentDataスロットを実装しました。
このParentDataは位置決め(Positioning)について解説する際に大切になってきます。

RenderObjectについて重要な点は、座標システムなど関する概念が一切登場しない純粋な木構造であるという点です。

Layout Data Flow

RenderObjectは次のような1-passのLayoutデータフローを定義しています。
木構造を深さ優先探索でwalkし、再帰的にConstraintsを受け渡していきます。RenderObjectには任意のConstraintsが渡されますが、実際にはRenderBoxと呼ばれるRenderObjectが良く使われ、この場合はBoxConstraintsという私が先ほど解説したConstraintsが渡されます。
そして、木構造の下から上に向かって、Sizeが登っていきます。なので、ConstraintsはどのぐらいSizeが大きくなるべきかという情報を表します。

親は子供に話しかけ、応答が返ってくると、自分が実際にどのぐらいのSizeになるか判明するのです。
いいですね？

RenderBox

抽象的な話をしましたが、より具体的な話に移りましょう。
とても便利な座標系としてデカルト座標系があり、これはxとy、widthとheightで構成されます。
RenderObjectをこのデカルト座標系に特殊化したものとして、RenderBoxと呼ばれるクラスがあり、これはSize決めと位置決めに関してより具体的に決められているものです。
特にSizeに関してはwidthとheightを持っています。これはRederObjectが円形上のセクターなどの任意の値を持てるのと対照的です。

また、いくつかの内部的(Intricsic)なSize情報をいくつかの難解なケースのために保持しています。

BoxConstraints

Boxモデルは先ほど話したBoxConstraintsを主として使っていくモデルです。
BoxConstraintsは基本的にスライドに示したようなものです。
width軸にはminとmaxがあり、height軸にもminとmaxがあります。
そして、親がこれらのConstraintsを渡してきたら、明るいグレー色で示したどこかの領域(width, heightそれぞれのmin/max範囲のどこか)にSizeを決定するというルールになっています。
小さすぎることも許されませんし、大きすぎることもダメです。

とても面白いのは、このシンプルなBoxConstraintsアルゴリズムを使って様々なレイアウトを表現できる点です。

例えば、もっともシンプルなレイアウトは親が完全に子供のSizeを決めることです。
それぞれの親はちょうど100x200ピクセルで、初めの子供は50x50ピクセル、そして次は50x100ピクセルに…といったものです。
このようなレイアウトはOSのWindowsManagerなどでよく使われる方法で、OS上のウィンドウは自分のサイズに対してどのぐらいの大きさになりたいか、何の意見も言えません。
なので、WindowsManagerがWindowのサイズをちょうどこの大きさ、と決定します。
このようなレイアウトをBoxConstraintsをtightにすることによって実現できます。

tightとはつまり、width/heightのminとmaxを同じ値に設定することで、子供は他にConstraintsを満たす選択肢がなくなり、ちょうどこの大きさになれ、と親から指定されることになるわけです。

これが意味するのは、全てのオブジェクトは親の大きさ指示のための準備が必要ということです。例えば、チェックボックスウィジェットは通常固定Sizeで表示したいですが、親が任意のSizeを強制できるため、子供は自分の倍もあるようなSize指定が来る覚悟をしなければなりません。
そのため、チェックボックスは中身を空いている領域で真ん中寄せし、残りの領域を占有します。

他のレイアウトパラダイムとしてWidth-in, Height-outというものがあります。
例えばWebはこのパラダイムを使っていて、Textの表示にとても便利なものです。
基本的には、例えば200pxの幅ちょうどで固定し、高さを中身に合わせて変えるというものです。
大量のテキストを用意し、横幅を設定しテキストが改行され下に広がっていく様子を想像してみましょう。何行になるかが分かり、どのぐらいの高さが必要が判明します。

このレイアウトを表現するためには単純に、横幅はtightで固定し、縦幅はlooseにします。
親は子供の横幅を指定し、子供から縦幅を受け取ります。

このレイアウトはxとyについて対称的に動作するのも面白い点です。逆に、Height-in, Width-outというレイアウトも可能です。
なぜ対称性が必要かというと、このプロジェクトに長く携わった結果、「水平方向にユースケースがあるなら、垂直方向にもユースケースがあるはず」と確信したからです。このトークの後半で詳しく話したいと思います。

BoxParentData

さて、私はParentDataについて説明すると先ほど言いました。
RenderBoxについて面白いのは、Sizeは知っているが、Positionは知らないという点です。
これは、Cocoaのような他のシステムと対照的な部分で、CocoaではそれぞれのUIViewがRectを持っています。Rectとは、SizeとPositionを合わせたものです。
RenderBoxでは、自分のSizeは分かっていますが、自分のPositionは分かりません。

Positionは親によってBoxParentDataのフィールドで制御されます(スライド上のOffsetというフィールド)。親が子供のSizeを全て取得するとき、親は自由なPositionを子供に触れることなく自由に設定することができます。
子供に触れずに(再び子供をvisitなどせずに)自由に動き回らせることができるため、これはウィジェットをスクロールするときなどに非常に効果的です。
親はPositionをTranslateする最低限の作業をするだけで良いのです。

Flex Layout

では、実際にFlex Layoutの例をとってLayoutがどのように行われているか説明しましょう。
Flex Layoutはとてもとても一般的なレイアウトパラダイムです。基本的な考え方は、アイテムをRowかColumnに並べることです。ここでは簡単のためRowの場合を考えます。

いくつかの子供はSizeについて強い意見を持っていて、自分の好みのSizeだったりIntrinsicなSize(内容物に合わせたSize)になりたいと思っています。
その他の子供はフレキシブルで、残った領域を埋めるようにSizeを決定します。
この決定にはもう少し詳細な挙動として、Flex Factorという概念もあります。
Flex Factorは、それぞれ異なる強さを持つバネと考えることができます。

このスライドでは、黄色いウィジェットはFlex Factor: 2を持っています。この2は、Flex Factor: 1を持っているピンクのウィジェットの2倍のSizeになりたい、という意味になります。
緑や赤のウィジェットを小さな積み木のブロックだと思うと、黄色とピンクのウィジェットはその間を異なる強さで引き合うバネだと考えることができます。

これはとても一般的なレイアウトですね。

これから、このレイアウト計算がどのように1-passでBoxConstraintsによって行われるか説明したいと思います。

アルゴリズムの入力値は、全体のmin/maxのwidthと、min/maxのheight、そして親から渡されるConstraintsです。
そして出力値は、親に返答すべき全体のSizeと、子供たちのSizeとPositionです。

この例では、簡単のためwidth/heightのminを0に設定しています。そして、グレー色の部分はheightのminからmaxの領域を表します。
図では実際にどのぐらいの高さになるか表示されてしまってますが、この計算についても段階を追って説明していきます。

STEP1. Layout Inflexible Children

始めのステップは、Inflexible(固定幅)の子供をレイアウトすることです。バネモデルでいうところの積み木ブロックですね。
彼らは自分のサイズについて意見を持っているためSizeを聞いて決定します。

さて、彼らにどんなConstraintsを渡すべきでしょうか？今はRowについて考えているので、Heightについてはとても簡単です。0でも良いし、許される最大のHeightでも良いです。
許される最大のHeightより高いとはみ出てしまう問題が起こるため、これは自然ですね。(つまり、minHeight=0, maxHeight=Constraintsから引き継ぐ)
Widthについては、彼らがなりたいできるだけ小さいSizeになることができます。このSizeは子供が決めることができます。
実際には、Infinityまでのあらゆる望む幅を指定することができます。(つまり、minWidth=0, maxWidth=+Inf)
何故Infinityなのでしょうか？これはとても良い質問です。
実際、初めのバージョンのレイアウトシステムではこの場合にInfinityを使っていませんでした。Constraintsで指定される親の最大幅を渡していました。
しかし、この方法ではたくさんの微妙な問題が引き起こされました。
もし親の最大幅が渡ってきたとして、その最大幅になりたい子供が複数いた場合を想像してみましょう。例えば、3人の子供のうち2人が最大幅になりたい、と言った場合です。
この場合、スペースからはみ出てしまうため、実際には彼らを収めることができなくなってしまいます。
Constraintsとして小さな値を設定しても、大きな値を設定しても、同様の問題が起こるため、実は適切な値は存在しないことになります。また、最大幅として0を設定してしまうと、Sizeは全て0になってしまうため使うことができません。
という訳で、最大幅については制限しない、という意味を込めてInfinityを渡すようにしています。

これらのConstraintsを子供に渡し、緑のウィジェット、赤のウィジェットがそれぞれどのぐらい大きくなりたいか応答します。
そして、親はこの情報を書き留めておき、彼らのWidthを足し合わせ、自分自身がどのぐらいの幅になるべきかを計算します。

STEP2. Compute Free Space

Rowは空いているスペースを埋めようとします。
なので、Inflexibleな子供のスペースを確保し空いているスペースを埋めたあと、あとどのぐらいスペースが空いているかを確認します。
これは単純に自分自身の全体の幅を取得し、足し合わせた子供のWidthを引くだけです。
この時十分なスペースが残っていれば、Flexibleな子供を配置する作業に入ります。

これも単純に、空き領域を計算し、Flex Factorの合計値で割り算することで1 Flex Factor毎の幅を計算します。もし子供が2単位のFlex Factorを持っていれば、計算した幅の2倍の幅に、1単位のFlex Factorを持っていれば、計算した幅の1倍の幅へ決定すればよいです。

STEP3. Layout Flexible Children

Flexibleな子供をレイアウトするとき、以下のようなConstraintsを渡します。
Widthは空いているスペースを埋めるために必要なSizeを指定します。(min=max=flexFactor * widthPerFactor, tightです)
Heightは子供にお任せします。(min=0, max=Constraintsを引き継ぐ)
これは、Width-In, Height-Outモデルと呼んだものでした。

そうしてついに、全ての子供のSizeを取得することができたので、ついに彼らの位置を決めることができます。

STEP4. Position Children

位置決めのアルゴリズムはとてもシンプルです。
順番通りに子供を調べていき、初めのウィジェットの幅をインクリメントし、次のウィジェット、次のウィジェット…とめぐっていくだけです。
何故なら、子供に渡したConstraintsは足し合わせると私たちが望む全体の幅ちょうどになるためです。
Heightについては位置決めにたくさんの選択肢があります。なので、FlexやRowには選択肢が用意されています。AlignをTopに揃える、Bottomに揃える、Centerに揃える、などなどお好みで選ぶことができます。
ここではCenterに寄せています。

今、全員の高さが分かっているため、自分自身の高さは子供の最大の高さになります。
そして、自分自身の高さとそれぞれの子供の高さが分かっているため、Offsetを計算することができます。

ここで注目したいのが、全ての子供のSizeが分かっていないと、位置が決められないが、一度全ての子供のSizeが分かってしまえば、あとは子供に再び触れることなく位置を決められるということです。
つまり、子供たちは自分の位置に関係なく、Sizeを決定することができるということです。
これは、Webのようなレイアウトシステムと対照的で、WebはそれぞれのオブジェクトのSizeは、画面上の位置に依存しています。

これで完了です。この例のFlexをレイアウトすることができました。

(質問: 聞き取れない。恐らく、ColumnでもTopやBottomにAlignできるのか？)
はい、TopやBottomにもそろえることができます。
縦にCenter寄せする代わりに、全てのX座標に0を指定します。

(質問: Inflexibleな子供が大きすぎた場合に何が起こる？)
魅力的な質問ですね。私たちは子供に渡すConstraintsにInfinityを渡しました。そして、子供はとても大きなWidthを決定し、私たちはこれを収めるためのスペースを持っていないとします。
どうするべきでしょうか？とても魅力的です。
このBoxConstraintsが表しているのは、レイアウトの中でどのぐらいのスペースを占有して良いのか、という値であって、子供がどのぐらいの大きさになりたいか、ではないです。
例えば、子供がとても大きくはみ出てしまうケースを考えてみましょう。この場合、彼らをはみ出た外側に描画することもできますし、はみ出た分を描画しないこともできます(Clipする)。実際に見えてる部分だけ描画します。
よって、はみ出た部分はClipされるため見えなくなります。

(質問: 聞き取れない。恐らく、初めのウィジェットが大きすぎた場合、後続のウィジェットが見切れるのか？)
そうです、おっしゃる通り、緑のウィジェットが大きすぎた場合は、ピンクや赤のウィジェットが見えなくなります。

(質問: 聞き取れない。恐らく、Sliverのようにはみ出たウィジェットを評価しないような最適化をしているのか？)
無駄なlayoutやbuildを避ける、より賢く高価なレイアウトもありますが、ここで紹介したFlexはとてもシンプルなものです。

オーバーフローした時に小さな赤い四角を表示するようなデバッグモードがあります。

私がここまで話し、皆さんはWidth-In, Height-OutがこれらのFlexibleな子供にしていされたことに気付いたと思います。
どのぐらいの横幅になってほしいかをこちらが指定し、子供にどのぐらいの高さが必要か質問しています。
試しに、このRowをColumnに回転させてみましょう。縦方向にもこのようなFlexレイアウトが存在するのはとても理にかなっています。
縦方向のFlexレイアウトでは、子供に高さを指示し、どのぐらいの幅になりたいかを質問します。つまり、Height-In, Width-Outとなるわけです。
この縦方向のレイアウトは始めは少し不思議かもしれませんが、実はとても自然なのです。

そして、このようなConstraintベースのシンプルなレイアウトアルゴリズムは、様々なレイアウトを実現するために十分だとということが分かりました。
実際、私たちはMaterial Designの見た目やレイアウトの完全な実装をこのアルゴリズムで実装することができました。

重要な点として、私たちがこのプロジェクトを開始したとき、実は私はこのようなシンプルなConstraintsアルゴリズムで十分か少し懐疑的でした。
これが、RenderObjectというとても汎用的なオブジェクトを用意した一つの理由になります。今後もっと複雑なことをしようとしたとき、特殊化できるだろうと思ったためです。
しかし、実際はこのシンプルなアルゴリズムで全てが実現できてしまったのです。

Relayout Boundary

アルゴリズムがシンプルだと良い理由は、最適化が容易で高速化できる点でした。
子供にタイトなConstraintを与えた場合、子供はちょうどそのサイズになることを意味します。
これは、レイアウトアルゴリズムのデータフローを減らすことができて良いです。

ここにあるTight constaintsとラベルのある要素を考えてみましょう。
子供は指定サイズちょうどになるはずですね。
なので、もしサブツリー（この子供以降の要素）に何か起こりレイアウトが必要になっても、その他の部分には影響を及ぼさないはずです。
なぜなら、ウィジェットはサイズのみによって他の要素とコミュニケーションを取っているからです。（逆にいうと、サイズが変わらなければ他の要素とのコミュニケーションも変わらない）
どんな激しい変更が起こったとしても、他の要素には伝搬しません。

これは、私たちが"Relayout Boundary"と呼ぶものを生成します。
Flutterでは、実行を通じてConstraitsアルゴリズムを監視し、裏でこれらの"Relayout Boundary"を計算しています。
"Relayout Boundary"の内部では、誰かがサイズや位置を変更したとしても、外側に伝搬しなくなります。
他の要素に一切触れることなく、Boundary以下をレイアウトするだけで済むので、めちゃくちゃ効率的です。

よって、今では「レイアウトは線形アルゴリズムだ」と言ってきましたが、実際には「劣線形アルゴリズム(Sub-linear)」です。（線形 O(n) よりもっと早い）
木の全体（要素N個）を調べなくて良いからです。

ここでは、Constraintsがtightな場合を例に挙げましたが、他にもいくつかケースがあります。
一つは、parentUsesSize を false にした場合です。
親が子供に対して、「子供のサイズを親のサイズの計算に使うかどうか」のフラグを渡します。これに false を与えた場合、Relayout Boundaryが生成されます。
なぜなら、子供がサイズを変更したとしても、親は子供のサイズを気にしないので、他の要素に影響が出ないからです。

もう一つのケースは、子供がサイズを親から渡されたConstraintsによってのみ決まると報告した場合です。
例えば、子供は親のサイズいっぱいに広がるサイズを持っていたとします。
親がどんなConstraintsを渡したとしても、子供は---自分の子供のサイズを調べずに---すぐに自身のサイズを決定します。
これもまたRelayout Boundaryを作成します。

もう一点だけ触れておきたい点があります。
レイアウトの際、どのような順番で子供をvisitするべきでしょうか？
先ほどの話では、まずInflexibleな子供をvisitし、次にFlexibleな子供をvisitしていました。
なので、まず緑色の子供、次に赤い子供、そして戻ってきて、黄色の子供、ピンクの子供と続きます。

Paintの順序はこれとは対照的です。
Paintの順序は木に沿って左から右へ向かってvisitします。しかし、Layoutでは別の順序でvisitします。

この順序の違いが、PaintをLayoutとは別のフェーズで行う理由です。
他のPaintとLayoutフェーズを統合しているレイアウトシステムでは、これらの順序の違い問題を解決するためにとても注意深いゴマカシを行なっています。

我々は、この二つのフェーズを分け、それぞれの木全体に対してLinearな走査を行うコンセプトを採用しました。

質問: もしウィジェットが重なったり、透明なウィジェットなどがあった場合は何が起こりますか？
このレイアウトでは全てのウィジェットが隣合っていて重なりはないですが、例えばStackというレイアウトは重なりがあります。
Stackはウィジェット同士を上に積んでいくようなレイアウトで、どのような順序でPaintが行われるかが重要になってきます。
そして、StackはPositionedとnon-Positionedの子供を持ちます。これも先ほどと似たように、面白いLayoutのvisit順序を持っています。

Paint

ここまででさまざまなUIの大きさを決定することができました。ですが、まだどのような見た目をしているのかが分かりません。G.I.ジョーなら「まだ戦いの半分だ」と言うでしょう。（海外のミーム）
これを行うのがPaintフェーズです。

Paint Data Flow

では、実際どのようにPaintを行うのでしょうか。実はとても簡単です。
純粋に、木構造を深さ優先で調べ、画面上のどこにいるのかを表すOffsetを子供に渡していきます。
そして、サイズはすでにわかっているため、自分のUIをその領域に描画するよう指示します。迷うことなく、ただそこに描画するだけです。

シンプルです。スライド一枚で終わっちゃいます。
でもこれだけではありません。

Layers

Paintで複雑な概念はLayerの管理です。
もし全てのUIを一つのBufferに描画するなら話は単純です。しかし、一つのBufferしかない場合、とても制約が多くなります。
例えば、この黄色い物体があなたの触れることのできない別のシステムによって描画される場合を考えて見ましょう。
例としては、ハードウェアVideoコーデックによるテクスチャへの動画の描画が行われていた場合です。

もし何かしらの物体をこの動画の上や背後に描画したい場合、描画内容を二つの異なる単位に分割する必要があります。
再生ボタンのように動画の上に描画されるUIと、動画の背後に描画されるUIですね。
後で正しく見えるよう、Composite(合成)し描画するためにはこの分割が必要です。

この描画におけるトリッキーな処理は、具体的には描画コマンドがどのLayerに格納されるかを決定する処理となります。

概念的にこのLayerはピクセルが格納されるBufferだと思ってもらって結構です。実際にはベクターを格納しており正確ではないですが、あまり気にしないことにします。

Paint into Layers

Paintフェーズの間、木構造を深さ優先で探索し、これらのLayerに対して描画を行います。
緑のバブルは緑のLayerに描画されます。4番のLayerは動画のように、別で合成されるべきLayerです。
4番より後の全てのUIは赤いLayerに描画されます。

ここで興味深い点は、2段目の左側のバブルが部分的に緑で部分的に赤であることです。
例えば、2番の背景である1番の描画後に、2番、3番、4番と描画し上に戻ったあと、まだ描画するものがあるため5番を描画するタイミングです。
2段目の左側のバブルは、自分の子供の描画が終わった後、前回とは別のLayerに描画する必要があったということを意味しています。この時描画されるのが、赤いLayerです。
（2番を描画し、子供の描画をした際、4番が動画専用のLayerであるため、ここでレイヤーの切り替えが発生する。子供の描画が終わった後、追加で5番の描画を行う場合このように切り替え後の赤いレイヤーに描画が行われる）

更に上に戻り、1番に行きますがここでは追加の描画は起こりません。

ここで面白いのは、全てのRenderObjectにユニークなLayerが割り当てられていない点です。
RenderObjectの描画内容は、複数のLayerにまたがります。
他のシステムが同様のことを行なっているかはわかりませんが、これは例えばCocoaはUIViewとCALayerの一対一対応を持つ点と対照的です。
Cocoaでは、UIViewを複数のCALayerに分割することはできません。
Webでも同様に、一つの描画物を複数のレイヤーに分割することはできず、これによるバグがとてもたくさんあります…。

ですが、このシステムではLayerをまたぐことができます。

Paint Data Flow

実現の方法としては、1passの走査時にOffsetを下へ渡した後、TargetLayerが返されます。
TargetLayerは、子供が親に対して指示する描画するべきLayerを表します。

親は子供に「ここに自分自身を描画して」と指示し、子供は親に「この別のLayerから描画を続行して」と応答します。
もしあなたが他の言語を使う人であれば、継続渡しのようなものだと気づくかもしれません。
親が描画を続行すべき継続が返却されるのです。

そしてこのどのLayerに描画されるべきかというComposite戦略の決定は、1passで行われるシンプルな描画コマンドの記録によって実現されています。
（TargetLayerに紐づくDisplayListに対して、描画内容・描画コマンドが記録されていきます。これがシンプルな1passのアルゴリズムによって行われているのです。）

ここで、描画の非ローカルな影響が起こった場合を見てみましょう。
この黄色いLayerが赤いLayerなど木の別の部分に影響を与える場合です。この場合、木の一部の変更によって全く別の木の部分に影響がでるため、描画はとても複雑になります。
黄色いLayerが描画内容を変更すると、全てを描画し直さなければいけません。

ですが、私たちはLayoutフェーズでRelayout Boundaryという、とても賢い方法を使いました。
同じような仕組みをPaintフェーズでも使ったらどうでしょうか？

これが人工的に挿入するRepaint Boundaryです。（人工的＝開発者が手動で挿入する）
Repaint Boundaryは子供が独自の合成Layerを必要とする、と宣言するための方法です。
そして、Repaint Boundaryの部分木の影響は閉じ込められ、親や木の他の部分に影響を与えないという意味になります。

例えば、青いオブジェクトは黄色のオブジェクトが独自のLayerを持つかもたないか、その他どんな処理をしようと関係なく青のLayerに描画されます。
Relayout Boundaryが部分木の影響を閉じ込めたのと同様です。

質問: Relayout BoundaryはLayout Data Flowをみて自動的に挿入されたが、Repaint Boundaryは手動で人工的に挿入しなければいけない？
Repaint Boundaryは自動的に決定することができません。Repaint Boundaryは木の中のどこにでも置けるような柔軟な概念です。
そして、フレームワークはどこに挿入するのが最適なのか知ることができません。
例えば、全てのRenderObjectが独自のRepaint Boundaryを持っていたとすると、全員が合成Layerを持つことになり、これはとても膨大な数の合成Layerの束が必要になってしまいます。
そして、これはLayer管理の複雑化と、実際に画面上に表示されるよりたくさんのGPUによるピクセルの生成が必要になってしまい非効率的です。
かといって、0個のLayerでは意味がありません。
よって、開発しているアプリにとって適切なRepaint Boundaryの数はこの間のどこかになるはずです。
そして、Boundaryがどこに描画されるべきかはアプリのパフォーマンスにとても大きな影響を与え、自動的に計算することができないのです。
例えばアプリの構造をみて、「この領域が再描画されるとき、いつも一緒に再描画される領域はどこ？」だったり、「アプリのどの領域が別のタイミングで再描画される？」のような質問に答えられるのは開発者のみです。
良い例が、スクロールコンポーネントです。左側にスクロール領域が表示され、右側に笑顔マークが表示されているとします。
スクロール領域をスクロールしても、笑顔マークが再描画される必要はありません。
よって、スクロール領域と笑顔マークの間のどこかに、描画の影響を閉じ込めるためのRepaint Boundaryがあるべきです。

Composite

Paintフェーズでは三つのLayerを生成しました。
何のために私たちはこれらのLayerを生成したのでしょうか？

画面を複数の合成Layerに分割するメリットの一つに、見た目の更新をとても素早く行えるという点が挙げられます。
Layerを動かしまわりたいとき、Layerの中身には触れずにOffsetを変更したり変形するだけで良いのです。
何故なら全ての部品を適切な粒度で分割をしているため、再描画時はその内容をただ描画するだけで良いためです。

例えば、黄色いLayerを右に動かしたいとき中身に触れる必要はなく、ただLayerを右に動かしLayer全体を合成しなおせばよいだけです。

Scrolling

この仕組みが活きる良い例は、スクロールです。

ここにスクロールできるリストがあるとしましょう。
グレーの要素はスクロールアイテム、暗いグレーの枠は私たちが見ることのできる領域を
表すビューポートです。
このリストを上方向にスクロールしたとき、素直な実装ではビューポート全体を毎フレーム再描画し、白からグレーに変化したピクセルを反映する必要があります。
なので、RenderObjectの木構造をRepaintBoundaryが現れるまで走査し、その内容を再描画する必要があります。
この処理には無駄があり、非効率的であることが分かります。
スクロールはシステム的にもとても大変な処理なため、できるだけ効率的に行いたいです。

Composited Scrolling

では、分割されたLayerを用いてスクロール要素に対して何を行いましょうか。
始めのスクロール要素を、二番目の要素の位置までスクロールした様子を想像しましょう。
すべきことは、全ての四角形を上にシフトするだけです。Paintをやり直す必要はありませんし、もちろんLayoutも不要です。
ただ、既に記録している描画コマンドを取り出すか、既にピクセルに変換済みであればそれを取り出し、画面に吐き出すだけです。

このスクロール処理の中で必要なPaint処理は、新しくビューポートに現れた要素のためにLayerを作成し、そこにPaintする処理のみです。
更にスクロールした場合も同様で、一度Paintした要素を再びPaintする必要はなく、ただ上にスライドしていけばよいだけです。
緑色の要素が画面の上部へ消えた場合は、その領域をReclaim(回収)することができます。
これにより、Recycling List Viewの仕組みを簡単に実現することができます。

画面上部でLayerの空き領域ができた場合、その領域を画面下部から表示する要素に使うことができます。
この仕組みにより、スクロールしても有限個の領域だけを管理すれば良くなります。

この話は、少し前に説明した「子供は自分のOffsetを知らなくて良い」という話とも繋がってきます。これらの要素の描画内容はOffsetに依存しないため、このように自由に動かすことができるのです。

これらの仕組みにより、スクロール時に必要な処理をとても少なくすることができ、3世代前の古いデバイスでもおよそ1ms以内にスクロール処理を行うことができます。とても高速です。

質問: 他のレイアウトシステムにおけるスクロール処理と比べてどうか？
大体どのシステムでも基本的に似たようなGPUコマンドを使ってこのようなスクロール処理をしています。
違いとしては、開発者がどれだけ自然にこのシステムを使うことができるかという点です。
例えば、AndroidはRecycling List Viewを持っていますが、6個のメソッドをdelegateによって開発者が実装する必要がありとても複雑です。
ですが、FlutterではListViewのウィジェットを置くと、FlutterがRepaintBoundaryで包みます。後は、要素はOffsetに対して不変であったりその他色々な工夫により、スクロール処理はデフォルトで前述した最適なパスを通るようになっています。

質問: ここで言うComposite(合成)の意味について詳しく教えてください。
私はずっとComposite(合成)という用語を使ってましたが、このスライドの図は合成処理のようには見えませんね。
伝統的には、Compositeとはテクスチャ上のピクセルを画面上に順序に沿って転写する処理のことを言います。
Flutterではこの意味でもときどきCompositeという用語を使いますが、別の意味もあります。
それぞれのLayerはDisplay Listなどの描画コマンドのVectorとして表現するか、テクスチャとしてピクセルで表現します。
そして、このピクセルは画面上に直接転写することができます。
沸きあがる疑問としては、いつこれらのLayerをテクスチャ化すべきでしょうか？

他の描画システムでは、ここに対してとても労力が割かれています。Cocoaでは、全てのCALayerがテクスチャです。とてもたくさんのGPUメモリがあれば問題はありません。

Androidの描画システムは反対に、メモリを消費したくないため極力テクスチャにしません。そのため、毎フレームDisplay List全体を1からできるだけ効率よく再描画します。

Flutterのアプローチはこの二つのシステムの中間に位置し、もし同じテクスチャ/Layerを3回描画した場合はテクスチャ化する価値があると判断します。
そして、3回目の描画では一度テクスチャに書き込んでから画面に転写し、以降はそのテクスチャから直接転写するようにします。

この3という数字はマジックナンバーです。
1の場合は、常に間接的にテクスチャを通して描画する処理になります。これはいくつかの場合に非効率的で、例えばMaterial Designの丸い読み込み中インジケーターを想像すると、円弧を常に回転させたりサイズを変えたりする必要があり、決して描画内容が同一のフレームは存在しません。よって、テクスチャから間接的に描画する適切なタイミングはありません。

では、常に描画コマンドから描画すれば良いと思うかもしれませんが、例えばDrawerのようにスライドして現れるUIの場合、中身は変化せず、変化するのはOffsetのみです。
RepaintBoundaryによってDrawerを囲えば、Compositorによって移動させるだけで中身はこのままでよいはずです。
よって、一度Drawer全体をテクスチャ化したらあとは動かすだけなので良さそうです。

では、なぜ3なのでしょうか？分かりません。もしかしたら4でも良いかもしれません。1、2でも良いかもしれません。
しかし実際、3はとても良い数字なのです。コンピュータ科学やエンジニアリングにおける色々なシステムを見渡してみると、2bitの飽和カウンタがとても良いと分かります。これが3である由来です。これは2bitの飽和カウンタなのです。（参考: 2bit 飽和カウンタはCPUの分岐予測で古典的に使われていた手法, 分岐予測の簡単な歴史 – Part 2）

質問: とても小さな部品が沢山あった場合、無駄が発生しない？
はい、先ほどの3という数字だけが答えではありません。実はもっとヒューリスティックにテクスチャ化するかしないかを判定しています。
そして、システムが成熟するにしたがって、このヒューリスティックはより洗練されていくはずです。
このヒューリスティックは、Layerがとても長い長方形のようなピクセルとして保持できない複雑な内容を含んでるかどうかや、余白がとても多いためたくさんの透明ピクセルが必要で無駄であるかなど、たくさんのヒューリスティックがテクスチャ化の判断に使われます。
ですが、ここについて開発者が意識すべきことはありません。全てCompositorによって処理されます。
もしかしたら、今後開発者がこの処理を制御できるような方法を公開するかもしれませんが、そういったことはまだ行っていません。

質問: 自動のテクスチャ化のように、なぜLayerを自動生成しないのか？
恐らく、その方法についても調査すべきでしょう。実際、Debugモードでは全てのRepaintBoundaryを監視し、どのぐらい効果があるのかという統計情報を取っています。
このRepaintBoundaryは99%の確率で親と子供の間で違うタイミングで描画されていれば効率的で良いですね、だったり、親と子供がほぼ同じタイミングで描画されていれば非効率的で良くない、などの情報を確認できます。
そして、この統計情報をRepaintBoundaryの自動生成に使えるかもしれませんが、十分な調査はできていません。

Q: RepaintBoundaryを設置することのトレードオフは何か？
描画コマンドを記録するPaintフェーズにかかる時間 v.s. メモリ使用量とLayer管理のためのオーバーヘッドです。
例えば、無限のメモリを持っていて、本当に良いメモリ管理ツールがあるなら、全てをRepaintBoundaryにするでしょう。

---ここから翻訳自信なし---

この時、画面上の全てのピクセルがRepaintBoundaryになります。
このようなとてもよいピクセルの管理ができるような特化したハードウェアを作り、それをGPUと呼びましょう。
これはパイプラインの一部を別のパイプラインの一部に移動するようなもので、もしこのような重量級のGPUがあり、全ての描画コマンドを画面上に描画してくれるなら、もはやRepaintBoundaryは要りません。これでは意味がないですね。

ですが実際には、開発したアプリの描画パイプラインはそれぞれ異なる制約を持っていて、CPUやGPUの強さもそれぞれ異なります。CPUメモリの量も違いますし、GPUメモリの量も違います。
アプリのワークロードをこれらの異なるリソースにどのように振り分けるかは開発者次第です。
他のGPUが存在しない時代に設計されたデスクトップデバイスなどに特化したシステムと対照的に、私たちは、モバイルデバイスに特化したアプローチを選びました。
Flutterはおおよそモバイルデバイスに最適化しており、開発者が調整できるパラメータは、パイプライン中の各ステージでどこぐらいリソースが利用可能かという点になります。

質問: 自動のテクスチャ化はパイプラインにコマ落ちのようなノイズを加えるのではないか？
これについても検討しました。結果として、そこまで悪影響はないということが分かりました。
理由としては、私の仮説では、全てが同期的ではないためだと思います。
例えば、このフレームで画面上のすべてをテクスチャ化するとしましょう。これはとても大きなコマ落ちを誘発します。
ですが、例えばこの画面を物理的にスクロールし、黒い要素が画面上に現れたとき、1, 2フレームは描画し、3フレーム目でテクスチャ化します。
つまり、全てのテクスチャ化が同時ではないということです。
これにより、実際にはそこまで大きなノイズをパイプラインに与えることはありません。

Flutterは様々な統計情報を取得しています。Observatoryを開けば、タイムラインを記録することができ、時系列でどんな処理が行われているか確認することができます。これにより、パイプラインの各フェーズがどのような順序で行われているか、相対的にどのぐらい時間がかかっているか確認できます。
テクスチャ化を確認できたり、Layoutをどのぐらい行っているか、フレームがPaintによって直接生成されているか、Compositingによって生成されているかを確認できます。

質問: 描画はいつもピクセルによって行われるのか、それともベクター形式で行われるのか？
基本的にベクター形式で描画します。もしPathを描画した場合、FlutterはそのPathのための三角形を発行します。

質問: 1, 2, 3回目でフレームが同じであると、どのように判断するのか？
良い質問です。DisplayListはイミュータブルであるため、一度記録した描画コマンドを変更する術はありません。
できることは、前回のDisplayListを破棄して、新しく記録しなおすことだけです。
よって、DisplayListはユニークなIDを持っており、これを前回描画したIDと比較するだけです。
例えば、前回DisplayList 27を描画し、DisplayList 27というデータが現れた場合、イミュータブルなので内容は同一のはずです。
また、FlutterはLayerを画面上に投影するためのMatrixも記録しています。そして、Flutterはデバイスのピクセルグリッドに合わせて完璧に描画します。なので、もしMatrixを変更した場合は同じ内容を描画したものとは見なしません。

他のCocoaのようなシステムでは、もしUIViewのMatrixを変更した場合、いつもデバイスのピクセルに沿う訳ではないので、アンチエイリアスの微妙な違いが現れてしまいます。
ここは、パフォーマンスのトレードオフです。
テクスチャから頻繁に描画すると、ピクセルパーフェクトな描画結果を得ることができません。
そして、私はこのような機能をシステムは持つべきと考えますし、確実に実現できると思いますが、今現在はピクセルパーフェクトな描画に最適化しているため、描画しなおしています。
もし、これがとても重たく調整の必要があるのであれば、パフォーマンスを得るために品質を下げるでしょう。
---ここまで---

Conclusion

このトークでは、これらの三つのレイヤについて説明をしました。

来てくれた方、ありがとうございます。（拍手）

---ここから翻訳自信なし----
質問: サイズを取得するウィジェットがあった場合、O(N^2)のレイアウトになってしまう？
正直、微妙なところです。シンプルな回答としては、NOです。一般的にはO(N^2)にはなりません。
親がConstraintsを渡したとき、子供にサイズを聞き、自分のサイズを回答する場面のことを思い出してみてください。
もし自分のサイズが子供のサイズと完全に一致していれば、すべきことは子供にサイズを確認し、これを自分の親に回答するだけです。
一般的に、もし自分の子供をShrink Wrapしたければ、特に高価ではありません。
ですが、いくつかの場合、少しだけ異なる事情があります。これだけでは解決できない問題があるのです。
良い例としては、Material DesignのPopupMenuです。PopupMenuの横幅はどのように決めるべきでしょうか？
答えとしては、メニュー内の最も長いテキストの幅を8pxで丸めたものです。口で言うのは簡単ですね。
それぞれの子供に自分のサイズでLayoutさせ、子供の最大サイズに+8pxしたものを自分のサイズにする、という処理は実際には正しくありません。
何故なら、アラビア語の場合これは成り立たないからです。
アラビア語は左から右に文字を書かず、右から左に向かって書きます。よって、アラビア語ではメニューのテキストは全て右端にそろうべきです。
これは、子供をレイアウトするときに、実際どのぐらいメニューが大きくなるのかを子供に伝えなければいけません。
どのようにメニューのサイズを知るのでしょうか？これは鶏と卵の議論のようなものです。
この場合では、前のスライドに出てきましたがあまり説明をしていなかった、Intrinsic Size関数を使う必要があります。
Intrinsic Sizingは「もし自由な幅でレイアウトしたとしたら、実際、一番長いテキストがどのぐらいのサイズになる？」と聞くことです。
抽象的に言うと、「改行を可能な限りしないとしたら、どのぐらいのサイズになる？」という質問です。
これはほとんどのケースでO(N^2)の挙動をします。何故なら、この質問は再帰的に木構造を下っていき、同様のことを最下層のTextに対しても行うためです。
このようなケースはとてもレアです。例えば、Stocksアプリという様々な考え得るウィジェットを詰め込んだアプリでは、おおよそ二つぐらいしかこのケースがありませんでした。
正しい挙動をさせるために必要ではありますが、基本的には1-passのレイアウトで十分です。

----ここまで----

質問: Layoutに依存したbuildを持つウィジェットを作りたい場合どうする？
実は、パイプラインの説明で少し嘘をつきました。
BuildフェーズとLayoutフェーズは実は混ぜ合わせることができます。なので、Layoutの途中でBuildを行うことができます。（ただし、Buildの途中でLayoutはできません。）
なので、Layoutフェーズの内部でBuildフェーズを行うことができます。
これは実際には先ほど説明したとても重要な性質である、RenderObjectは子供について何も知らない、という法則に従っています。
例えば、別の種類のRenderObjectやRenderBoxのようなものがあり、この子供はある意味でLazyであるとしましょう。
子供をLayoutするとき、他のRenderObjectは子供について知らず、子供とやり取りすることができないため、結果としてLayout時に必要な子供を生成することができるのです。
例えば、ビューポートに入ったときに初めてウィジェットをBuildするLazy Scrollウィジェットがあったとします。この処理は、Layout中に「ビューポートを埋めるための子供がいない、もう一個Buildしよう」といった調子で行われます。
この処理は、事前に子供をVisitする必要はないですし、一度Visitしてしまえば再びVisitする必要もありません。他のLayoutの影響を受けることがないため、これ以上の情報を取得することなく子供を生成する処理を行うことができます。
これにより、とてもクリーンな無限スクロールのメカニズムを実現できます。
これについてより詳しく説明したいですが…少し長くなるためここまでにしたいと思います。
本当に理解するためには、もっと深く説明する必要があります。

…ありがとうございました。（拍手）