Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Incremental – A library for incremental computations

github.com

Post reply on HN
Print view View original

61–70 of 83 posts

Re: Incremental – A library for incremental computations

#61

Post by jimaway123 »

erichocean wrote: post #59
jimaway123 wrote: post #56

Is 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?

https://github.com/cmuparlay/psac is extremely fast, I use it to recompute sculpting topology updates (think: Zbrush DynaMesh) at 60 fps.

Yes 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.

Re: Incremental – A library for incremental computations

#62

Post by ronfriedhaber »

foltik wrote: post #55
ronfriedhaber wrote: post #34

Earlier quoted context omitted.

One 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

Your 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 broken on mobile

Not true as of last deployment.

> but zero technical detail

What additional technical detail would you be interested in?

> Also seems a couple orders of magnitude slower than what I’d expect even for a single core.

1) it's more than 2m/s on a MacBook AIR 2) Most of the latency is networking. This was a preliminary setup with a client / server over websockets where the book of 1m contracts combination of (strike, exp_date). Each insert only after a corresponding query has been returned (over the wire) from the previous insert. I can agree the eval isn't great; as in, the throughput is much higher.

> What exact transformations are being done

This is provided in the blog post.

Re: Incremental – A library for incremental computations

#63

Post by eyupucmaz »

Interesting 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.

Re: Incremental – A library for incremental computations

#64

Post by hantusk »

ronfriedhaber wrote: post #24

This 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 (…

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

Re: Incremental – A library for incremental computations

#65

Post by lioeters »

seanmcdirmid wrote: post #58
jitl wrote: post #54

Earlier quoted context omitted.

my understanding of FRP is the inverse of your description, I use the same definition of “functional reactive programming” as in this Jane Street blog post on the subject https://blog.janestreet.com/breaking-down-frp/ : FRP is history sensitive and wants to compute over some stream of events explicitly - and the sort of events we expect the system to handle are UI events like mouse motions, clicks, and FRP is expecte…

You might want to go over the original Elliot/Hudak work? It’s a bit obtuse since it’s all in Haskell, but signals were never meant to be historical accumulators unless you set them up that way. Signals are continuous values, they don’t reveal discrete events like streams do, that’s the main distinction between them, your signal computations then can be viewed as a continuous value derived from other continuous value…

I assume you mean "Functional Reactive Animation" (1997) by Conal Elliott and Paul Hudak? While searching for this, I found a great collection of papers on this topic of Functional Reactive Programming in the Haskell language wiki. Most are by Elliot and/or Hudak. Good stuff!

https://wiki.haskell.org/Research_papers/Functional_reactive...

This feels related to many other topics and various strategies, like incremental parsing/compilation/computation, reactivity, CRDTs (conflict-free replicated data type) and distributed computing. About coordinating state changes, reconciling differences, managing dependencies and derived values.

@jitl, the "Data oriented signal library", dalien-signals, looks very interesting and useful, particularly for efficient UI rendering like large tables or maybe editors. I'll enjoy exploring it.

Re: Incremental – A library for incremental computations

#67

Post by SkiFire13 »

evomassiny wrote: post #37

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 co…

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.

Re: Incremental – A library for incremental computations

#68

Post by 27183 »

zitterbewegung wrote: post #21
fadesibert wrote: post #6

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. Edit: Related HN discussion https:…

Yea and this created "bank python" informally a good article is here. 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 le…

Wow 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.

Re: Incremental – A library for incremental computations

#70

Post by grovesNL »

jimaway123 wrote: post #61
erichocean wrote: post #59

Earlier quoted context omitted.

https://github.com/cmuparlay/psac is extremely fast, I use it to recompute sculpting topology updates (think: Zbrush DynaMesh) at 60 fps.

Yes 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 p…

I 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.

Post reply on HN