solid: Duplicate edges in signal graph

If I understand correctly, when signal value is accessed, it doesn’t perform a check when the edge already exists:

Accessing current() value: https://github.com/ryansolid/solid/blob/8fe0c11360387a325d64e040a756585a69f6da63/src/signals.ts#L189-L192
Creating an edge: https://github.com/ryansolid/solid/blob/8fe0c11360387a325d64e040a756585a69f6da63/src/signals.ts#L405-L439

Without such checks, use cases that involve sorting/filtering in data tables will create insanely huge graphs.

For example, simple sort() on 5000 items will create ~110000 edges:

let i = 0;

class Item {
  _a = Math.random();

  get a() {
    i++;
    return this._a;
  }
}

const items = [];
for (let i = 0; i < 5000; i++) {
  items.push(new Item());
}

items.sort((a, b) => a.a - b.a);
console.log(i);

About this issue

Original URL
State: closed
Created 5 years ago
Reactions: 1
Comments: 32 (6 by maintainers)

Commits related to this issue

Add observable duplicate edges check #20 This prevents the most cases of duplicate edges like when observables are accessed in a `sort` for example explained here https://github.com/ryansolid/solid/is... — committed to luwes/sinuous by luwes 5 years ago

Most upvoted comments

Thanks, everyone for this discussion. It actually ended up productive in the end. Did simple last edge detection here. And will look at more sophisticated methods in the future.

ryansolid on Jul 31, 2019

@luwes I think that it is possible to get rid of all duplicates from observables to computeds at the cost of one additional property on observables, also it can improve reset performance (in most cases it won’t be necessary to remove edges from observables to computed).

When computed is executed, create a new execution id nextId++ and store it in the execution context(on stack) of this computed.
When observable is accessed - push a new entry to the array of dependencies (computed -> observable) and assign computed execution id to observable lastAccessedBy to perform a simple check for duplicates.
When computed is finished executing, iterate over all dependencies and refresh all lastAccesedBy to prevent edge cases when nested computeds could overwrite it.
Iterate over old dependencies and remove observable->computed dependencies that have lastAccessedBy !== computed execution id. When observable is removed, assign lastAccesedBy to -1, if it still should remain in the list, assign -2.
Iterate again over new dependencies and add observable->computed edges that doesn’t have -2 in lastAccessedBy.

Just an idea, maybe I’ve missed something, maybe it isn’t worth it 😃

EDIT: Also, it is possible to detect when there aren’t any nested computeds by checking that nextId isn’t greater than current execution id + 1. And when there aren’t any nesteds, we can skip step3.

EDIT2:

In step4 it is actually unnecessary to mark removed nodes with -1
In many cases we can also skip step5 by counting how many observable->computed should stay alive in step4 and then just comparing it with the length of new dependencies array (this optimization probably won’t work when we detect nested computeds).

localvoid on Jul 29, 2019

I don’t usually find it productive to respond to Boris, but for Ryan’s benefit and anyone else interested, I benchmarked this design decision pretty thoroughly back when I made it. De-duping edges during creation requires a hashtable or Set, and at the speeds we want, those are both slow. Or at least they were when I was doing the benchmarking. At the time, a basic read ran about 300% slower. The relevant metric isn’t number of edges but number of reads. It was considerably faster overall to create a duplicate edge than to detect whether it was a duplicate. That was still true even if I accounted both for the time to traverse the extra edges during update and for the extra GC time of creating/freeing the larger arrays of dependencies.

In fact, this, plus the fact that the S data structures were designed not to need try/finally statements in the update loop, were where S got most of its speed over other reactive libraries.

@leeoniya it was a while ago that I looked at cellx. At the time, the try/finally statements in its core loops gave S a considerable advantage. That was before turbofan made try/finally optimizable, though, so the picture may have changed since then.

adamhaile on Jul 23, 2019