baconjs/bacon.js — pull request #355 by skozin (2014-04-06 19:24:24+00:00)
Title: Fix/353 (invalidating dep cache)

The implementation of invalidating dependency cache mentioned in #353. Works like this:

* the cache manager keeps a set of ids of nodes with dirty cache (`DIRTY`);
* during each `dependsOn` call, the manager firstly checks whether the node's cache is dirty; in case it is, the manager re-collects dependencies of the node and removes it from the set of dirty nodes;
* for each node `P` the cache manager keeps a set of ids of (direct and indirect) children `CHILDREN_WITH_CACHE(P.id)` that have `P.id` in the dep cache;
* when deps of node `P` are changed, it and all its children from the `CHILDREN_WITH_CACHE(P.id)` set are added to the `DIRTY` set; after that the set `CHILDREN_WITH_CACHE(P.id)` is emptied;
* the cache of a new node is considered dirty.

Collecting dependencies:

1. start with an empty set `FLAT_DEPS(N)` where `N` is the node of interest;
2. add ids of all direct dependencies to the set `FLAT_DEPS(N)`;
3. for each direct dependency `DIRECT_DEP`, get (or recursively collect, if needed) ids of it's deps `FLAT_DEPS(DIRECT_DEP)` and add to the set `FLAT_DEPS(N)`;
4. for each dependency `DEP` in the set `FLAT_DEPS(N)`, add `N.id` to the set `CHILDREN_WITH_CACHE(DEP.id)`.

The pros:
* it is fast when dependency tree is immutable (costs one extra hashtable lookup during each `dependsOn` call);
* only affected subtree is re-calculated after dependency changes;
* dependencies of each node in the affected subtree are calculated only once between tree mutations;
* dependencies are calculated lazily.

The cons:
* it has a little extra cost compared to the immutable cache (see perf. test results);
* each `Observable` exports the `flatDeps` property that is visible from the outside but intended for internal use only; maybe it should be prefixed with underscore.

Performance tests:

master (immutable cache) | | |
-------|-------:|--------:|
diamond | 24.12 ops/sec | ±6.97% (36 runs sampled)
combo | 38.64 ops/sec | ±10.51% (39 runs sampled)
zip | 1,412 ops/sec | ±9.16% (84 runs sampled)
Bacon.combineTemplate.sample | 321 ops/sec | ±5.44% (82 runs sampled)
Bacon.combineTemplate (deep) | 18.25 ops/sec | ±4.51% (37 runs sampled)
Bacon.combineTemplate | 212 ops/sec | ±3.48% (86 runs sampled)
EventStream.map | 3,402 ops/sec | ±5.07% (83 runs sampled)
EventStream.scan | 3,142 ops/sec | ±4.93% (83 runs sampled)
EventStream.toProperty | 3,217 ops/sec | ±4.60% (81 runs sampled)

fix/353 (without cache) | | |
-------|-------:|--------:|
diamond | 9.85 ops/sec | ±6.66% (30 runs sampled)
combo | 39.89 ops/sec | ±7.57% (40 runs sampled)
zip | 1,445 ops/sec | ±8.67% (85 runs sampled)
Bacon.combineTemplate.sample | 325 ops/sec | ±5.18% (82 runs sampled)
Bacon.combineTemplate (deep) | 18.03 ops/sec | ±5.56% (40 runs sampled)
Bacon.combineTemplate | 208 ops/sec | ±3.52% (86 runs sampled)
EventStream.map | 3,411 ops/sec | ±4.46% (84 runs sampled)
EventStream.scan | 3,087 ops/sec | ±4.13% (88 runs sampled)
EventStream.toProperty | 3,154 ops/sec | ±3.75% (88 runs sampled)

fix/353 PR (invalidating cache) | | |
-------|-------:|--------:|
diamond | 19.44 ops/sec | ±6.46% (38 runs sampled)
combo | 41.62 ops/sec | ±4.23% (52 runs sampled)
zip | 1,330 ops/sec | ±3.95% (86 runs sampled)
Bacon.combineTemplate.sample | 313 ops/sec | ±4.19% (83 runs sampled)
Bacon.combineTemplate (deep) | 17.75 ops/sec | ±3.25% (49 runs sampled)
Bacon.combineTemplate | 208 ops/sec | ±2.75% (85 runs sampled)
EventStream.map | 3,216 ops/sec | ±4.15% (85 runs sampled)
EventStream.scan | 3,125 ops/sec | ±4.30% (86 runs sampled)
EventStream.toProperty | 3,144 ops/sec | ±4.13% (89 runs sampled)

There are many possible optimizations to this impl, but I think that the current performance is quite acceptable.