I have built something similar like this for my fund 7 years ago. We were doing parametric optimization on large computational graphs. I have never programmed Ocaml but my understanding is introspection is kind of a weak spot for the language. Curious language choice! I know Ocaml is fast, about 1-2x speed of C, on par with Java.
One thing I've never fully grokked is how this differs from an observable pattern where one can publish new values to inputs, propagate that through the computation, and push newly computed values to listeners.
I guess there's probably optimizations around change detection and stopping the propagation if there's no change (though observables can do that as well). The stabilize command also makes things interesting as a way to batch changes together before recomputing (but again, doable with observables too).
Is the delta primarily coming from introspection and automatically building the compute graph? Or is there something more fundamental that I'm missing?
Goldman took the same approach with instrument pricing ~30 years ago. I recall long discussions about "Node Purpling" in my ~13 year tenure there.
Computer Science has evolved, and AFAICT this is not a graph approach, but things like differentiation are computationally expensive, and therefore you want to minimize the number of times you do it to as close to the theoretical minimum.
One thing i have always linked about Jane street projects is that they tend to package ideas that have existed in research or niche system into something developers can actually use. Even if you never adopt the library, the design docs are usually worth reading.
In C# a dependency graph that automatically updates only the affected dependencies can be implemented using events and/or functors and/or data binding.
I do not understand what is the big deal with Increment. Is it more efficient because it is written in OCaml rather than C#?
I was very curious about Dataflow programming years ago - I think a lot of people were coming at this problem from various angles. This specific library immediately reminded me of Javelin from Clojure [0]
It’s used by frameworks Vue, SolidJS, Svelte, Ember, Angular, and there’s a few different implementations for React like Mobx and Jotai. There’s a few different algorithms for how to propagate changes and evaluate the DAG, I believe SolidJS2 uses a height-based algorithm similar to Incremental.
There are a few of these for Rust as well, Leptos is an example in UI frameworks, and Salsa is an example in general incremental computing, used in rust-analyzer.
As far as I can tell, incremental the library aims to solve the problem of partially hydrating a computation graph when source data is altered. This approach is similar to the one pursued by (well designed) build systems and is common in the FP world. [2] This has many use cases and is very cool.
In addition, in the sphere of incremental computation, there exists Differential Dataflow, Timely Dataflow (adjacent), and DBSP. Systems like Feldera are built on DBSP. Materialize is lead by some DD guys.
Personally, I am pursuing an orthogonal approach specifically for the problem of financial data and financial workloads, There exists huge, very important problems to solve! [1]
Check out https://github.com/ila/openivm which implements a very large scope of aggregations as incremental operations in an SQL-to-SQL compiler, and extension for duckdb that automatically maintains a materialized view
Usually these kinds of systems either don't scale dynamically or have caching issues. The first example, a spreadsheet, is "easy" because there are a fixed amount of cells to track. A GUI can be a lot harder (imagine sub windows and sub-sub windows dynamically popping up and tracking some redundant and some unique "computations". Entities can appear and then be removed at random). Though the wording carefully says "constructing views" so maybe it doesn't handle dynamism
Can't you solve it using hash trees (or Merkle trees) ?
You tag each computation nodes with a hash of its dependencies and some constant salt, that gives you an ID which identifies the results that the computation node would produce; before running it.
You can then use those IDs to index the computations results in a cache;
whenever you query a computation results, as long as you update the IDs of each leaf of the computation graph, you will only re-compute the nodes that need to be updated
What you're describing is akin to a basic pull-based incremental engine, akin to salsa. The base design is straightforward, but you need some additional logic to avoid following the whole execution tree when hashing. Their downsides is that sometimes you do have to follow the whole execution tree, even if nothing changed.
Push-based designs instead "push" changes to their dependants, which can be quite efficient especially in the case where the update doesn't propagate much. However it has the downside of potentially requiring to update nodes that are no longer used, or updating nodes multiple times.
Libraries like React are pretty efficient with skipping work by using Virtual Dom, but constructing this vdom still takes time. Bonsai makes the vdom incremental and it is pretty fun to work with.
I built a desktop UI library with it by targeting (now unmaintained) Revery. It is using a much older version of Bonsai however: https://github.com/ozanvos/bonsai_revery
It tends to be. While it does use a GC, it has both bytecode and native AOT compilers. When compiled to native, it's closer in performance to C++ and Rust than to C# or Java. It's a reasonable middle ground in PL design that Nim also tries to occupy. In recent years, OCaml's runtime also shed the GIL, making it a good solution for parallelizable, CPU-bound tasks. As a language, OCaml is one of the most impressive ones (in terms of features and capabilities), yet it still provides strong, practical tooling, good performance, and access to low-level-ish features.
TL;DR: OCaml is usually going to be a bit slower than C++, but faster than Java, while rivaling Rust and Haskell in terms of expressive power.
Caveat: a lot of the power comes from the tooling. Last I checked, syntax extensions were external preprocessors, just with standardized APIs. And you need those extensions for things that are handled by (in-language) macros in Rust (like deriving string representation for a record). Without the tooling, OCaml can get a bit tedious/boilerplate-y. OTOH, after a period of instability and competing solutions, the tooling mostly settled down, and enabling the important parts is often a single line in the config. It's not a situation unique to OCaml, but if you look at the language docs only, you'll miss half of what OCaml development normally offers.
39 comments
[ 3.5 ms ] story [ 48.0 ms ] threadI guess there's probably optimizations around change detection and stopping the propagation if there's no change (though observables can do that as well). The stabilize command also makes things interesting as a way to batch changes together before recomputing (but again, doable with observables too).
Is the delta primarily coming from introspection and automatically building the compute graph? Or is there something more fundamental that I'm missing?
Computer Science has evolved, and AFAICT this is not a graph approach, but things like differentiation are computationally expensive, and therefore you want to minimize the number of times you do it to as close to the theoretical minimum.
Edit: Related HN discussion https://news.ycombinator.com/item?id=36006737
I do not understand what is the big deal with Increment. Is it more efficient because it is written in OCaml rather than C#?
[0]: https://github.com/hoplon/javelin
It’s used by frameworks Vue, SolidJS, Svelte, Ember, Angular, and there’s a few different implementations for React like Mobx and Jotai. There’s a few different algorithms for how to propagate changes and evaluate the DAG, I believe SolidJS2 uses a height-based algorithm similar to Incremental.
I’ve been fooling around with an implementation that uses an Int32Array arena to allocate nodes and link them together with linked lists without paying O(dependency edges) GC load: https://github.com/justjake/dalien-signals/tree/dalien-signa...
There are a few of these for Rust as well, Leptos is an example in UI frameworks, and Salsa is an example in general incremental computing, used in rust-analyzer.
Another way to look at this sort of thing is as a build system with automatically tracked dependencies. One such build system is tup, which instruments build jobs to detect what files they read to establish dependency relationships. Interesting reading from the author: https://gittup.org/tup/build_system_rules_and_algorithms.pdf, see also the classic Build Systems à la Carte https://www.microsoft.com/en-us/research/wp-content/uploads/...
As far as I can tell, incremental the library aims to solve the problem of partially hydrating a computation graph when source data is altered. This approach is similar to the one pursued by (well designed) build systems and is common in the FP world. [2] This has many use cases and is very cool.
In addition, in the sphere of incremental computation, there exists Differential Dataflow, Timely Dataflow (adjacent), and DBSP. Systems like Feldera are built on DBSP. Materialize is lead by some DD guys.
Personally, I am pursuing an orthogonal approach specifically for the problem of financial data and financial workloads, There exists huge, very important problems to solve! [1]
[1] https://modolap.com
[2] Signals And Threads episode on the subject https://signalsandthreads.com/build-systems/
Very satisfying to use when you manage to find a problem that is suited to this type of approach.
Usually these kinds of systems either don't scale dynamically or have caching issues. The first example, a spreadsheet, is "easy" because there are a fixed amount of cells to track. A GUI can be a lot harder (imagine sub windows and sub-sub windows dynamically popping up and tracking some redundant and some unique "computations". Entities can appear and then be removed at random). Though the wording carefully says "constructing views" so maybe it doesn't handle dynamism
You tag each computation nodes with a hash of its dependencies and some constant salt, that gives you an ID which identifies the results that the computation node would produce; before running it.
You can then use those IDs to index the computations results in a cache; whenever you query a computation results, as long as you update the IDs of each leaf of the computation graph, you will only re-compute the nodes that need to be updated
Push-based designs instead "push" changes to their dependants, which can be quite efficient especially in the case where the update doesn't propagate much. However it has the downside of potentially requiring to update nodes that are no longer used, or updating nodes multiple times.
The closest thing to Electric (IMO) is SolidJS, but frontend only: https://www.solidjs.com/
https://hn.algolia.com/?q=flow+based+programming+
Libraries like React are pretty efficient with skipping work by using Virtual Dom, but constructing this vdom still takes time. Bonsai makes the vdom incremental and it is pretty fun to work with.
I built a desktop UI library with it by targeting (now unmaintained) Revery. It is using a much older version of Bonsai however: https://github.com/ozanvos/bonsai_revery
TL;DR: OCaml is usually going to be a bit slower than C++, but faster than Java, while rivaling Rust and Haskell in terms of expressive power.
Caveat: a lot of the power comes from the tooling. Last I checked, syntax extensions were external preprocessors, just with standardized APIs. And you need those extensions for things that are handled by (in-language) macros in Rust (like deriving string representation for a record). Without the tooling, OCaml can get a bit tedious/boilerplate-y. OTOH, after a period of instability and competing solutions, the tooling mostly settled down, and enabling the important parts is often a single line in the config. It's not a situation unique to OCaml, but if you look at the language docs only, you'll miss half of what OCaml development normally offers.