Weak Graph

[Jussi Kalliokoski]

On Wed, Nov 4, 2015 at 6:19 PM, Isiah Meadows <isiahmeadows at gmail.com>
wrote:

> Would this be possible with a mixture of weak references and weak
> collections?
>

I don't think so - the only potential implementation I can think of would
make a weak reference to the parent which would allow the parent to be
GCed, but then all the nodes between the latest revision and the ancestor
would require strong references somewhere in order to be maintained, making
the whole thing kinda pointless because you couldn't rely on it working.
Also this use case doesn't require making GC observable, which I think is
pretty much the only feature of weak references that WeakMaps don't provide.

- Jussi


>
> On Wed, Nov 4, 2015, 11:09 Jussi Kalliokoski <jussi.kalliokoski at gmail.com>
> wrote:
>
>> Usually my first assumption when I think I need weak references is that I
>> should use WeakMaps instead. Today I came across an interesting use case
>> and was wrong for the first time. However it wasn't weak references I
>> needed either.
>>
>> I'm trying to come up with a solution to the problem of rendering lists
>> that's often used as a counter argument for using a framework / view
>> library instead of direct DOM manipulation, where - even with React -
>> updating (even appending to) a list is O(n) at best.
>>
>> My idea for a solution is that the lists are immutable, contain a
>> reference to their parent and a changeset / diff compared to their parent.
>> This would allow rendering the whole list initally, then just applying the
>> diffs on subsequent renders by walking the graph up to the last known
>> ancestor and combining the changesets. This would make subsequent renders
>> O(1) which is a great improvement even with small lists.
>>
>> The biggest problem is that this will leak memory like crazy; every
>> revision of the list will be preserved. Let's say we have the following
>> implementation:
>>
>> ```JS
>> function WeakGraph () {
>>     const parentByNode = new WeakMap();
>>
>>     this.getLineage = function (node, ancestor) {
>>         const lineage = [];
>>
>>         let currentNode = node;
>>         do {
>>             lineage.push(currentNode);
>>             if ( !parentByNode.has(currentNode) ) { throw new Error("node
>> is not a descendant of ancestor"); }
>>             currentNode = parentByNode.get(currentNode);
>>         } while ( currentNode !== ancestor );
>>
>>         return lineage;
>>     };
>>
>>     this.addNode = function (node, parent) {
>>         parentByNode.set(node, parent);
>>     };
>> }
>> ```
>>
>> It provides the needed interface and the unused child revisions get
>> cleaned up properly. However:
>>
>> * This is a complete nightmare for GC performance because of cyclical
>> weak references.
>> * Any reference to a child will maintain references to all its parents.
>>
>> However this doesn't necessarily need to be the case because the stored
>> ancestry is not observable to anything that creates a WeakGraph, except to
>> the oldest ancestor that has a reference elsewhere.
>>
>> I'm not sure if this use case alone warrants adding a new feature to the
>> language, or if I'm just missing something and it can be implemented with
>> existing constructs or if there should be some other lower level primitive
>> that would allow building a WeakGraph on the user level.
>>
>> - Jussi
>> _______________________________________________
>> es-discuss mailing list
>> es-discuss at mozilla.org
>> https://mail.mozilla.org/listinfo/es-discuss
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/es-discuss/attachments/20151104/634ecd98/attachment.html>