7 ms·
Incremental – A library for incremental computations
- Magicrafter13 3mo agoI don't understand how to use this library, as it doesn't seem to indicate what language it is for, but the concept sounds very cool.
- woggy 3mo agoOCaml
- reinitctxoffset 3mo agoKobe!
- mempko 3mo agoI 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.
- hankbond 3mo agoNot trying to be pedantic but do you mean half the speed of C?
- deleted 3mo ago[deleted]
- RandomBK 3mo agoOne 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?
- blovescoffee 3mo agoRoughly, you subscribe and listen to an observable. Incrementals are more like a cache across some DAG of computation + state that lets you optimize by only recomputing what needs to be recomputed. There's a really good talk from Ron Minsky here: https://www.janestreet.com/tech-talks/seven-implementations-of-incremental/ https://www.janestreet.com/tech-talks/seven-implementations-...
- Onavo 3mo agoMust make building backpropation algorithms really easy.
- runtime_lens 3mo ago[flagged]
- Eliah_Lakhin 3mo agoIt depends on how you define the observable pattern. The fundamental components here are laziness and weak connections between graph nodes. Node values are getting materialized only when you observe them, and the system is flexible for live structural changes. Usually, you don't need to materialize the entire graph when you need to observe just some nodes. Additionally, you can halt computations at any point in time leaving the graph in semi-actualized state, make extra changes to the inputs, and continue materialization of the nodes of interest. The algorithm will sort out all changes for you. Essentially, incremental computations is just a term covering these features. You can organize the same system in terms of observers and subscribers. Perhaps, classical Excel spreadsheets is the best illustration of the idea. Also, see my article on the topic: https://medium.com/@eliah.lakhin/salsa-algorithm-explained-c5d6df1dd291 https://medium.com/@eliah.lakhin/salsa-algorithm-explained-c...
- RandomBK 3mo agoLaziness and weak connections makes sense as differentiators. However I'm not sure Excel is such a great illustration in that case, as it's neither lazy nor weakly connected; at least at the surface.
- fadesibert 3mo agoGoldman 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. Edit: Related HN discussion https://news.ycombinator.com/item?id=36006737 https://news.ycombinator.com/item?id=36006737
- zitterbewegung 3mo agoYea and this created "bank python" informally a good article is here. https://calpaterson.com/bank-python.html https://calpaterson.com/bank-python.html The best description about how it became a problem is one of the paragraphs. "New starters take an exceptionally long time to get up to speed - and that's if they don't resign in fit of pique as soon as they see the special, mandatory, in-house IDE (as I nearly did). Even months in, new starters are still learning quite fundamental new things: there is a lot that is different." I think it took me til I was there around two and a half years to fully comprehend it when I was working on it. Not much modern training til they figured out they had to teach it again that was better. The worst part is to make an UI around it coding it and it wasn't approved for new projects.
- rwmj 3mo agoThat article was fascinating, thanks for sharing it. I wonder if all banks use the same "bank Python" or if they all forked it in different ways?
- bboreham 3mo agoSome of the same people bounced around implementing it in different places, but they started from scratch each time. Some things to search for: JP Morgan Athena BofA Quartz Kirat Singh Mark Higgins
- 27183 3mo agoWow thanks for the link. My first reaction was "that's the jankiest thing I've ever heard of" but on reflection the author is correct about it being a fairly optimally fit predator. When the benchmark is .xlsx files on a shared drive things are bound to get pretty weird.
- runtime_lens 3mo ago[flagged]
- raphinou 3mo agoI think websharper's Var are similar to this, and it is really great to develop dynamic web interfaces (in fsharp).
- dh2022 3mo agoIn 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#?
- djtango 3mo agoI 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] [0]: https://github.com/hoplon/javelin https://github.com/hoplon/javelin
- jitl 3mo agoThis style of reactive programming is quite popular in JavaScript UI frameworks these days under the moniker “signals”, with a proposal for standardization here: https://github.com/tc39/proposal-signals#-javascript-signals-standard-proposal https://github.com/tc39/proposal-signals#-javascript-signals... 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-signals#benchmarks 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 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/2018/03/build-systems-final.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/...
- edparcell 3mo ago[dead]
- avallach 3mo agoAnother notable example: JetBrains Noria ( https://blog.jetbrains.com/fleet/2023/02/fleet-below-deck-part-vi-ui-with-noria/ https://blog.jetbrains.com/fleet/2023/02/fleet-below-deck-pa... ). As the authors highlight: "Noria is not a UI framework at its core. Instead, it’s a platform for incremental computations.". But currently they happen to use it to optimize gui rendering in JetBrains Air IDE.
- tgv 3mo agoIt looks as if there is a significant difference in treating updates to complex objects, and probably scheduling as well.
- BedVibe_Studios 3mo ago[flagged]
- curtisblaine 3mo agoThis reminds me of https://github.com/electric-sql/d2ts https://github.com/electric-sql/d2ts. Not sure they're comparable, but they seem to be aiming at the same problem.
- sorenbs 3mo ago[dead]
- geoHeil 3mo agoI maintain a similar library more focused on data engineering needs: https://docs.metaxy.io/ https://docs.metaxy.io/ maybe it is useful for more people.
- ronfriedhaber 3mo agoThis is cool. 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 https://modolap.com [2] Signals And Threads episode on the subject https://signalsandthreads.com/build-systems/ https://signalsandthreads.com/build-systems/
- valzam 3mo ago> https://modolap.com https://modolap.com Redirect to a 2k USD stripe payment with no explanation when clicking on the main callout button is a pretty baller move.
- ronfriedhaber 3mo agoOne man's baller is another man's insufficiently baller. Email me for details, pricing & installations, or your target use case, would love to talk. In addition, if you have any feedback. ron at modolap dot com
- foltik 3mo agoYour site has a bunch of marketing copy, trademark symbols, and a link to pay you $2k/mo, but zero technical detail and is broken on mobile. It gives vibe coded. The benchmark of 2m black-scholes evals/sec is meaningless without additional context. Also seems a couple orders of magnitude slower than what I’d expect even for a single core. What exact transformations are being done, and what’s the throughput in GB/sec? Is it multi threaded? Benchmark against the equivalent query in kdb+ and ClickHouse?
- arthurbrown 3mo agoAnother related but semantically distinct package with great developer ergonomics is the FRP library React -- https://erratique.ch/software/react/doc/React/index.html https://erratique.ch/software/react/doc/React/index.html Very satisfying to use when you manage to find a problem that is suited to this type of approach.
- geokon 3mo agoWhere is it actually explained how it works..? 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
- Balinares 3mo agoWhenever I see something in OCaml I assume it's Jane Street and that ends up correct a surprising amount of the time.
- shikck200 3mo agoJane street was/is a top user of ocaml, they kind of flushed their reputation down the toilet with they massive fraud in the asian markets. IIRC the entire company got banned from trading inside India, hongkong etc. After they got caught most of their online posts/videos either got deleted, or locked so you could not comment on them. I had hoped their front guy for ocaml, Ron Minsky had atleast made some sort of statement. Currently no ones know how deep that fraud went, but what we know ocaml was used in the fraud, damagine ocaml ecosystem too.
- luciana1u 3mo ago[flagged]
- iamwil 3mo agoFor those interested in incremental systems, I recommend checking out DBSP. I thought it was pretty neat.
- evomassiny 3mo agoCan'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
- deleted 3mo ago[deleted]
- SkiFire13 3mo agoWhat 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.
- pgt 3mo agoElectric Clojure does incremental rendering that crosses the client/server boundary: http://electric.hyperfiddle.net/ http://electric.hyperfiddle.net/ The closest thing to Electric (IMO) is SolidJS, but frontend only: https://www.solidjs.com/ https://www.solidjs.com/
- srean 3mo agoIt might be worth reading this in concert with https://hn.algolia.com/?q=flow+based+programming+ https://hn.algolia.com/?q=flow+based+programming+
- osener 3mo agoIf you find this interesting, also check out their UI library called Bonsai that built on top of Incremental: https://github.com/janestreet/bonsai/ https://github.com/janestreet/bonsai/ 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 https://github.com/ozanvos/bonsai_revery
- Arshad-Talpur 3mo ago[dead]
- xiaodai 3mo agopardon my ignorance but is Ocaml performant enough? Why isn't something like this coded in say, C++?
- klibertp 3mo agoIt 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.
- tangsoupgallery 3mo ago[flagged]
- lsuresh 3mo agoOver at Feldera, we focus on IVM for SQL, but incremental computing problems show up far and wide: UIs, spreadsheets, control planes, compilers and more.
- shortercode 3mo agoOh cool I was working on something similar awhile back and couldn’t find much precedent. The project got retired as our use case went away. But I’d love to revisit it. It’s still on npm as “data-rambler”. Idea was a DSL that could be loaded into a JS runtime, then fed data streams. Your module would transform that data into various output streams which could then be fed to a separate reporting library. Powering dynamic reports based on a template. Our first iteration was already pretty powerful but I had some big plans to bring it into a more JS feeling syntax to reduce complexity.
- erichocean 3mo agoParallel Self-Adjusting Computation[0] is a fun entry in this genre. [0] https://github.com/cmuparlay/psac https://github.com/cmuparlay/psac
- atombender 3mo agoThis library is based in part on that same paper.
- jheriko 3mo ago[dead]
- jimaway123 3mo agoIs anyone aware of a version of this focused on very speed sensitive, low-level incremental computation? Like perhaps a compiler that generated a kernel for doing an incremental computation on a static graph?
- tempfile 3mo agoGiven this is a Jane Street library, I would be surprised if it were not very speed-sensitive already.
- erichocean 3mo agohttps://github.com/cmuparlay/psac https://github.com/cmuparlay/psac is extremely fast, I use it to recompute sculpting topology updates (think: Zbrush DynaMesh) at 60 fps.
- jimaway123 3mo agoYes I can see it would be pretty fast, but the computation is defined at run time and its evaluation uses pointers to the various nodes of the computation graph. This limits what optimizations be applied (ie inlining, vectorization, reordering, etc). I'm just curious if anyone has taken this a step further and written something like PSAC except with a code-generation step that creates an optimized implementation of psac_propagate() for the specific computation graph.
- grovesNL 3mo agoI think it would be interesting, especially for dynamic use cases where you can recompile the graph but use it many times. Although it's also probably pretty niche to get to that level of performance from these libraries. At that point I'd guess most projects start to build up their own set of primitives (e.g., containing subsets of particular graphs) that they can hand-optimize better than these general purpose computation graphs. That's what I ended up doing so I could better control the tradeoff around which operations should be batched, heuristics around how cheap certain operations are (especially based on the elements at the time), more complex dependency tracking when working with data outside the graph, etc.
- seobot_dk1289 3mo ago[flagged]
- eyupucmaz 3mo agoInteresting to see JaneStreet's take on incremental computation. As a frontend engineer working with React state management (Zustand, Jotai), the concept of granular re-computation is very familiar — though the OCaml type system gives this a level of correctness guarantees that JS solutions can only dream of.
- lilactown 3mo agoOne of my favorite tech talks is "Seven implementations of incremental": https://www.janestreet.com/tech-talks/seven-implementations-of-incremental/ https://www.janestreet.com/tech-talks/seven-implementations-...
- deleted 3mo ago[deleted]
- 01111011111 3mo ago[dead]