flatMapLatest glitch

[skozin]

Consider the following setup:

B = require 'baconjs'

trace = (obs, name) ->
  obs.subscribeInternal (e) ->
    desc = if e.hasValue() then e.value() else '' + e
    console.log name + ':', desc

traceAll = (obss) -> trace(obs, name) for name, obs of obss

changes = new B.Bus

a = changes.map '.a'
b = changes.map '.b'

ab = B.combineAsArray a, b

f = ab.flatMapLatest (values) ->
  valuesDesc = "( #{ values.join ', ' } )"
  console.log 'inside flatMapLatest: ' + valuesDesc
  B.once 'f' + valuesDesc

fb = B.combineAsArray f, b

traceAll { a, b, ab, f, fb }

changes.push
  a: 'a_0'
  b: 'b_0'

console.log '-------------------------------'

changes.push
  a: 'a_1'
  b: 'b_1'

console.log '-------------------------------'

console.log 'fb depends on f:', fb.dependsOn f
console.log 'fb depends on b:', fb.dependsOn b
console.log 'fb depends on ab:', fb.dependsOn ab
console.log 'fb depends on a:', fb.dependsOn a
console.log 'fb depends on b:', fb.dependsOn b

... and the output:

a: a_0
b: b_0
ab: [ 'a_0', 'b_0' ]
inside flatMapLatest: ( a_0, b_0 )
f: f( a_0, b_0 )
fb: [ 'f( a_0, b_0 )', 'b_0' ]
-------------------------------
a: a_1
b: b_1
ab: [ 'a_1', 'b_1' ]
inside flatMapLatest: ( a_1, b_1 )
fb: [ 'f( a_0, b_0 )', 'b_1' ]
f: f( a_1, b_1 )
fb: [ 'f( a_1, b_1 )', 'b_1' ]
-------------------------------
fb depends on f: true
fb depends on b: true
fb depends on ab: true
fb depends on a: true
fb depends on b: true

Notice the glitch after the second push (fb = [ 'f( a_0, b_0 )', 'b_1' ]). Is this a correct behavior?

If I change flatMapLatest to flatMap, the glitch disappears.

[skozin]

I think this might be somehow related to the fact that observables spawned inside flatMapLatest are dependent on the source stream (as a result of takeUntil combinator):

flatMapLatest: =>
    f = makeSpawner(arguments)
    stream = @toEventStream()
    withDescription(this, "flatMapLatest", f, stream.flatMap (value) =>
      makeObservable(f(value)).takeUntil(stream))

But I am not sure, because the glitch is highly setup-dependent. For instance, the update of fb after the second push is atomic when flatMapLatest is applied to the stream a instead of ab = combineAsArray(a, b).

[raimohanska]

I made a fiddle of this: http://jsfiddle.net/G4aAb/1/

[raimohanska]

So yes, this seems like a real glitch and needs investigation. I'll have a look.

[raimohanska]

The glitch occurs because f doesn't "depend" on the spawned streams, the update in which are "put to hold" by takeUntil. Gotta think how to fix that.

[raimohanska]

The dependsOn mechanism relies heavily on immutability right now. This means we can't easily change the deps of the flatMapped stream on the fly. That would probably solve this problem.

[raimohanska]

The assumption was correct. I have a fix in 748dd4400de7e73ce609f186f42cc7537899ba90 although with the cost of disabling dep caching.

I don't have an actual test case in BaconSpec for this yet either.

[raimohanska]

Neither do the performance tests indicate a slowdown caused by disabling dep caching. Weird that.

I'd be more than happy to ditch the cache, but I have a feeling that it would cause slowdown in grownup applications. I'll check that out.

And there's always the possibility of carefully crafted cache invalidation :) That gives me creeps already tho.

[raimohanska]

Now there's a perf test for a "diamond" setup where cache matters. But it doesn't actually matter very much. It gives like 30% more speed.

[raimohanska]

The new stuff is in fix/353 branch.

[skozin]

Thank you very much for investigation and the fix! It's really weird that there is no slowdown after disabling the cache. Probably it would appear in complex setups with both deep and wide dependency graph.

I think that I have an idea how to implement rather simple and efficient invalidating cache. I'll make a PR after some experimenting.

[skozin]

Done. @raimohanska, do you think that the implementation from #355 is acceptable?

[raimohanska]

Already commented on the PR.

[rpominov]

I noticed similar issue with bus.plug(), for example:

a = new Bacon.Bus()
b = new Bacon.Bus()
a.plug(b)
mapA = a.map (x) -> 'a' + x
mapB = b.map (x) -> 'b' + x
Bacon.combineWith(((a, b) -> a + b), mapA, mapB).log()
b.push(1)
b.push(2)

=> a1b1
=> a2b1   <--- Glitch
=> a2b2

Not sure if it is a bug or intended behavior.

[raimohanska]

@pozadi Bus doesn't have "dependencies" so using a Bus in the middle of your event network will always defeat the glitch prevention mechanism.

[raimohanska]

@skozin this is still not solved. As I commented in #355 (which was kinda accidentally closed and cannot be re-opened), the invalidating caching solution doesn't work as-is, because it introduces a global memory leak. An invalidation cache is in fact tough to implement because back-references to dependent observables are not maintained. And the maintenance of which would also necessitate tracking of the lifecycle of observables to avoid causing a memory leak.

I was thinking about using a DAG instead of simple list to track the "waiters" in UpdateBarrier. This might decrease the number of "dependsOn" calls and would make the dep cache less necessary.

[raimohanska]

Another idea for cache invalidation. Let say we have deps A -> .. -> B. When the dependencies of B change at time t, we can tag B as "changed-at t". This itself cannot be used to bust the dependency cache of A (because there's no reference from B to A), but if the same change tag was applied to all current and previous deps of B, and the change-tag was checked for each cached dependency in the depends-on check, we could detect the need for invalidation. So when checking whether A depends on X if either any of cached deps of A or X itself had a change flag higher than A's cache timestamp, we'd invalidate the dep cache of A.

Not sure if this would improve perf in real-life use cases though.

[raimohanska]

Or we might try dep caching but only per transaction. At least in the "diamond" test case it seems there's just 89 transactions but 3 million depends-on checks.

[raimohanska]

I rebased the fix/353 branch on top of current master. The perf test indicates difference to master only in the "diamond" case where the difference is 13ops/sec vs 34 ops/sec, i.e pretty bad. And that's without dep caching.

[raimohanska]

Added transaction-scope caching with invalidation for flatMapped streams. Solves the diamond-case but slows down simpler cases :)

master:

diamond x 21.07 ops/sec ±8.66% (40 runs sampled)
combo x 34.25 ops/sec ±10.89% (33 runs sampled)
zip x 1,491 ops/sec ±7.53% (73 runs sampled)
Bacon.combineTemplate.sample x 321 ops/sec ±6.24% (75 runs sampled)
Bacon.combineTemplate (deep) x 18.63 ops/sec ±4.48% (36 runs sampled)
Bacon.combineTemplate x 228 ops/sec ±3.95% (75 runs sampled)
EventStream.map x 3,203 ops/sec ±5.71% (74 runs sampled)
EventStream.scan x 2,731 ops/sec ±4.54% (79 runs sampled)

no cache:

diamond x 9.99 ops/sec ±9.65% (29 runs sampled)
combo x 34.76 ops/sec ±10.93% (34 runs sampled)
zip x 1,553 ops/sec ±5.24% (77 runs sampled)
Bacon.combineTemplate.sample x 319 ops/sec ±4.43% (81 runs sampled)
Bacon.combineTemplate (deep) x 18.49 ops/sec ±3.86% (35 runs sampled)
Bacon.combineTemplate x 220 ops/sec ±4.22% (78 runs sampled)
EventStream.map x 3,054 ops/sec ±4.34% (77 runs sampled)
EventStream.scan x 2,687 ops/sec ±5.12% (76 runs sampled)

tx scope with invalidation:

diamond x 21.59 ops/sec ±8.97% (31 runs sampled)
combo x 32.09 ops/sec ±10.22% (37 runs sampled)
zip x 1,332 ops/sec ±8.00% (79 runs sampled)
Bacon.combineTemplate.sample x 297 ops/sec ±5.66% (73 runs sampled)
Bacon.combineTemplate (deep) x 17.01 ops/sec ±4.18% (41 runs sampled)
Bacon.combineTemplate x 208 ops/sec ±4.01% (74 runs sampled)
EventStream.map x 2,937 ops/sec ±6.06% (74 runs sampled)

[raimohanska]

Some minor tuning and

diamond x 22.07 ops/sec ±6.10% (32 runs sampled)
combo x 35.39 ops/sec ±8.94% (37 runs sampled)
zip x 1,409 ops/sec ±6.65% (78 runs sampled)
Bacon.combineTemplate.sample x 305 ops/sec ±6.23% (75 runs sampled)
Bacon.combineTemplate (deep) x 17.37 ops/sec ±5.41% (34 runs sampled)
Bacon.combineTemplate x 219 ops/sec ±3.41% (76 runs sampled)
EventStream.map x 2,814 ops/sec ±6.13% (72 runs sampled)

[raimohanska]

Performance is now so close to master that we should merge. Correctness over performance, especially when we're talking about a mere 5% reduction, right?

[raimohanska]

Alrighty then. Fixed and released 0.7.16! Good night!