dynamic dependencies

[danielepolencic]

Hi,

I can find references in the perf folder and some of the issues on Github about the dynamic dependencies.

I tried to play with a very basic dynamic dependencies, but it doesn't work. Also, I can't find any test.

var s1 = stream();
var s2 = stream();

var sum = stream(function () {
  return s1() + s2()
})

flyd.on(console.log.bind(console, 'sum'), sum);

s1(12);
s2(1)

// expected: 13
// got:
// sum function () {
//   return s1() + s2()
// }

is this feature still supported?

[paldepind]

@danielepolencic

The code in perf is definitely outdated. Which issue are you referring to? A very early version of Flyd had (almost) automatic and dynamic dependency tracking. I removed the feature since it turned out to have very limited usage.

It is still possible to create streams with dynamic dependencies. flyd-switchlatest for instance does this. But you will have to handle it yourself. What is your use case?

[danielepolencic]

This is the issue I was referring to.

I don't have a use case for dynamic dependencies, I was just interested in how flyd works. I was about to benchmark an implementation of flyd that computes the dependency graph ahead of time against the current runtime algorithm, when I realised that I didn't take into account dynamic dependency.

On a side note, computing dependency ahead of time seems to improve performance significatively.

static dependencies:
  New x 2,303,809 ops/sec ±0.53% (94 runs sampled)
  Old x 2,297,583 ops/sec ±0.45% (96 runs sampled)
  Alt (static graph) x 11,670,654 ops/sec ±0.67% (93 runs sampled)
  Alt (static graph) is 407% faster.

map:
  First x 844,201 ops/sec ±0.38% (97 runs sampled)
  Second x 856,267 ops/sec ±0.48% (99 runs sampled)
  Alt (static graph) x 4,084,794 ops/sec ±0.43% (96 runs sampled)
  Alt (static graph) is 384% faster.

[paldepind]

That sounds very interesting! Can you explain how you calculate the dependency graph ahead of time and how dynamic dependencies is a problem?

[danielepolencic]

You can checkout the poof of concept just here. When you run

cd perf
node perf.js

you should get the results I posted earlier.

In a nutshell, the idea is that the graph can be precomputed when a new stream is instantiated, rather than every time a new value is pushed into it.

You could:

• when a new stream is instantiated, save it in the dependency graph and recompute the topological graph.
• when a value is pushed into the stream, read the topological graph for that stream and execute each subsequent stream in order.

In theory you would get less garbage collection too (no need to recompute dependencies at every push).

Dynamic dependencies are tricky to express in that sense. You can't have the topological graph computed ahead of time.

[monfera]

@danielepolencic

| In a nutshell, the idea is that the graph can be precomputed when a new stream is instantiated, rather than every time a new value is pushed into it.

When learning about flyd, paring down the stream function to its bare essentials, about 20 lines, I also switched to precomputing the dependencies. (Since stream instantiation time was negligible either way, this also allowed a simpler, functional implementation instead of preserving the array growth and keeping an index that points to the end.) Specifically, each stream has an array which, in the proper order, contains everything that directly or indirectly depended on it.

Also, instead of keeping the dependent streams in the array, I kept only the updater function in the array. This saves yet another step of indirection, because in push time, you just blindly loop through an array, no need to check argument counts etc.

| Dynamic dependencies are tricky to express in that sense. You can't have the topological graph computed ahead of time.

While I'm not familiar with all design constraints, it appeared possible to precompute the dependents even if additional streams and dependencies are added dynamically (my use case didn't necessitate removals). Removal (dereferencing) would be more of a problem, but if it's not done in very large quantities, the ES2015 WeakMaps may solve the dereferencing issue but if a dereferenced dependent does anything imperative, it'll still be executed because of the unpredictable finalization time. So all in all, if the use case is mostly about creating and adding to a DAG, and maybe disposing of them en bloc rather than one by one, then precomputation works, otherwise there has to be a resource mechanism to do housekeeping on node removals.