基于Flutter動態(tài)化的作用域管理研究

劉桐 劉剛 郭發(fā)玉 孫曉棟 袁偉

（1.數(shù)字化家電國家重點實驗室 山東省青島市 266103 2.青島海爾科技有限公司 山東省青島市 266103）

（3.海爾優(yōu)家智能科技（北京）有限公司 陜西省西安市 710000）

隨著互聯(lián)網(wǎng)行業(yè)的飛速發(fā)展和用戶基數(shù)的不斷擴充，高速化的迭代需求日益凸顯，而傳統(tǒng)的移動終端應(yīng)用開發(fā)往往不能滿足迭代的速度性，這就促使著開發(fā)者不斷尋求一種在保障性能的情況下提升迭代速度的解決方案。鑒于此，行業(yè)內(nèi)衍生出了混合開發(fā)，但不管是 Hybrid、React Native 還是Webview 嵌套 H5，都存在一個共同的弊端：即在性能緯度上，遠遠達不到原生應(yīng)用的效果，F(xiàn)lutter 框架依靠其高性能的渲染引擎 Flutter Engine，開發(fā)出的移動應(yīng)用性能幾乎與原生應(yīng)用無差別[1]。這也是Flutter 對比混合開發(fā)的最大優(yōu)勢，但也存在很大的弊端——無法支持熱更新，這就意味著需求無法以最快的速度觸達到用戶，這也就成為了一些開發(fā)者選擇Flutter 比較顧忌的點。

為了使 Flutter 能夠具備動態(tài)化熱更新的能力，本文給出一種有效的解決方法。首先，利用 Dart 官方提供的 Analyzer分析庫，將 Dart 代碼生成為 AST[2]，然后根據(jù) AST 信息組裝生成所需要的 DSL JSON 文件，在 APP 運行時開發(fā)一套解析器來解釋和執(zhí)行DSL JSON 文件。而對于運行時的作用域管理，是決定運行時執(zhí)行效率的關(guān)鍵點。目前在計算機領(lǐng)域中作用域管理通常采用“堆?！毙问降臄?shù)據(jù)結(jié)構(gòu)，即“先進后出”的工作模式[3]。然而，這種堆棧式的數(shù)據(jù)結(jié)構(gòu)存在數(shù)據(jù)讀取效率不高的問題。例如，現(xiàn)有技術(shù)在基于無序的數(shù)據(jù)索引情況下，使用傳統(tǒng)堆棧時查找的時間復(fù)雜度是O(n)，插入的時間復(fù)雜度是O(1)，其中查找相比于插入效率就會低很多，這對于軟件層面上的執(zhí)行來說效率是低下的，尤其對于涉及到需要快速讀取和頻繁讀取的工作中。

針對傳統(tǒng)的作用域管理存在的問題，本文提出了一種新的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)運行時作用域管理。該數(shù)據(jù)結(jié)構(gòu)包括了哈希表與雙向鏈表兩部分[4]：雙向鏈表包括若干用于存儲函數(shù)唯一哈希值以及函數(shù)作用域的鍵值結(jié)點，哈希表包括了若干用于存儲函數(shù)唯一哈希值以及鏈表結(jié)點的鏈接結(jié)點；各個鍵值結(jié)點之間均為雙向連接，且每個鏈接結(jié)點保存了對應(yīng)的鍵值結(jié)點的引用?；谏⒘泻瘮?shù)計算key 鍵值對應(yīng)的哈希碼，讀取哈希碼對應(yīng)的鏈接結(jié)點。通過將哈希表與雙向鏈表的結(jié)合，從而簡化了邏輯，相對于堆棧來說，上述技術(shù)可以將查找的時間復(fù)雜度從線性時間O(n)降低至常數(shù)時間O(1)。線性時間復(fù)雜度，表示算法的運行時間隨著輸入數(shù)據(jù)的規(guī)模線性增長。而常數(shù)時間復(fù)雜度，不論輸入數(shù)據(jù)的規(guī)模是多少，對于運行時間來說，其對外表現(xiàn)的運行查找效率是一致的。

本文第1 節(jié)介紹本文所需的基礎(chǔ)知識，包括抽象語法樹和深度遍歷。第2 節(jié)介紹本文闡述的作用域模型。第3 節(jié)介紹了運行時的內(nèi)存釋放機制。第4 節(jié)通過對比實驗驗證了所提模型的有效性。最后總結(jié)全文。

1 基礎(chǔ)知識

本文所提方法主要基于抽象語法樹，下面就相關(guān)概念和基本知識予以介紹。

1.1 抽象語法樹

抽象語法樹（Abstract Syntax Tree，縮寫：AST）是用正式語言編寫的文本（通常是源代碼）的抽象語法結(jié)構(gòu)的樹形結(jié)構(gòu)表示。樹的每個結(jié)點表示文本中出現(xiàn)的構(gòu)造。抽象語法樹是編譯器中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，用于表示程序代碼的結(jié)構(gòu)。AST 通常是編譯器語法分析階段的結(jié)果。它通常通過編譯器所需的幾個階段作為程序的中間表示，并且對編譯器的最終輸出有很大的影響。

1.2 標(biāo)識符

標(biāo)識符（Identifier）是指用來標(biāo)識某個實體的一個符號，在不同的應(yīng)用環(huán)境下有不同的含義。在計算機編程語言中，標(biāo)識符是用戶編程時使用的名字，用于給變量、常量、函數(shù)、語句塊等命名，以建立起名稱與使用之間的關(guān)系。標(biāo)識符通常由字母和數(shù)字以及其它字符構(gòu)成。

1.3 深度遍歷

深度遍歷（Depth-Frist-Search，縮寫：DFS）是一種用于遍歷或搜索樹或圖數(shù)據(jù)結(jié)構(gòu)的算法。該算法從根結(jié)點開始（在圖的情況下選擇某個任意結(jié)點作為根結(jié)點）并在回溯之前沿著每個分支盡可能深地探索。當(dāng)結(jié)點v 的所在邊都己被探尋過，搜索將回溯到發(fā)現(xiàn)結(jié)點v 的那條邊的起始結(jié)點。這一過程一直進行到已發(fā)現(xiàn)從源結(jié)點可達的所有結(jié)點為止。如果還存在未被發(fā)現(xiàn)的結(jié)點，則選擇其中一個作為源結(jié)點并重復(fù)以上過程，整個進程反復(fù)進行直到所有結(jié)點都被訪問為止。通過深度遍歷，就可以遍歷整個圖，從結(jié)點的角度來說，通過深度遍歷，就可以遍尋到所有的結(jié)點。

1.4 統(tǒng)一資源標(biāo)識符

統(tǒng)一資源標(biāo)志符（Uniform Resource Identifier，縮寫：URI）在電腦術(shù)語中是用于標(biāo)志某一互聯(lián)網(wǎng)資源名稱的字符串。該種標(biāo)識允許用戶對任何（包括本地和互聯(lián)網(wǎng)）的資源通過特定的協(xié)議進行交互操作。

1.5 作用域

作用域（Scope）在程序設(shè)計中，是標(biāo)識符與實體的綁定保持有效的一部分計算機程序。不同的編程語言可能采用不同的作用域（靜態(tài)作用域/動態(tài)作用域）；靜態(tài)作用域又稱詞法作用域，采用詞法作用域的變量叫詞法變量。詞法變量有一個在編譯時靜態(tài)確定的作用域。相反，采用動態(tài)作用域的變量叫動態(tài)變量。只要程序正在執(zhí)行定義了動態(tài)變量的代碼段，那么在這段時間內(nèi)，該變量一直存在；代碼段執(zhí)行結(jié)束，該變量便消失。本文闡述的作用域為靜態(tài)作用域。

2 模型設(shè)計

為了解決運行時查找效率低下的問題，以及使用哈希表存儲數(shù)據(jù)時，容易產(chǎn)生哈希沖突的問題。本文闡述了一種使用哈希表替換堆棧，作為運行時作用域管理的數(shù)據(jù)結(jié)構(gòu)，以及生成唯一哈希值解決現(xiàn)有技術(shù)中哈希沖突的問題。

基于 Dart SDK 內(nèi)置的 analyzer 分析庫，解析出 dart 目標(biāo)文件，生成抽象語法樹(AST)，同時獲取抽象語法樹中所有的標(biāo)識符(identifier)結(jié)點；基于標(biāo)識符的自身信息，獲取其所聲明文件的URI。通過標(biāo)識符結(jié)點中的信息，再基于自定義Builder，能夠在編譯階段生成其種類及唯一的標(biāo)識，具體步驟如下：

（1）基于 dart 目標(biāo)文件，生成抽象語法樹；

（2）通過對抽象語法樹進行深度遍歷，找出所有標(biāo)識符結(jié)點；

（3）基于標(biāo)識符結(jié)點中的信息，得到其名稱；

（4）基于標(biāo)識符結(jié)點所聲明文件的URI，得到其全限定名；

（5）結(jié)合自定義Builder，所有的標(biāo)識符都會被賦予一個種類，比如頂級變量、全局函數(shù)、局部變量等；

（6）基于步驟（3）和步驟（4）得到的名稱和全限定名，結(jié)合自定義Builder 進行整合拼接，能夠得到一個唯一的 hashcode，此 hashcode 可以替代該標(biāo)識符存儲在作用域中；

運行時作用域模型設(shè)計，具體包括：雙向鏈表以及哈希表。其數(shù)據(jù)結(jié)構(gòu)模型如圖1所示：雙向鏈表中的結(jié)點，key存儲對應(yīng)函數(shù)的hashcode，value 存儲其對應(yīng)的函數(shù)作用域；哈希表中的結(jié)點，key 同樣存儲函數(shù)的hashcode，value 指向其對應(yīng)的雙向鏈表結(jié)點。具體實現(xiàn)思路如下：

圖1：作用域模型

（1）APP 運行時，解析器開始加載DSL JSON 文件，此時需要先構(gòu)造出全局作用域來存儲頂級變量的數(shù)據(jù)模型，在雙向鏈表中創(chuàng)建一個頭結(jié)點，此結(jié)點中key 存儲字符串字面量‘global’，value 存儲全局作用域的引用。全局作用域的存儲數(shù)據(jù)結(jié)構(gòu)為{key:value}鍵值對形式，其中key 為頂級變量的hashcode，value 存儲其具體的數(shù)據(jù)模型；

（2）解析器在加載到頂級變量時，從 DSL JSON 文件中提取出頂級變量的信息，同時開始解析其DSL JSON 信息，并生成對應(yīng)的數(shù)據(jù)模型來表示具體的頂級變量，最后將該數(shù)據(jù)模型存儲在全局作用域中；

（3）全局作用域構(gòu)造完成后，需要在哈希表中增加一個鍵值對，key 同樣存儲字符串字面量‘global’,value 指向雙向鏈表中全局作用域結(jié)點；

（4）解析器在加載到全局函數(shù)時，從DSL JSON 文件中提取出函數(shù)對應(yīng)的信息，其中函數(shù)信息包括函數(shù)對應(yīng)的標(biāo)識符名稱及全局唯一的 hashcode，基于函數(shù)信息，構(gòu)建出對應(yīng)全局函數(shù)的數(shù)據(jù)模型。同時在雙向鏈表尾部插入一個結(jié)點用于存儲該全局函數(shù)作用域，哈希表中新增一個鍵值對來指向該函數(shù)作用域。

（5）解析器在加載到全局函數(shù)調(diào)用語句時，先根據(jù)全局函數(shù)的hashcode 從哈希表中找到其對應(yīng)的作用域；

（6）解析器在加載到全局函數(shù)中的代碼塊語句時，將其中的局部變量轉(zhuǎn)化為對應(yīng)的數(shù)據(jù)模型，并存儲在其所處函數(shù)的作用域中；

（7）解析器在加載到函數(shù)內(nèi)部聲明的局部函數(shù)時，將局部函數(shù)內(nèi)聲明的局部變量轉(zhuǎn)化為對應(yīng)的數(shù)據(jù)模型，并存儲在其所處函數(shù)的作用域中；

（8）解析器在解析執(zhí)行變量查找時，首先根據(jù)該變量在編譯階段生成的種類，判斷需要從哪個作用域中進行查找。例如：變量種類為頂級變量時，則直接從全局作用域中進行查找；變量種類為局部變量時，則直接從對應(yīng)函數(shù)的作用域中進行查找。

以圖2、圖3 代碼為例，具體說明運行時中作用域的符號/變量查找流程。

圖2

圖3

（1）執(zhí)行函數(shù)調(diào)用語句test()，在哈希表中根據(jù)test 全局函數(shù)的hashcode 查找其函數(shù)作用域；

（2）在 test 函數(shù)體中，執(zhí)行語句；

（3）執(zhí)行到變量聲明語句時，將變量c 存入當(dāng)前函數(shù)作用域；

（4）runtime 在執(zhí)行到 a>b 時，需要先根據(jù)編譯階段生成的種類，判斷需要從當(dāng)前函數(shù)作用域查找還是從全局作用域中查找；

（5）發(fā)現(xiàn)變量a、變量b 均為頂級變量，則會直接在全局作用域中查找；如果為局部變量的話，則直接在當(dāng)前的函數(shù)作用域中進行查找；

（6）在全局作用域中查找到了變量a、變量b，讀取其值；

（7）執(zhí)行比較結(jié)果，發(fā)現(xiàn)a>b 結(jié)果不成立；

（8）繼續(xù)執(zhí)行 c=func() 這條賦值語句；

（9）從哈希表中，根據(jù)func 的hashcode 查找func 的函數(shù)作用域；

（10）查找到后，執(zhí)行func 函數(shù)體中語句并返回結(jié)果。

在本示例中，雙向鏈表的頭結(jié)點指向全局作用域，雙向鏈表中的頭結(jié)點存儲值為 ‘global’,global 為全局作用域的意思，這樣有利于程序的變量共享，可以簡化添加和修改的流程。在源碼的運行時，即代碼中函數(shù)語句執(zhí)行時，在創(chuàng)建一個鏈表結(jié)點之后，將函數(shù)的 hashcode 作為key、將其對應(yīng)的作用域作為value，存儲在新增的結(jié)點上，同時會將函數(shù)標(biāo)識符即 hashcode 作為 key 值、其對應(yīng)的鏈表結(jié)點引用作為 value 存入哈希表中。

在函數(shù)調(diào)用語句執(zhí)行前，首先根據(jù)函數(shù)的hashcode 在哈希表中進行查找，查找到后，哈希表中存儲的value 指向了其對應(yīng)的函數(shù)作用域。在函數(shù)內(nèi)部語句執(zhí)行的過程中，則會根據(jù)標(biāo)識符的種類分別在不同的作用域中進行查找。源碼中的函數(shù)語句執(zhí)行完成后，會將其對應(yīng)的函數(shù)作用域進行釋放。

本示例中，首先在編譯階段結(jié)合自定義Builder，生成標(biāo)識符的種類以及唯一的 hashcode，通過函數(shù)標(biāo)識符的hashcode 在雙向鏈表中增加新的鏈表結(jié)點，并且在雙向鏈表中存儲key 以及函數(shù)作用域，同時將hashcode 作為 key、其對應(yīng)的鏈表結(jié)點作為 value 存儲在哈希表中。此方法可以將傳統(tǒng)的作用域查詢效率提升到最優(yōu)（常數(shù)階：O(1)），與存儲的數(shù)據(jù)規(guī)模（n）無關(guān)。從而相對于堆棧的方式來說，降低了查詢的時間復(fù)雜度。

綜上，該模型具體涵蓋了三部分，包括：編譯階段生成標(biāo)識符種類及唯一的 hashcode，加載階段生成作用域模型，解釋運行時階段變量的查找及賦值。其中：

（1）編譯階段：基于目標(biāo) dart 源文件生成抽象語法樹。結(jié)合自定義Builder，找到抽象語法樹中所有的標(biāo)識符結(jié)點，根據(jù)標(biāo)識符的 name 信息、URI 信息，然后進行整合拼接，生成唯一的 hashcode。

（2）加載階段：解析器在加載 DSL JSON 文件時，根據(jù)在編譯階段生成的標(biāo)識符種類，遇到頂級變量聲明語句，則將其轉(zhuǎn)化為具體的數(shù)據(jù)模型存儲在全局作用域中。遇到全局函數(shù)聲明結(jié)點，則在雙向鏈表中新增一個結(jié)點，將其標(biāo)識符對應(yīng)的 hashcode 作為key，其對應(yīng)的函數(shù)作用域作為value 存儲到新增的結(jié)點中；同時將 hashcode 存儲在哈希表中作為 key 值，其對應(yīng)的鏈表結(jié)點作為 value；哈希表中存儲的結(jié)點始終指向其對應(yīng)鏈表結(jié)點。

（3）解釋運行時階段：根據(jù)標(biāo)識符的種類，如果是頂級變量，則直接在全局作用域中進行查找；如果是局部變量，則直接在當(dāng)前作用域中進行查找。如果標(biāo)識符的種類是函數(shù)，則在哈希表中根據(jù)hashcode 查找其對應(yīng)的函數(shù)作用域。

3 內(nèi)存釋放

內(nèi)存空間是所有程序的公共資源，排除已經(jīng)被占用的內(nèi)存，空閑內(nèi)存往往是散落在各個地方的。我們知道，存儲數(shù)組、棧等數(shù)據(jù)結(jié)構(gòu)需要內(nèi)存空間連續(xù)，當(dāng)我們需要申請一個很大的數(shù)組、棧時，系統(tǒng)不一定存在這么大的連續(xù)內(nèi)存空間。而鏈表則更加靈活，因為其每個結(jié)點都是通過指針相連，所以存儲鏈表時并不需要內(nèi)存地址是連續(xù)的，只要剩余內(nèi)存空間大小夠用即可。

如何將APP 的內(nèi)存開銷降低到最小，以保證APP 整體運行的穩(wěn)定性及用戶體驗，這就成為了本研究中無法避免的問題。上述方案中，能夠?qū)е聝?nèi)存增加的主要原因就是隨著程序執(zhí)行，作用域中存儲的數(shù)據(jù)會越來越多，如果不進行內(nèi)存釋放，則很有可能會導(dǎo)致APP 運行時內(nèi)存溢出崩潰，進而影響用戶的使用意愿。

本研究采取的方案為：基于上述整體設(shè)計，在函數(shù)調(diào)用語句整體執(zhí)行完后，將其對應(yīng)的函數(shù)作用域置為空，保留其在雙向鏈表中的結(jié)點及哈希表中的引用；在整個頁面退出時，將運行時持有的作用域全部釋放，包括將雙向鏈表置為空及哈希表置為空。此方案不僅能夠?qū)?nèi)存使用開銷降低至最小，還可以保證運行時作用域查找的效率。

4 性能比對

對于本研究設(shè)計方案的計算性能，我們考慮使用Nilakantha 級數(shù)來計算 Pi 的值，在該公式中，從3 開始，依次交遞加減以4 為分子、三個連續(xù)整數(shù)乘積為分母的分?jǐn)?shù)，每次迭代時三個連續(xù)整數(shù)中的最小整數(shù)是上次迭代時三個整數(shù)中的最大整數(shù)。反復(fù)計算多次，結(jié)果與 Pi 非常接近。

具體公式如下：

π=3+4 ?(2×3×4)-4 ?(4×5×6)+4 ?(6×7×8)-4 ?(8×9×10)+4 ?(10×11×12)…

具體實現(xiàn)代碼如圖4所示，使用 Dart DevTools 分析工具，分析圖4 代碼的運行結(jié)果。對于使用堆棧進行作用域管理，在進行變量查找時，其自身耗時過多。綜合平均運行時間為1.58 秒，在使用本文闡述的新數(shù)據(jù)結(jié)構(gòu)后，使用相同的測試代碼，綜合平均運行時間為486 毫秒，對比改造前的運行效率提升了69.2%。

圖4：具體實現(xiàn)代碼

對于頁面渲染幀率，使用Dart DevTools 分析工具獲取操作頁面后的平均幀率如表1 格所示，可以看到動態(tài)化頁面渲染幀率基本與AOT 頁面持平，其表現(xiàn)已接近于Flutter 原生性能。

表1：平均幀率

5 結(jié)束語

本方案闡述了一種運行時作用域管理的整體方案流程，在編譯階段結(jié)合自定義Builder，對所有標(biāo)識符賦予特定的種類以及整合后唯一的 hashcode，就可以將傳統(tǒng)的作用域管理的數(shù)據(jù)結(jié)構(gòu)—堆棧，轉(zhuǎn)化為哈希表及雙向鏈表的結(jié)合；這樣就可以將作用域查詢效率從O(n)提升至O(1)，從而達到最優(yōu)的運行時效率。本方案闡述的數(shù)據(jù)結(jié)構(gòu)，因為其自身的存儲特性，可以最大程度的利用系統(tǒng)的內(nèi)存空間