global roots?

[stevengj]

It looks worrisome that push! updates everything in a global roots array. This seems like it will scale badly.

Surely, pushing a value to an input should only affect the signals that depend on that input. Aren't you already storing the dependency DAG via the children field etcetera?

[stevengj]

In particular, it seems like a push! should trigger an update of all dependencies, processed exactly once each in dependency order (i.e. a topological sort of the dependencies).

This should also eliminate the awkward counting in the lift implementation (#2).

In general, it seems like the cost of push! should be Õ(# dependencies), whereas currently it is potentially far more expensive than that.

[stevengj]

As mentioned in #2, it seems like it would be more natural to get rid of all the recv functions and replace them with an update(s::Signal, parent::Signal) method that is overloaded as needed for each s::Signal type.

And don't even call update (née recv) if the parent was not changed ... what is the point?

[shashi]

Consider:

i = Input(0)
j = lift(x -> x^2, i)

k = lift(g, i, j)

when i gets updated, so does j. If I am not mistaken, even if I topologically sort inputs and update only specific root nodes like you have described, g gets called twice for a single update of i.

Do you see a not so awkward way of dealing with this?

[stevengj]

@shashi, no, you would topologically sort the inputs and all their descendants, with duplicates removed. In this case, that would result in the list [i, j, k]. Then you would call update (or whatever) on each of those signals, in order, and hence would update k exactly once.

[shashi]

Oh cool!!! That's awesome! On it!

[shashi]

@stevengj could you take a look at the pull request? I use a global counter to keep a topological ordering of nodes (if nodes are created only with the primitives provided, the logical time of their creation gives a complete ordering.)

To propagate a signal I do something like BFS but with a min-heap instead of queue: the lowest ranking child node always gets precedence. This is O(n*logn) worst case, which is asymptotically worse than it used to be, but should be much faster in practice than the previous. The average case should be much better, and in general should perform better than the previous design.

One problem I am facing is with merge. If merge has two inputs that update in the same timestep, then merge should guarantee that the left most signal gets the precedence. All implementations I can imagine destroy the elegance of the current code. I'm still thinking about this.

Edit: Merge is done. It doesn't look too bad to me. Doesn't affect the asymptotic time at least. All previous tests pass :D