Search code examples
reactive-programmingbacon.jskefir.js

exponential time and inconsistent transient values when pushing a value in reactive programming?

I'm fairly new to reactive programming, and I'm starting to play with kefirjs. On the face of it, it looks like bacon/kefir's event streams and properties are essentially a way to express a dependency/computation dag that varies with time, and there are neat ways to hook up these dags to DOM events and UIs. Ok, sounds good.

I know that in general, when you have a computation dag, if you change the value of a single upstream node and naively push the computation downstream recursively, the well-known problems are:

  1. it takes up to exponential time relative to the number of dag nodes affected

  2. intermediate computations use a mix of the previous and current values of the input node, resulting in strange/inconsistent transient output values.

I see from playing around with some simple toy programs that kefir does such updates naively, so (1.) and (2.) do in fact occur. (I haven't tried bacon.)

Are these not considered to be problems?

For an example, in the following program, I'd expect the output x6 to change directly from 64 to 640, at a cost of 12 combinator evaluations (6 initially, and 6 triggered by the single update). Instead, the output goes 64,73,82,91,...,622,631,640 (63 pointless intermediate values) at a cost of 132 combinator evaluations (6 initially, which makes sense, and then 126 for the update, which is excessive).

https://codepen.io/donhatch/pen/EXYqBM/?editors=0010

// Basic plus
//let plus = (a,b)=>a+b;

// More chatty plus
let count = 0;
let plus = (a,b)=>{console.log(a+"+"+b+"="+(a+b)+"  count="+(++count)); return a+b;};

let x0 = Kefir.sequentially(100, [1,10]).toProperty();
let x1 = Kefir.combine([x0,x0], plus).toProperty();
let x2 = Kefir.combine([x1,x1], plus).toProperty();
let x3 = Kefir.combine([x2,x2], plus).toProperty();
let x4 = Kefir.combine([x3,x3], plus).toProperty();
let x5 = Kefir.combine([x4,x4], plus).toProperty();
let x6 = Kefir.combine([x5,x5], plus).toProperty();
x6.log('                x6');

I'm rather mystified that kefir apparently makes no attempt to do such updates efficiently; I'd think that would make it a non-starter for real apps.

Maybe I'm misunderstanding what reactive programming is used for. Are the dags encountered in real-life reactive apps always trees, or what?

Solution

  • Bacon.js has Atomic Updates (https://github.com/baconjs/bacon.js/#atomic-updates) while Kefir has not. This is why with Bacon.js you'll see your desired behaviour while with Kefir you'll get a lot of intermediate values.