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

71–80 of 83 posts

Re: Incremental – A library for incremental computations

#71

Post by Eliah_Lakhin »

jimaway123 wrote: post #53
Eliah_Lakhin wrote: post #32

Earlier quoted context omitted.

I meant that the graph (DAG) structure is not necessary need to be sealed and defined upfront. It could be computed and changed on the fly by the same function that computes node's value. Assuming that the node value computation function is a pure function without side effects (e.g. it's output depends purely on inputs) the function may read other node values directly, and the act of reading would establish graph edg…

How do you consistently update a DAG, like you describe in your medium article, if the functions corresponding to the nodes in the graph are free to create new dependencies willy-nilly? It seems like this would have to be pretty restricted and/or performance killing, because you'd have to evaluate the graph under the assumption that any node could depend on any other node (unless that dependency creates a cycle, pres…

In the article it is assumed that the object of the node owns a vector of it's dependencies locally. We don't need to access the entire edges set all at once. The evaluation process is recursive. Once the node's function re-evaluate, the vector is being updated. Though, the re-evaluation is not happening for every node every time due to the caching system based on the node's value hash comparison and the two-layer monotonic versioning in case of present algorithm. Other incremental computation algorithm have different approaches in verifying on whether the node's function needs to be re-evaluated. Each approach have pros and cons.

You are right, it is assumed that in general the average node function evaluation is more expensive than the cost of graph management. It's not too expensive, but if by chance node's function is notably cheaper, this approach could be suboptimal in certain cases.

The key insight here is that it is assumed the end user don't need to actualize the entire graph each time any random input is being changed. The user observes only a small portion of the graph nodes in real time, and the incremental computation system ensures to minimize required evaluations. If this local observability is not a goal the system is not incremental by definition. For example, in case of Spreadsheets the entire table could be 10000x10000 cells, however the end user typically sees only a small portion of the table on the screen. On a general note the incremental computation systems are closely tied to the GUI-related tasks.

Re: Incremental – A library for incremental computations

#72

Post by WorldMaker »

Eliah_Lakhin wrote: post #12
RandomBK wrote: post #4

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…

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

> You can organize the same system in terms of observers and subscribers.

Also, the differences between "hot" and "cold" observers and the use of schedulers.

I like that about the observable pattern that while hot versus cold is confusing, it is generally "explicit" in the dance of observers/subscribers. I also tend to like the way that observable schedulers and scheduling operators are often usefully explicit in halting computations while still being largely automated in the time domain.

Certainly my gut instinct with this specific library is seeing if the stuff being done with it might be a cleaner fit in something like RxOcaml, but I realize I'm in something of a minority in preferring explicit observable operators over implicit "computation signals".

Re: Incremental – A library for incremental computations

#74

Post by bboreham »

rwmj wrote: post #47
zitterbewegung wrote: post #21

Earlier quoted context omitted.

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…

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

Some 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

Re: Incremental – A library for incremental computations

#77

Post by jitl »

lioeters wrote: post #65
seanmcdirmid wrote: post #58

Earlier quoted context omitted.

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

here’s a page with a very unscientific benchmark that runs a computed signal for every pixel of a {320p, 480p, 720p, 1080p, 4k} canvas and tries to recompute 10% of the graph per frame. on my m4 macbook pro, dalien-signals manages the highest fps and lowest heap out of libraries i could find to test. i think there’s still room for improvement though, im not satisfied with cache locality of graph under heavy churn; iirc i only compact/move stuff on resize or a large deallocation batch. so theres potential for original js-heap-allocated alien-signals to be faster in spots where moving GC becomes an advantage. lemme know if my library ends up being a win for you!

https://justjake.github.io/dalien-signals/

Re: Incremental – A library for incremental computations

#78

Post by zitterbewegung »

27183 wrote: post #68
zitterbewegung wrote: post #21

Earlier quoted context omitted.

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.

The problem was that people who know python don't really expect this specific DSL and it is easier for someone that doesn't know python and just learn their DSL and then read the rest of python.

Re: Incremental – A library for incremental computations

#79

Post by lioeters »

jitl wrote: post #77
lioeters wrote: post #65

Earlier quoted context omitted.

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

here’s a page with a very unscientific benchmark that runs a computed signal for every pixel of a {320p, 480p, 720p, 1080p, 4k} canvas and tries to recompute 10% of the graph per frame. on my m4 macbook pro, dalien-signals manages the highest fps and lowest heap out of libraries i could find to test. i think there’s still room for improvement though, im not satisfied with cache locality of graph under heavy churn; ii…

[dead]

Re: Incremental – A library for incremental computations

#80

Post by klibertp »

xiaodai wrote: post #46

pardon my ignorance but is Ocaml performant enough? Why isn't something like this coded in say, C++?

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.

Post reply on HN