partially solve glitches problem in combine

[mhelvens]

I sometimes need several properties that maintain a valid arithmetic relationship. For example, properties F, B and C such that we always have B = C * F.

If I change B, then C should update itself. If I change C, then B should update itself. If I change F, one of them should update itself. I do this by plugging each into the pool that feeds the other:

Bp.plug(Kefir.combine([C, F], (c, f) => c * f));
Cp.plug(Kefir.combine([B, F], (b, f) => b / f));

If I change the value of F to upset the equilibrium, a stack overflow will occur. Since both properties are set up to skip duplicates, and in my scenario I'm working with integers at all times (so, no rounding errors), I would expect them to quickly reach a new equilibrium. Have a look at the following Fiddle for a minimal working example:

https://jsfiddle.net/mhelvens/hcpy13x0/1/

If you comment/uncomment as indicated in the code, some extra debugging output is printed in the console, and we can see what's going on. The two plugs are in mutual recursion, but each is working with a different value for F --- one is using the old value, the other is using the new value. I believe this should be considered a bug.

I can bypass the problem by maintaining the state of F independently from Kefir. See example:

https://jsfiddle.net/mhelvens/9kzfbjqq/1/

But I'm trying to be pure here. :-)

[rpominov]

Seems like the problem here is "glitches" of combine (see #97) If we avoid them manually, by moving B to passive observables in combine, it works:

- Cp.plug(Kefir.combine([B, F], (b, f) => b / f));
+ Cp.plug(Kefir.combine([F], [B], (f, b) => b / f));

[rpominov]

The changed version is more in line with your requirements, BTW:

If I change B, then C should update itself. If I change C, then B should update itself. If I change F, one of them should update itself.

[mhelvens]

Thanks for the quick response.

I half expected the "use a passive dependency" answer. But then what if I don't manually change F, but manually change B? Then it wouldn't trigger the change in C. (My real project exhibits this scenario a lot. The dependency graph there is a bit more complex, and it's hard to compress it in a simple working example. But this example seems to illustrates the issue.)

And even if it did work, it would be a big maintenance problem if I have to keep track of the asymmetry in active vs passive dependencies. It would break encapsulation if two components need to agree on which one of them will keep an active dependency to the other.

Currently, I'd choose the lesser of two evils, and manually keep track of values (i.e., have a synchronous getCurrentValue() function; see second fiddle) and use them in the transform function. In fact, could you not do something similar internally, or would that break certain properties?

[rpominov]

Currently, I'd choose the lesser of two evils, and manually keep track of values (i.e., have a synchronous getCurrentValue() function) and use them in the transform function. In fact, could you not do something similar internally, or would that break certain properties?

You have probably invented another ad-hoc glitch privation mechanism, which works in your case but can't be extended to a general solution. I did't see the code, but I suspect it works like this:

let curA
let curB
A.onValue(a => {curA = a})
B.onValue(b => {curB = a})
const AB = Kefir.combine([A, B], (a, b) => curA + curB)
AB.log()

This is works because you have separate subscriptions to A and B, that always get values earlier that subscriptions inside combine. So at the moment combine only got one value and is in an inconsistent (glitch) state curA and curB already both updated, and if we reading from them we get consistent result.

Hm, on the second thought this could actually work, if we simply duplicate subscriptions to all sources in combine, and emit on values from second subscriptions but using values from first ones. Would be cool if someone tried to implement a Kefir.safeCombine() method using this technic. Do you want to try?

[mhelvens]

Yes, that's what I'm doing. See the second fiddle link. I'd be happy to try and create that method. (I'm a bit busy this weekend though.)

Your suggestion would work, but I don't see why it's even needed. I don't really know the Kefir internals, but presumably you store the current value of a property in a field inside that property already, so when that changes it should be available to all other observables that subscribe to it. Instead, it seems you're keeping copies of current values inside the combine instances.

I may be completely off, but I guess that combine([A, B], fn) is currently doing something like this:

• Oh, I'm being notified of a change in B.
• I will update my local copy of B.
• I will call fn, and pass local copies of A and B to it.

But it should instead do something like this:

• Oh, I'm being notified of a change in B.
• I will call fn, and pass A._currentValue and B._currentValue to it.

In other words, why don't you cheat? It's OK if you don't expose it in the public API.

[rpominov]

Yes, you're right, combine keeps local copies. This is done because it also supports streams which don't have internal ._currentValue. Also I'm not sure ._currentValue will actually be updated in time if we try to use it. This all need more investigation, it may not actually work in general case with duplicate subscriptions either. We could add ._currentValue to streams and try to use it.

[mhelvens]

Shouldn't the combine instance just subscribe to stream.toProperty()?

As for update-order. I suspect that when a property changes, it first updates its stored value, and then emits a signal afterwards. If so, we'll be fine.

[rpominov]

Shouldn't the combine instance just subscribe to stream.toProperty()?

If I remember correctly it's not that way only because of performance hit.

[mhelvens]

I suspect that the performance hit would be negligible, or at least equaled by storing local copies anyway.

[rpominov]

No, It's quite noticeable, I've tried it. At least was noticeable back then.

[mhelvens]

Can you account for the performance hit? To my mind, a property is just a stream that keeps a local copy of the last value (and emits it at new subscriptions).

But anyway, yeah, you could just store _currentValue inside streams for a quick and easy solution, and see if it works to solve the glitch.

[rpominov]

Can you account for the performance hit?

It adds a layer of indirection in subscriptions (adds extra dispatcher)

[mhelvens]

So it does. Strange that it would be so noticeable.

Anyway, I'd love to see you try my last suggestion. It'll be some time before I could work on this myself.

[rpominov]

I took a closer look, actually my assumption from https://github.com/rpominov/kefir/issues/193#issuecomment-198695857 was wrong. This won't help.

const src = Kefir.later(1, 1).toProperty(() => 0)
const map1 = src.map(x => 10 + x)
const map2 = src.map(x => 20 + x)
const combined = Kefir.combine([map1, map2], (x, y) => [x,y])
combined.log()

[combine] <value:current> [10, 20]
[combine] <value> [11, 20]
[combine] <value> [11, 21]
[combine] <end>

const src = Kefir.later(1, 1).toProperty(() => 0)
const map1 = src.map(x => 10 + x)
const map2 = src.map(x => 20 + x)
var x1, x2
map1.onValue(x => {x1 = x})
map2.onValue(x => {x2 = x})
const combined = Kefir.combine([map1, map2], (x, y) => [x1, x2])
combined.log()

[combine] <value:current> [10, 20]
[combine] <value> [11, 20]
[combine] <value> [11, 21]
[combine] <end>

Not sure why it helps in your case though. If you find a way to make it a general solution that would be great.

Anyway, I'd love to see you try my last suggestion. It'll be some time before I could work on this myself.

I don't have much time to work on this project either unfortunately. But I'm very open to any contribution, and would be happy to help by reviewing PRs, discussing solutions, answering any questions etc.

[mhelvens]

Ah, but the problem you're describing there is, to my mind, a different problem than the one I described.

If I'm guessing correctly, you'd like to get rid of the [11, 20] result in between, since the update for both values originally came from the same source, i.e., you have a diamond in your dependency graph. But it still settles properly in the end.

My problem is different. I have a cycle in my dependency graph. I would expect first the one, then the other to be updated. But since the combines are storing local copies rather than fetching the values from their original source, one of them uses an old copy, and one a new copy, causing the cycle to never end.

My problem is rather easily solved. Have combine fetch the values from the original properties directly, rather than storing copies. For streams, if .toProperty() is too expensive, just have them store their last value too. It would help me a lot with my work if you could implement this fix.

Your problem is a bit more tricky, but certainly not impossible. I'd be happy to work with you on that when things have died down a bit. But one solution that immediately comes to mind is this. Starting at the original source of a synchronous signal (.stream, .later, .fromEvents, ...), send out the signal in two phases: [1] send an advance signal to let every recipient know what to expect, then [2] send out the actual signal. A .combine would pass every phase 1 signal through immediately, but in phase 2 it would wait until all expected signals had arrived.

This would probably cover most cases, but there are some caveats. First, a naive implementation would hurt performance. This may be mitigated by performing incremental pre-processing whenever the dependency graph changes. (If you go this route, changing stream connections would be a bit slower, but passing signals would be a lot faster.) Second, in order to participate in phase 1 signaling, a stream adapter has to be either side-effect free, or be specially equipped for phase 1 signaling. Otherwise, the side-effects would happen twice.

[rpominov]

My problem is different. I have a cycle in my dependency graph. I would expect first the one, then the other to be updated. But since the combines are storing local copies rather than fetching the values from their original source, one of them uses an old copy, and one a new copy, causing the cycle to never end.

I think you have both a cycle and a diamond actually :) Honestly I don't quite understand what is going on in your example (I mean internally in Kefir).

But I'm almost certain reading directly from ._currentValue will change nothing. I think we'll get exactly same values as from copies.

[mhelvens]

I think you have both a cycle and a diamond actually :)

Nah. Mine is definitely a triangle.

Honestly I don't quite understand what is going on in your example (I mean internally in Kefir).

Throughout the conversation I'm getting more and more convinced that I do understand.

But I almost certain reading directly from ._currentValue will change nothing. I think we'll get exact same values as from copies.

Did you look at the second jsfiddle of my original post? I made exactly that change (though, from outside Kefir), and it worked. It also worked in my larger project.

If you would go look at that second jsfiddle, I will in the meantime write a more comprehensive explanation of what I think causes the stack to overflow in fiddle 1.

[rpominov]

It would help if you create a more minimal example that only shows the difference between values in combine, when they're read from copies and from external variable or ._currentValue.

[mhelvens]

Here's what's happening in the F, B, C example of fiddle 1. Note that everything here happens synchronously. They start respectively with values: F.val = f1, B.val = b1, C.val = c1, and the two combine instances each have local copies of their dependencies: B.f = f1, B.c = c1, C.f = f1, C.b = b1.

1. F gets a new value: F.val = f2 and intends to emit it to each of its subscribers in turn: B, C
2. It emits f2 to B. (C has to wait until B is finished)
   1. B receives the signal and updates its local copy B.f = f2
   2. It calculates its own new value B.val = b2 based on B.f = f2 and B.c = c1
   3. It emits b2 to its only subscriber: C
      1. C receives the signal and updates its local copy C.b = b2
      2. It calculates its own new value C.val = c2 based on C.f = f1 and C.b = b2
      3. It emits c2 to its only subscriber: B
         1. B receives the signal and updates its local copy B.c = c2
         2. It calculates its own new value B.val = b3 based on B.f = f2 and B.c = c2
         3. .....

This continues until the stack overflows. We keep having B.f = f2 and C.f = f1 (because it will never be C's turn to receive the new F value), so their formulas are not in equilibrium, and the cycle is never stopped by .skipDuplicates.

If there are no local copies, but values are fetched directly from the original property, it would go like this:

1. F gets a new value: F.val = f2 and intends to emit it to each of its subscribers in turn: B, C
2. It emits f2 to B. (C has to wait until B is finished)
   1. B receives the signal
   2. It calculates its own new value B.val = b2 based on F.val = f2 and C.val = c1
   3. It emits b2 to its only subscriber: C
      1. C receives the signal
      2. It calculates its own new value C.val = c2' based on F.val = f2 and B.val = b2
      3. It does not emit anything, because c2' === c1; the signal is stopped by .skipDuplicates
3. It emits f2 to C
   1. C receives the signal
   2. It calculates its own new value C.val = c3' based on F.val = f2 and B.val = b2
   3. It does not emit anything, because c3' === c1; the signal is stopped by .skipDuplicates

Done. Both B and C always have the same value F.val = f2, so their formulas are in equilibrium, and C's new value fails to get through .skipDuplicates.

[rpominov]

Ok, I can confirm reading from ._currentValue changes behavior. Here is the minimal example:

The shape looks like this:

  F
 / \
C   \
 \ /
combined

const F = Kefir.later(1, 1).toProperty(() => 0)
const C = F.map(x => 10 + x)
const combined = Kefir.combine([C, F], (x, y) => [x, y])
combined.log()

[combine] <value:current> [10, 0]
[combine] <value> [11, 0]
[combine] <value> [11, 1]
[combine] <end>

const F = Kefir.later(1, 1).toProperty(() => 0)
const C = F.map(x => 10 + x)
var f
F.onValue(_f => {f = _f})
const combined = Kefir.combine([C, F], (x, y) => [x, f])
combined.log()

[combine] <value:current> [10, 0]
[combine] <value> [11, 1]
[combine] <value> [11, 1]
[combine] <end>

I'll look into fixing this.

[mhelvens]

That's great, thanks! Let me know if I can help.

In the meantime, I updated the two jsfiddles to generate better logs, also illustrating the problem.

Here is the version that fails: https://jsfiddle.net/mhelvens/hcpy13x0/4/ Here is the fixed version: https://jsfiddle.net/mhelvens/9kzfbjqq/2/

Though your example is simpler, and therefore better. Unfortunately, as you've noticed, the fix doesn't help with your actual diamond problem, when there are four nodes participating in the graph.

[rpominov]

The fix seems to do good things for your diamond problem too. It's still generating two signals, but you don't get inconsistent values. :-)

Not quite, in diamond case this fix don't work (see example I posted), which is why I thought it never works. But it works in triangle case.

[mhelvens]

Yeah, I realized it as soon as I posted it, and made an edit. ;-) You respond really quickly.

[rpominov]

I tried it in a branch, and it works. But we should consider this a breaking change, because it may add many subtle differences. One example, in the triangle case, it also adds extra value in response to the first value from the source:

- [1,1], [2,1], [2,2]
+ [1,1], [1,1], [2,2], [2,2]

I didn't work with Kefir for a while so I having trouble predict what other cases this change may affect, and I don't think it's a good idea to introduce this change in a minor release.

This will hopefully land in 4.0

[mhelvens]

Thanks for the quick work!

But why does it add an extra value? In the proposed change as I understand it, you wouldn't have changed the timing or number of signals, nor would you have added or removed any subscriptions. You would simply have changed the source of values used inside combine, no?

[rpominov]

Well, it's more complicated. Take a closer look at source code if you're interested.

[mhelvens]

I've had a look, and I'm fairly confident I figured out the problem there. https://github.com/rpominov/kefir/commit/7a0bd7a547baa6f0063b36e4ea9d0a4177f729bd#commitcomment-16778577

If you agree with my proposed fix, I would much appreciate an early release of this change.

[rpominov]

Probably won't happen closing for now to cleanup open issues.

[mhelvens]

Not even in a future release?

[rpominov]

Yeah, I don't think it's a good idea, sorry.

[mhelvens]

You mean my proposed fix is not a good idea, or do you not agree that the proposed behavior is better than the current behavior?