BPS 開發分享之 16：變化傳播

本系列的上一篇文章當中，我用了不少篇幅在靠北別人的程式庫；平衡起見，我這篇打算反過來靠北一下自己過去的一大心血結晶，即我自己花了一年多的時間所開發的 Shrewd 框架。那曾經是我對 BPS 感到很自豪的一部分，但是隨著新版本的開發，我最終做出了放棄該框架的決定，並且大概未來也不會再採用類似的做法來解決變化傳播的課題。本篇中我分享一下其始末。

動機

變化傳播（change propagation）是各種複雜的系統中都會遇到的課題，所以如果搜尋這個關鍵字，會找到很多跟我們這邊要討論的沒有直接關聯的東西，但總之，在軟體架構當中，所謂的變化傳播講的就是當系統中的某些資料發生變化的時候、其它跟它有關的資料要怎麼樣一起連動發生變化的課題。

以排序為例來說明好了：假設我們的程式做的事情就是把一個任意輸入的陣列加以排序，這當然有著各式各樣的演算法。而今天如果輸入的陣列裡面有一個數值變動了，排序出來的結果當然有可能不一樣，但是我們有需要把排序演算法（耗時為 O(n \log n)）整個重新跑一次嗎？其實是不用的，如果變動的數值只有一個，我們在前一次排序過的結果中找出該元素對應的位置、然後往前（或往後）逐一比較並且交換元素、直到新的值被安插到正確的位置上，這樣也只需要 O(n) 的耗時就完成了 ¹。

所以變化傳播的第一個要點就是：如果只有部份的相依資料變動時，能否用比起「整個重新計算」要快的方式去更新對應的結果。不過如果光只是這樣，那也只是在講動態演算法（dynamic algorithm ²）而已。相較於排序的例子中只有兩個資料（輸入的陣列與排序後的陣列）相依，變化傳播的課題中更大的學問在於，如果系統當中有著無數個資料彼此構成複雜的相依關係時，要怎麼樣把一個資料的變化（通常是由使用者的操作所引起）導致的連鎖反應有效地傳播到整個系統之中？

BPS 是一個輔助設計摺紙的應用程式，而它的核心演算法就牽涉到無數個這樣的相依資料。從最底層的樹狀結構與角片位置，它後面需要根據這些來決定出角片重疊狀態、進而分組並決定出伸展模式、然後再去算出所有河道的輪廓乃至反應在畫面上，這每一個環節都牽涉到許多層的資料連動。管理這些資料是怎麼連動的、從 BPS 最一開始開發的時候就是一個大難題。

單純解法：立即更新

一種最單純的想法就是任何資料一改變，就立刻往後逐一更新所有的下游相依資料。例如，假設樹狀結構的中的任何一條邊長發生了改變，我們在那個 length 屬性的 setter 當中除了理所當然地更新私有的 _length 欄位之外，同時也跟著去呼叫後續的變動，例如遞迴地往下更新子樹當中所有節點的 _dist 欄位（距離樹根點的距離）、並且也遞迴地往上更新父點等等的 AABB，然後這些更新又繼續立即觸發後續的更新……換句話說，任何一個更新的發生，都會立刻同步地把所有下游變化一口氣傳播完畢。

可是，我們馬上就會意識到、這樣的架構很容易做了不必要的重工。如果使用者一口氣改變了兩條以上的邊長呢？那麼第一條邊的 length 的 setter 被執行時就會往下游全部跑一輪，而第二條邊的 setter 又再度跑了一輪，這會重複做了很多其實可以一起做的工作。比較好的作法應該是不要急著馬上更新、而等到某個資料相依的對象全部都更新完成了之後，它自己再來一次更新就好。

這種重工的問題就算最底層只有一個資料發生變化，若不夠小心的話也很難避免。舉例來說，想像我們有如下的相依關係：

flowchart TB
A --> D
A & B --> C --> D

如果今天使用者觸發了 B 的更新，那麼它就會去更新 C、而 C 又會繼續去更新 D，這倒沒什麼問題，但是如果使用者觸發了 A 的更新，那麼依照上面這張圖，A 就會立刻去更新 C 和 D、而其中 C 又會再去更新 D 一次，結果變成了 D 就被更新了兩次，造成重工。以這個例子來說，我們就必須要知道其實 A 更新的時候不需要立刻去更新 D、留著給 C 去更新就好，自己唯一要做的就是更新 C 而已，也就是變成這樣 ³：

flowchart TB
A & B --> C --> D

可是這樣一來就變得有點不好維護了，因為就 D 的內部運算邏輯看來，它的確是 A 跟 C 的資料都有參考到沒錯，那我又怎麼知道 A 不應該立刻更新 D？這對於複雜度較小的系統還算容易盤點出來，但是如果系統中有成千上萬的相依資料呢？

更糟糕的是，在這之前，甚至連「A 更新之後要去記得更新 C」這件事都是不容易維護的，因為「C 相依於 A」的這件事是寫在 C 的內部邏輯當中，我們去看 A 的程式碼的時候是絲毫看不出來有誰相依在它的身上的！當系統隨著開發而變得越來越複雜的時候，我們怎麼能夠有效保證當相依的資料發生更新的時候、自身一定會跟著被更新？這在立即更新式的架構中，是很難在實務上有效落實的。

反應式程式設計與 Shrewd

為了解決這個問題，受到了 Excel 的運算方式以及 Vue 這類反應式框架的啟發，我了解到了反應式程式設計（reactive programming）就是一個可行的解答。關於何謂反應式程式設計，網路上很多的定義都不盡相同，但是在我自己的觀點中，它最重要的精神在於：我們只需要定義資料之間的相依關係就好，剩下的事情底層自己會幫我們優化一切變化傳播的細節（主要是透過物件導向當中的觀察者模式）。

換句話說，在剛才的例子之中，我們只需要宣告「C 相依於 AB」、「D 相依於 AC」這樣的關係，剩下的事情（尤其是正確決定更新的順序以避免重工）都自然會有底層的機制幫我們決定出來。這樣的一種宣告式（declarative）的寫法的好處在於，我可以專注於去開發整個系統的邏輯本身（亦即每一個箭頭內部的邏輯）、而不用花一堆心力去煩惱變化傳播的事情。

在我剛開始開發 BPS 的那個時候，其實已經有了很多反應式的程式庫和框架存在，但是我試了一下都不是很滿意。有些對 TypeScript 的支援度差強人意，有些對物件導向的支援不夠好，有些沒辦法完全避免反應式程式設計的一些常見的毛病像是循環相依等等，又有些沒有完全地把做到更新路徑的最佳化（如果一條更新路徑途中有某個資料算出來的結果跟上一回合中一樣，那就不用繼續觸發後續的更新了，諸如此類）⁴。

所以我就決定自己來寫一個特別強調這些環節的反應式框架，其結果就是 Shrewd。我花了很多功夫發展出一套機制可以完全地確保所有的更新路徑都是以正確的順序在執行、會免去掉一切的重工、支援動態更新相依性（因為參與計算的物件可能會有所增減）、並且能自動偵測出循環相依（這在 BPS 開發的初期很容易不小心發生）。Shrewd 也是完全宣告式的，例如它只要這樣寫：

@shrewd class MyClass {
    @shrewd public A: number;
    @shrewd public B: number;

    @shrewd public get C() {
        return this.A * this.B;
    }

    @shrewd public get D() {
        return this.A % 2 + this.C;
    }
}

就能夠表達出前述例子中的那種相依關係，使得 C 和 D 會在 A 或 B 變化時自動以正確的順序更新。除此之外它也做了很多其它的優化，例如如果它發現 D 的計算結果暫時沒有人「在看」，那通往 D 的更新路徑都會自動停用以省下工作量。換句話說，Shrewd 用盡了一切方法來確保整個系統只做了必要的更新計算，絕對不會多做任何事情。

成功開發出了這樣的框架之後，確實在很長的一段時間中、它真的讓 BPS 的邏輯開發變得非常地輕鬆容易，但是在那之後又過了兩年多，反應式程式設計的各種缺點陸陸續續地就浮現了出來：

它有著太多的 overhead

跟大部分的反應式框架一樣，Shrewd 也是在執行階段才去盤點資料之間的相依關係的（透過的方法是去側錄程式碼的執行）。這導致了每一個資料在進行更新的時候、除了像上面那段程式碼本身顯示出來的計算量之外，還多了很多額外的開銷：

1. 在更新之前，必須去檢查、確定所有已知的相依資料都已經被更新到了最新狀態，而如果沒有的話，必須先插件去更新它們。
2. 在更新的過程當中，因為 Shrewd 允許動態更新相依性，於是相依關係的側錄都必須重新進行、以確保相依關係正確無誤。
3. 更新完成之後，還要額外檢查看看是否結果跟前一回合中一樣（這對於某些資料型態、例如集合來說是頗花時間的），以決定是否要繼續往下游傳播。

而就結果來說，這些額外開銷很多時候反而可能遠遠超過了更新本身的計算量，這麼一來反而不划算、傻傻地重工還反而更快。這反映了一則在討論動態演算法的時候也會遇到的現象：硬是去檢查演算法的每一個步驟是否真的有更新發生、有的時候還不如乾脆全部重算來得快，所以動態演算法的設計必須要小心地在兩者之間找到最佳的平衡點。然而 Shrewd（儘管它的意思是「精明」）卻不可能自己聰明到能優化到這種地步。

完全不容許循環相依也有其不便

循環相依是指例如 A → B → C → A 這樣的狀況；在變化傳播的課題上，循環相依通常是有問題的，因為那意味著如果 A 更新了，後面會依序對 B 和 C 進行更新、而 C 更新完了以後又會反過來變動 A 的值，然後再次觸發 B 和 C 的更新……如此反覆，最糟的情況可能陷入無窮循環。就算沒有無窮循環（例如更新個幾次之後總是會因為值不再繼續變動而停止），循環相依的出現很多時候也意味著整個系統的設計上是有欠考慮的。

因此，Shrewd 是刻意設計成完全不允許循環相依發生的。除了它提供的 API 本身就減少了循環相依的可能之外，一旦它偵測到循環相依，它就會馬上中止反應關係、杜絕無窮迴圈的可能。

但凡事有原則總有例外，循環相依並不見得總是有害的。以 BPS 為例，它在對樹狀結構進行平衡的時候，會根據各個節點的高度來決定是否要選取新的根點，而選取了新根點之後，舊的根點的高度也會跟著再次更新，所以就某種意義上來說，「樹的根點」跟「各個節點的高度」這兩個資訊之間是存在循環相依的，但是這是無害的循環相依，因為這邊的交互更新總是會停止的（到樹平衡了之後就會停止）。然而，完全不允許循環相依的 Shrewd 框架就沒有一個好的方式可以表示出這樣的一種刻意循環的關係，變得我又必須在框架之外開啟例外，不但麻煩也不利於未來維護。

無法有效預測程式被執行的順序

雖然 Shrewd 保證會以「絕對不重工」的順序去執行各項資料的更新，但是除此之外我們並沒有辦法知道更多關於它到底會以什麼順序來執行的細節。特別是，對於同一個類型的物件的某一個特定計算屬性來說，並沒有辦法保證這些計算屬性的更新都會接續著被執行——Shrewd 有可能中途會插播很多別的計算，然後才繼續執行剩下的物件的計算屬性之更新。

如此一來，我就很難進行分段計時來診斷效能瓶頸之所在；如果整個系統執行得不夠快，我根本無法知道到底是慢在哪裡，頂多根據 devtools 裡面的 sampling 來猜可能是哪邊不夠快，但是這樣的診斷方式也有其極限。

也因為執行的順序無法預測，有些時候會因此出現一些非常匪夷所思的 bug ⁵，且偵錯上又再度因為同樣的原因而非常之困難：無論是下中斷點還是 log 都很難有效掌握程式的運作脈絡，而逐步執行或檢視執行堆疊又因為框架的 overhead 太多而不切實際。

難以支援非同步的程式碼

在 JavaScript 當中，非同步的程式碼沒有一個簡單的方法可以得知執行的上下文，這使得我們要在非同步程式碼當中要暗中側錄相依性是不可能的；如果要支援非同步程式碼，我就必須很小心地把相依性在同步的部分建立完畢、然後才進入非同步的部分。但如此一來就很難避免人為錯誤了。

值得注意的是，並非所有的反應式框架都有這個罩門；有些框架是更加明確地把相依性直接宣告出來、而不使用側錄機制，這樣的框架就很容易支援非同步程式碼。但是像 Shrewd 這種主打語法糖的框架就沒辦法了。

反應式程式設計容易阻礙演算法思考

跟上面的種種缺點比起來，這或許才是真正最大的問題所在。

反應式程式設計開發起來非常容易，因為它能讓我們把複雜的系統分解成細小的單元、並且讓我們在同一時間當中只需要專注於單元到單元之間的邏輯關係，而這通常是很簡單的。然而，雖然這樣的特性使得它能夠讓開發者很快速地完成複雜的系統，但卻因為太過於方便，很容易使我們沒有花足夠的心思、來從演算法的角度思考課題。

確實，演算法當中也有所謂分而治之的概念，亦即有的時候把大問題拆解成較小的單元去處理是可以更有效率的，但或許更多的時候，把問題整體一起考慮才能想得出真正最有效率的演算法。

在開發新版 BPS 的過程中，或許最讓我印象深刻的例子就是角片之間的碰撞測試；跟通常二維空間中的物件碰撞測試不同地，角片的碰撞測試還要額外考慮到它們的對應節點在樹狀結構上的距離，而要快速求出樹狀結構上兩點之間的距離倒也不是個簡單的問題。在之前的 BPS 當中，這個問題是透過維護「任兩個節點的 LCA（least common ancestor）」這項資訊來做到的。也就是說，我先把碰撞問題化簡成距離問題，再把距離問題化簡成 LCA 的問題。至於 LCA 的問題，在文獻當中是有著很多高明的演算法沒錯、但是那些演算法的實作都相當複雜，於是因為樹狀結構的異動相對地不頻繁、且實務上我會遇到的樹也不會太大，所以我在這邊可以允許用比較慢的方法來解決、然後再用較大的記憶體消耗去快取結果就好。然而，在我捨棄掉反應式的想法之後，我發現其實如果所有角片之間的碰撞問題全部一起用遞迴的方式處理的話，LCA 可以直接在這個遞迴的過程中自動得到，亦即我既不需要刻意去計算它、也根本不用快取其結果，這是之前始料未及的。反應式的設計思維因為太過於著重「拆解」，反而會讓我沒辦法發現有這樣的一種解法。

新解法：分層式更新

所以基於上述種種原因，在 BPS 發展了兩年之後，Shrewd 本身就變成了最大的效能瓶頸之一，終於我最後決定完全不再用它。取而代之的，是我稱之為「分層式更新」的作法。這種作法的核心精神在於把整個變化傳播的過程劃分成若干個大層次（其總數不會超過數十個），然後手動以圖表的方式盤點它們之間的相依關係，再用類似反應式的排程機制去依序執行它們（但是因為層次的總數很少、而且相依關係明確且固定，這邊不需要採用反應式框架，直接寫即可）；至於各個層次的內部，則是用演算法的思維去針對層次的課題去發展最佳化的解法。層次跟層次之間的資料傳遞，則會透過一個共用的 data store 來紀錄一些發生變化的關鍵性物件，以便下一個層次可以根據前一個層次中的局部變化來優化它的運算。

以 BPS 為例，它的相依關係圖表經過若干次的簡化之後，最終有了這樣的面貌：

flowchart TB
subgraph User input
    direction LR
    T{{Tree\nstructure}}
    L{{Edge\nlengths}}
    F{{Flap positions\nand sizes}}
    P{{Stretch pattern\nchoices}}
end
subgraph Tree
    h([node heights])
    b(tree balancing)
    d([structure])
    a([AABB hierarchy])
end
j(junctions)
i[[invalid\njunctions]]
subgraph Pattern
    s(stretches)
    p([patterns])
    rc(rough contours)
    pc(pattern contours)
    g[[graphics]]
end

T --> h --> b
b & L --> d
d & F --> a --> j --> i & s
rc --> pc --> g
s & P --> p --> rc

這個圖表最上面的群組中顯示著四種使用者可能進行的操作，各自會引發不同程度的後續反應。下面的每一個節點都代表著一個運算層次，而它們會各自把運算結果中有發生變化的部份記錄在 data store 當中（大多是利用 Set 資料結構來記錄，並且會在每一回合開始的時候清空）、讓下一個層次可以根據那些來決定自己要怎麼處理。

再來一個很大的重點是程式碼的組織方式。在這種架構之下，絕大多數的物件都只會是純粹的資料類別、其中的欄位都是公開的，而幾乎不會包含任何跟更新有關的邏輯的程式碼。每一個層次的更新邏輯則都是集中寫在同一個檔案當中，而這些邏輯會去讀寫那些物件的公開欄位以完成變化傳播。

OK，聽起來很合理，可是這種架構是怎麼幫助我們解決之前遇到的各種困難的呢？

首先關於重工的部份，由於層次之間的執行順序決定機制跟反應式是類似的，也不會發生層次重新被執行的問題。至於層次的內部，因為是用演算法的方式整體一起更新同一類型的資料（即同一個資料類別的同一個欄位），所以除非演算法有問題，不然也不會發生重工。而因為單一層次的演算法全部都是寫在同一個地方，我們很容易去了解演算法的全貌並且釐清是否有這樣的問題存在。

再來，由於層次之間的相依性是我們手動盤點並且寫死的，這邊絕對不會有循環相依、或是執行順序難以預測的程式碼。而層次內部的演算法因為根本不是反應式的程式碼，所以也不用擔心這個問題，甚至我們還可以視情況來自由地採用一些其實無害的循環相依，如同前面所述。

然後，由於各個層次會一口氣處理完同一類型的資料更新，要針對各個層次進行分段計時來進行效能診斷也很容易。此外，這個架構除了完全免去了反應式架構的各種 overhead，還可以在層次內部把演算法優化到極致，所以效能上遠超過過去的任何一種作法。而因為這不是反應式架構、不需要進行任何側錄，當然支援非同步程式碼方面是沒問題的（雖然最後我自己並沒有用到就是了，因為整個系統已經跑得完全夠快了）。

不過，要採用這種作法有一個很大的前提，就是我們必須要已經對於整個系統要做的事情有一個完整透徹的了解，這樣我們才有辦法手動盤點出上面的那張層次相依圖表出來。這個前提在軟體開發的初期是不容易滿足的，大概都要等到開發到了一定的程度、對於整個系統的需求夠了解了之後才能來引入這種架構。

除此之外，分層式架構對物件導向並不友善，因為它打從規格開始就指定了大量的實作細節，這使得物件沒有辦法被抽象化、且又因為那些細節必須被暴露出來，使得我們沒有辦法對這些物件做到封裝。

最後，分層更新雖然整體效率高，但那也意味著物件的欄位值直到其層次被更新之前可能會暫時處於錯誤的狀態，此時我必須要很小心地確定欄位值的讀取都只能發生在正確的時間點上。（相較之下，反應式架構則比較沒有這個問題，因為讀取一個尚未更新的反應欄位將會觸發它的更新；但如果是讀取普通的欄位則也有同樣的顧慮。）

結語

其實我一直很好奇本篇當中討論的主題、到底在學術上有沒有一個比較專門的討論，但是多年下來我就是沒有找到那樣的資料，所以本篇中的心得都是我這幾年開發 BPS 下來自己累積出來的，希望會對遇到類似難題的人會有幫助。

另外，在發展分層次架構的時候，一個絕對功不可沒的功臣就是 Mermaid，上面的圖片就是用它畫出來的；Mermaid 可以讓人極快地以文字方式描述一個圖表、然後它會自動幫我們排版好，這比起用任何繪圖軟體來畫都還要來得快速，使得當時我可以非常快速地迭代好幾輪候選的架構、並且用圖來激發我自己的演算法思考。Mermaid 語法現在 GitHub、VS Code 等等環境的 Markdown 當中都有支援（VS Code 需要搭配延伸模組），非常方便。