Incremental - 増分計算のためのライブラリ

 (github.com/janestreet)
1 ポイント 投稿者 GN⁺ 4 시간 전 | 1件のコメント | WhatsAppで共有
  • Incrementalは、入力が変化したときに複雑な計算を効率的に更新できるよう支援するライブラリ
  • Umut Acar らの 自己調整計算（self-adjusting computation） の研究に着想を得ている
  • スプレッドシートのような大規模計算がデータ変更に効率的に反応するよう構成できる
  • GUI アプリケーションのビューに新しいデータを効率的に反映できる
  • フィルタリングやマッピングの逆変換のような 派生データ が元データと継続的に同期されることを保証できる

活用分野

  • 変化する入力に対応して 複雑な計算 を効率的に更新する
  • スプレッドシート形式の大規模計算がデータ変化に反応するよう構成できる
  • GUI ビューに新しいデータを効率的に統合できる
  • 元データから計算された派生データを継続的に同期する
    • データのフィルタリング
    • マッピングの逆変換

設計背景とドキュメント

関連記事

1件のコメント

 
GN⁺ 4 시간 전
Hacker Newsのコメント

  • この種のリアクティブプログラミングは、最近の JavaScript UI フレームワークでは signals という名前で広く使われており、標準化提案も進んでいる。
    Vue、SolidJS、Svelte、Ember、Angular が採用しており、React には MobX や Jotai のような実装がある。変更伝播と有向非巡回グラフ（DAG）の評価アルゴリズムにもさまざまな種類があり、SolidJS 2 は Incremental に似た高さベースのアルゴリズムを使っていると理解している。
    私はノードを Int32Array アリーナに割り当て、連結リストでつなぐことで、依存エッジ数に比例する GC 負荷を避ける実装を試している。
    Rust にも複数の実装があり、UI フレームワークとしては Leptos、rust-analyzer が使う汎用の増分計算システムとしては Salsa がある。これを依存関係を自動追跡するビルドシステムと見ることもでき、tup はビルド作業を計測してどのファイルを読んだかを検出し、依存関係を設定する。著者の記事と古典的な Build Systems à la Carte も読む価値がある。

    • すばやく空にできる軽量な 依存グラフ を作れる。signals がどう変わったかまで記述する必要はなく、変わった可能性があることだけを示し、変更時に依存先を空にして新しいデータを要求するときに再登録すればよい。この過程では、もう関心のない変更の通知を一部の購読者が受け取ることはありうる。
      ただし 増分計算と関数型リアクティブプログラミング（FRP） は実際には別の領域だ。増分計算はデルタ上で動作する関数を明示的に導出するが、FRP は壊れた部分を見つけて修復する方式だけを使うこともある。
    • もう 1 つの主要な例として JetBrains Noria がある。Noria の中核は UI フレームワークではなく 増分計算プラットフォーム だが、現在は JetBrains Air IDE の GUI レンダリング最適化に活用されている。
    • 複雑なオブジェクトの更新処理 にはかなりの違いがあるようで、スケジューリングも異なる可能性が高い。

  • Incremental ライブラリは、元データが変わったときに計算グラフを 部分的に再具体化 する問題を解決しようとしているようだ。よく設計されたビルドシステムに似ており、関数型プログラミングでもよく使われる有用なアプローチだ。
    増分計算の分野には Differential Dataflow、隣接技術である Timely Dataflow、DBSP もある。Feldera は DBSP ベースで、Materialize は Differential Dataflow の関係者が率いている。
    私は金融データとワークロードに特化した別アプローチである modolap を開発している。解くべき大きく重要な問題がたくさんある。関連して、Signals and Threads のビルドシステム回も参考になる。

    • modolap の主要ボタンを押すと、何の説明もなく 2,000ドルの Stripe 決済 に進むのはかなり大胆だ。
    • openivm は広範な集計演算を増分演算として実装した SQL-to-SQL コンパイラ であり、具体化ビューを自動維持する DuckDB 拡張も提供している。

  • Goldman も約 30 年前に金融商品の価格算定で同じアプローチを使っていた。そこで約 13 年働くあいだ、Node Purpling に関する長い議論を覚えている。
    コンピュータサイエンスは進歩しており、私の見る限りこれはグラフアプローチではないが、微分のような計算は高コストなので、実行回数を理論的最小値にできるだけ近づける必要がある。関連する HN 議論 もある。

    • これにより非公式に bank python と呼ばれる環境が生まれ、この記事 がうまく扱っている。
      専用の社内 IDE を見た瞬間に腹を立てて辞めないとしても、新人が適応するのに異様に時間がかかり、数か月たっても根本的に異なる要素を学び続けなければならないというくだりが、この問題を最もよく表している。私も作業内容を完全に理解するまで約 2 年半かかった。
      再教育が必要だと気づくまでは、現代的な教育もほとんどなかった。最悪だったのは UI を作るためのコーディングで、新規プロジェクトでは使用が承認されなかった。

  • お気に入りの技術講演の 1 つは Seven Implementations of Incremental だ: https://www.janestreet.com/tech-talks/seven-implementations-of-incremental/

  • 数年前、データフロープログラミング に強い関心があり、多くの人がさまざまな方向からこの問題に取り組んでいたように思う。このライブラリを見ると、すぐに Clojure の Javelin を思い出した。

  • 興味があるなら、Incremental の上に構築された UI ライブラリ Bonsai も見る価値がある。
    React のようなライブラリは仮想 DOM によって不要な作業を効率よく省くが、仮想 DOM 自体を作るのにも時間がかかる。Bonsai は 仮想 DOM まで増分化 しており、触っていて面白い。
    私は現在は保守されていない Revery 向けにデスクトップ UI ライブラリを作ったが、かなり古い Bonsai バージョンを使っている。

  • これが、入力に新しい値を発行し、計算を経て新しい結果を購読者に渡すオブザーバブル・パターンとどう違うのか、完全には理解できていない。
    変更検知や、値がそのままのときに伝播を止める最適化はあるのだろうが、それはオブザーバブルでも可能だ。stabilizeで再計算前に変更を一括処理する部分も興味深いが、やはりオブザーバブルで実装できそうだ。
    核心的な違いが、内部的な探索によって計算グラフを自動構築する点にあるのか、それとももっと根本的な要素があるのか気になる。

    • オブザーバブル・パターンをどう定義するかによる。ここでの根本的な要素は、遅延評価とグラフノード間の弱い結合だ。ノードの値は観測されたときにだけ具体化され、実行中のグラフ構造変更にも柔軟に対応する。
      一部のノードだけを観測する場合、グラフ全体を具体化する必要はない。計算はいつでも中断して、グラフを部分的にだけ更新された状態のままにし、入力をさらに変更したあとで、関心のあるノードの具体化を続けることもでき、アルゴリズムがすべての変更を整理してくれる。
      増分計算は本質的にこうした特性を含む総称であり、同じシステムを観測者と購読者のモデルとして構成することもできる。古典的な Excel スプレッドシートがよい例で、Salsa アルゴリズムの説明も参考になる。
    • 大まかに言えば、オブザーバブルは対象を購読して値を受け取る方式で、Incremental は計算と状態の DAG 全体にわたるキャッシュに近い。必要な部分だけを再計算して最適化できる。
      Ron Minsky の発表はとても良い。
    • この記事は、増分・ストリーミングシステムの地図を把握するのに役立つ。
    • 私も似たように感じた。最初に見ると、依存関係追跡を備えたリアクティブプログラミングにかなり近く見える。本当の利点がAPI の使いやすさなのか、あるいは一般的なオブザーバブル実装では現実的に難しい内部最適化なのかが気になる。
    • 根本的にはグラフの話だが、巨大で動的に変化するグラフにおいて、変更を正確かつ効率的に計算する方法だ。
      数百個の中間ノードに分岐し、長さの異なる経路を通って再び合流するダイヤモンド型のサブグラフを考えてみるとよい。一部の経路に min(A, B) があり、最大値側だけが変わるような場合もある。
      単純なオブザーバ方式では、計算量が潜在的に指数的に爆発し、並行性の問題も引き起こしかねない。このライブラリは、グラフ構造を動的に変更しても最適に近く、しかも正確だ。オブザーバなどでも同じ結果は出せるが、性能の崖を避けつつ正しく実装するのははるかに難しい。

  • Jane Street のプロジェクトの長所は、研究用途やニッチなシステムにあった発想を、開発者が実際に使える形にパッケージ化する点にある。ライブラリを導入しなくても、設計文書はたいてい読む価値がある。

  • Electric Clojure は、クライアント・サーバー境界をまたぐ増分レンダリングを提供する。最も近いのは SolidJS だと思うが、SolidJS はフロントエンドに限られる。

  • 以前、似たようなものを作ったことがあるが、先例をほとんど見つけられなかった。用途がなくなってプロジェクトは終了したが、また見直してみたいと思っており、npm に data-rambler という名前で残っている。
    構想としては、JavaScript ランタイムにロードできる**ドメイン特化言語（DSL）**にデータストリームを供給する方式だった。モジュールがデータを複数の出力ストリームに変換し、それを別のレポートライブラリに渡して、テンプレートベースの動的レポートを生成する。
    最初のバージョンからかなり強力だったが、複雑さを減らすために JavaScript らしい文法へ改善する大きな計画もあった。