Atomic updates to Properties

[raimohanska]

Assume you have properties A and B and property C = A + B. Assume that both A and B depend on D, so that when D changes, both A and B will change too.

When D changes d1 -> d2, the value of A a1 -> a2 and B changes b1 -> b2 simultaneously, you'd like C to update atomically so that it would go directly a1+b1 -> a2+b2. Unfortunately, Bacon.js does not recognize simultaneous events/updates and C will have a transitional state like a1+b1 -> a2+b1 -> a2+b2

[raimohanska]

I got this idea yesterday. There might, after all, be a quite simple way to achieve atomic updates.

The main idea would be to hold all Property updates to external observers until the orinal event has been fully dispatched. All internal updates would work as before, but only the very last update originating from the same input event would be sent to any external observer. That's it!

Now we just need to identify external and internal observers and the entry point of the original event so that we can do this.

The external and internal observers can be distinguished using a subscribeInternal method for all internal observers. Now we would always know what subscribers are actual exit points for events, the rest of the observers being internal to the Bacon.js event system.

The entrance point for events can also be determined quite easily: in a single-threaded environment we can simply use global state to keep track of whether we are already "inside the system". In Dispatcher.push we can check whether we are already "inside", so that we'll know whether this is an entrance point to the system.

The idea can be taken a step further too: We can easily provide Bacon.atomically(f) to allow, for instance, pushing to several Bus object in a single atomic update.

Please (in)validate this idea!

[RoboTeddy]

I don't see any holes in the logic. Nice work!

I don't know much about browser event architecture, but:
Is there a solid way to determine all the entrance points that matter? We'd probably need some way to set the global "inside the system" flag back to 'false' at the start of each browser loop (or the end of the previous one). If we receive an event directly from the DOM (e.g. via asEventStream), we can be confident we're at a new entrance point. But what about browser loop entrance points that don't have associated events? i.e. setTimeout, setInterval, and requestAnimationFrame?

For example, I have a 'tick' stream that fires on each requestAnimationFrame:

tick = new Bacon.EventStream (sink) ->
  cb = (time) ->
    sink(new Bacon.Next time)
    window.requestAnimationFrame cb
  window.requestAnimationFrame cb
  _.noop

These should probably count as new entrance points. If there's no way to auto-detect this situation, we might need to add a way to manually tell Bacon that something is an entrance point. Or, perhaps we could only support atomic property updates when using Bacon.later, Bacon.interval, and perhaps a built-in Bacon.frame observable

I don't understand browser or bacon internals enough to be confident at all here-- I might just be making up imaginary problems :)

[raimohanska]

Ted, Thanks for helping me validating this idea!

It happens to be so, that all EventStreams route their events through a Dispatcher, which means that we can in fact capture all entrance points in Dispatcher.push. Something like

    iAmRoot = false
    try
      if not Bacon.inside
        iAmRoot = true
        Bacon.inside = true
      doTheUsualDispatchingStuff()
    finally
      if iAmRoot
        sendPendingExternalUpdatesNow()
        Bacon.inside = false

[acthp]

If the update would be async (e.g. for a server fetch), I think there's still a problem. This solution relies on not giving up the cpu. It might allow, however, putting the async stream into some kind of pending state (None?).

E.g. suppose b requires a server fetch. When d updates, a1->a2, b1->undefined, and C filters on !undefined. When the fetch completes, b goes undefined->b2, and C gets a new value.

I'm not sure I understand how the internal/external thing would work. Suppose C is doing a join on two arrays by passing a function to .combine(). Is that function internal or external? If it's internal, the function will be called with inconsistent data, which might lead to the join failing.

[raimohanska]

You're correct in that the proposed solution only guarantees atomicity in case there's a single entry point.

In case A,B require an async fetch, you can keep the D -> C update atomic by using flatMap+combine:

var D = C.flatMap(function(c) {
  var A = Bacon.fromPromise($.ajax("/get/a"))
  var B = Bacon.fromPromise($.ajax("/get/b"))
  var combined = Bacon.combineTemplate({a : A, b : B})
  return combined
}).toProperty()

Here the combined property gets its value only when both A,B have returned a value.

[francescoagati]

Atomica update will be a feature of next releases of bacon.js?

[raimohanska]

Maybe. I'm still not sure about the implementation details. Also, I've got limited time to spend on this. Also, I don't need this myself right now. Will accept a well-tested-and-documented Pull Request of course :)

[raimohanska]

I'm wondering how important this is and to how many people.

The problem is that I don't think it will be possible to totally guarantee atomicity using the current (simple) internal design. Bacon.js uses internally the exact same mechanism as it provides for external subscribers, so it does not have, for instance, a dependency graph of the whole event network. This limits what we can do with regard to atomic updates. I'm planning to try something like the proposition above, but that will only guarantee atomicity in a graph comprised of Properties. So it would guarantee atomic updates in cases like the one in the description of this issue, but it wouldn't guarantee atomicity in case there are EventStreams in the graph.

So, a half-ass implementation might be doable with moderate effort, but a kick-ass one would require a grand re-implementation. I've got a gut feeling that even the half-ass one would satisfy most needs. What do you think?

[RoboTeddy]

I'm not familiar with the internals, but:

Might it be possible to infer dependent EventStreams without drastic changes, using a global context? e.g.,

  onValue: (f, args...) ->
    f = makeFunction(f, args)
    @subscribe (event) =>
      Bacon._parent = this
      f event.value() if event.hasValue()
      Bacon._parent = null

Bacon._addDependency = (child) ->
  # we now know that `child` depends on the current value of `Bacon._parent`

Contrived setup:

bus = new Bacon.Bus()
stream = new Bacon.sequentially(100, [1,2,3,4,5])
stream.onValue (val) -> bus.push(val+1)

Somewhere in EventStream or EventStream's dispatcher, we could call Bacon._addDependency(this). In this case, we'd then learn that bus depends on stream -- we might be able to build the dependency graph this way.

[acthp]

I think the critical issue here is that FRP implies a consistent view of time. You can get an inconsistent view of time just using callbacks. FRP is different than callbacks in just this way. If bacon isn't going to provide that, it's not FRP, it's something else. Flapjax and rxjs might provide examples. Flapjax uses a counter as timestamp to prevent pushing inconsistent data.

[raimohanska]

It might, in fact, make sense to dig into flapjax implementation to see how they've solved this.

My impression on RxJs, though, is that it has the most inconsistent view of time of all the FRP libs, as it's based on the Observable abstraction only. Or does it have atomic updates? Should try...

[raimohanska]

Whoa! Finally got something done. First, ugly draft exists in the atomic-updates branch. I'd be happy to have more tests for this.

[raimohanska]

Anyone interested in Atomic Updates? I'd be glad to get some feedback on the first implementation. It passes all automatic tests in the branch, but does it pass yours?

[acthp]

I hope to get back to this soon. I'm in server code for a couple more days, at least.

[raimohanska]

No problemo. I'd be very glad to get some feedback on this before going to master. And as I said, this is a very rough first draft, and I'll do some cleanup if it seems to work. Have fun with servers!

[raimohanska]

I re-implemented sampledBy combinator too to fix #161 in the atomic-updates branch. Would like to go to master with atomic updates. Still would like some external validation on this one. Would you like to try the atomic-updates version?

[RoboTeddy]

I can't comment on the implementation (I haven't had a chance to learn bacon's internals yet), but I just dropped atomic-updates into a decently-sized project that depends heavily on bacon, and nothing broke! 👍

[raimohanska]

Thanks Ted! I really appreciate that. Exactly what was needed. I'll try it on my "work" project too and if that works, i think I'll merge.

[desmond-dsouza]

The way Elm does this is:

• A node either propagates a new output value, or propagates special token UNCHANGED
• No node re-evaluates until ALL its inputs have been updated
• If all inputs to a node came in UNCHANGED, it propagates UNCHANGED
• All inputs (external) nodes are marked for re-evaluation (typically all except 1 will propagate UNCHANGED)

Elm currently prohibits cycles in the event graph.

[acthp]

I just tried it against my unit test again, but it's still failing. I won't swear I updated correctly. I did a git pull, checked-out out atomic-updates, and ran "coffee -c src/Bacon.coffee". I'm testing that there are no inconsistent states, where a combined stream has out-of-sync data from its dependencies. Here's the test. The third assert fails because the combined stream gets three updates when only two updates have happened.

'test no glitches': function() {
    var a = new Bacon.Bus();
    var b = a.map(function (v) { return "b" + v; }); 
    var c = Bacon.combineAsArray(a, b); 
    var cb = sinon.stub();
    c.onValue(cb);
    a.push(1);
    assertTrue(cb.calledOnce);
    assertEquals([[[1, "b1"]]], cb.args);
    a.push(2);
    assertEquals(2, cb.callCount);
    assertEquals([[[1, "b1"]], [[2, "b2"]]], cb.args);
},

[raimohanska]

@acthp the problem in your case is that a is not a Property, so atomic updates are not applied. So, the implementation is not perfect. It now just handles cases where the "root" is a Property. The perfect implementation would recognize the updates to a and b to be simultaneous. I'll think about it...

If you modify it to this, it will work (coffee/jasmine):

values = []
a = new Bacon.Bus();
ap = a.toProperty()
b = ap.map ((v) -> "b" + v)
c = Bacon.combineAsArray(ap, b)
c.onValue ((x) -> values.push x)
a.push(1)
expect(values).toEqual([[1, "b1"]])
a.push(2);
expect(values).toEqual([[1, "b1"], [2, "b2"]])

[raimohanska]

@des1303 that approach sound good, but not suitable for Bacon.js, where there's no concept of a Node. To apply the Elm approach, a complete internal redesign would be needed. Also, it might prove hard because in Bacon.js you can create new streams "on the fly" instead of defining the statically at start. Isn't this how you set up the "event network" in Elm?

[raimohanska]

Atomic Updates, with limitations, are now in master and included in release 0.4.0.