News for hackers. Stuff that matters.
Re:Differential Dataflow but at what cost? (2017) by edflsafoiewq on Sunday January 19, 2020 @07:27PM (#22095199)
Incremental. I think the problem is this: you have an input that you want to change a bunch of times

    input = ...;
    input += d1;
    input += d2;
    input += d3;
and you have some output that depends on the input. Whenever the input changes, the output needs to be recomputed, like this

    input = ...;     output = f(input);
    input += d1;     output = f(input);
    input += d2;     output = f(input);
    input += d3;     output = f(input);
The idea here is to, instead of recomputing the output every time from scratch, find a function g that will compute the output-difference from the input-difference

    input = ...;     output = f(input);
    input += d1;     output += g(d1);
    input += d2;     output += g(d2);
    input += d3;     output += g(d3);
And I think if you write f using the combinators from the differential dataflow framework it will be able to find g automatically for you.
Re:Differential Dataflow but at what cost? (2017) by mehrdadn on Sunday January 19, 2020 @07:39PM (#22095256)
Yeah, makes sense. Dynamic breadth first search has been a thing for a while; it seems like they're just introducing it with a new name. The automatic part seems cool though!
Re:Differential Dataflow but at what cost? (2017) by hexane360 on Sunday January 19, 2020 @08:55PM (#22095612)
The idea is that it isn't limited to breadth first searches. It provides a way to write algorithms such that they are automatically differential in nature.
Re:Differential Dataflow but at what cost? (2017) by iamwil on Sunday January 19, 2020 @09:07PM (#22095671)
Where did you learn how it worked? Was it just through his other blog posts?
Re:Differential Dataflow but at what cost? (2017) by benesch on Sunday January 19, 2020 @11:59PM (#22096437)
Frank’s written a tutorial style mdbook on Differential [0] that I highly recommend in addition to his blog posts. There’s also the research paper on the spawned the Timely and Differential projects, Naiad [1].

If you get into it, the library itself is well documented on docs.rs and there’s an active Gitter channel.

(Disclaimer: I work with Frank at his company, Materialize.)

[0]: https://timelydataflow.github.io/differential-dataflow/

[1]: http://sigops.org/s/conferences/sosp/2013/papers/p439-murray...

Re:Differential Dataflow but at what cost? (2017) by edflsafoiewq on Monday January 20, 2020 @12:52AM (#22096624)
Obviously computing output-diffs from input-diffs looks a lot like automatic differentiation. Is there a precise relationship?
Re:Differential Dataflow but at what cost? (2017) by iamwil on Sunday January 19, 2020 @11:41PM (#22096369)
How would writing f using combinators yield the ability to derive g?
Re:Differential Dataflow but at what cost? (2017) by benesch on Monday January 20, 2020 @12:07AM (#22096457)
Each combinator knows how to produce the output diff from an input diff; the computation is then just a matter of stringing these combinators together.

For example, consider a map combinator. The output diff is just the input diff with a function applied to the data. More formally, for every incoming (data, time, diff) triple, an output triple (f(data), time, diff) is produced.

For a filter combinator, the output is (data, time, diff) if f(data) is true, or (data, time, 0) if f(data) is false.

A computation that wants to filter and map some data then just requires piping together these operators.

Things get interesting when you want to aggregate and join data, but Frank’s blog posts and documentation explain how you build that in a dataflow system far better than I can here.