Jane Street Incremental: 增量計算函式庫

Incremental 透過追蹤計算圖中的依賴關係來最小化重新計算

Jane Street 的 Incremental 是一個旨在解決當來源數據發生變動時，如何部分更新（partially hydrating）計算圖問題的函式庫。當輸入發生變化時，Incremental 並非重新執行整個計算流程，而是追蹤計算之間的依賴關係，並且僅更新受變動影響的特定節點。這種方法將計算開銷降低到理論最小值，使其在處理複雜且相互依賴的數據轉換時非常高效。

核心概念與實作

Incremental 的運作方式如同計算的建置系統，將數據輸入與輸出之間的關係視為有向無環圖（Directed Acyclic Graph, DAG）。

依賴追蹤與傳播

• 自動建構圖形：該函式庫透過在執行期間內省（introspecting）依賴關係來自動建構計算圖。
• 變動傳播：當來源值更新時，函式庫會將該變動傳播至整個圖形。此模式的一些實作版本會使用基於高度（height-based）的演算法來決定評估順序，以避免冗餘的更新。
• 批次處理：stabilize 指令允許開發者將多個變動打包在一起，確保計算圖僅在完成一組更新後重新評估一次。

與 Observable 模式的比較

雖然與 Observable 模式（輸入向監聽器發布值）相似，但 Incremental 的重點在於優化變動檢測並最小化節點重新計算的次數。它避免了傳統推播式（push-based）系統的陷阱，因為它能確保如果計算出的值在輸入變動後仍保持不變，則傳播會停止。

行業應用與生態系統

增量計算是一種基礎模式，廣泛應用於從金融建模到現代使用者介面等各種領域。

金融工作負載與高效能計算

增量計算在金融領域有著悠久的歷史。例如，Goldman Sachs 等公司的金融工具定價系統在數十年前就利用了類似的基於圖形的處理方式，以最小化昂貴的微分計算。現代的迭代版本包括 Differential Dataflow、Timely Dataflow 以及 DBSP（由 Feldera 使用），這些系統都針對大規模金融數據工作負載進行了優化。

UI 框架與「Signals"

在 JavaScript 生態系統中，此模式目前以「Signals」之名廣為流傳。Vue, SolidJS, Svelte, Ember, 和 Angular 等框架使用 Signals 來實現細粒度的響應性（reactivity）。

• SolidJS 特別利用了與 Incremental 類似的、基於高度的 DAG 評估演算法。
• Bonsai 是由 Jane Street 開發的 UI 函式庫，它直接建立在 Incremental 之上。它透過讓 VDOM 本身具備增量特性，改進了（React 使用的）Virtual DOM 方法，從而減少了建構樹狀結構所需的時間。

編譯器與建置系統

增量計算是現代建置系統與編譯器的核心。例如，Salsa 是 rust-analyzer 中使用的增量計算框架，用以確保 IDE 僅重新分析發生變動的程式碼部分。

技術權衡與考量

語言選擇：OCaml

Incremental 是以 OCaml 編寫的，提供了強大的型別系統保證，確保在複雜的依賴圖中保持正確性。雖然有人質疑 OCaml 與 C++ 相比的效能，但其他人指出 OCaml 的速度通常與 Java 相當，且明顯快於解釋型語言，使其非常適合高效能計算圖的處理。

動態與靜態圖形

增量系統中的一個挑戰是處理動態性——即節點在執行期間被新增或移除（例如，UI 視窗彈出與消失）。雖然固定大小的圖形（如試算表）很直觀，但動態圖形需要更精穩密的記憶體管理與追蹤，以避免快取問題或擴展瓶頸。

其他替代方案

有些開發者建議使用 Merkle Trees (hash trees) 作為替代方案。透過為計算節點標記其依賴關係的雜湊值（hash）與鹽值（salt），系統可以僅透過比較雜湊值來判別是否需要重新計算，並使用 ID 來索引快取中的結果。