Weak Graph

Isiah Meadows isiahmeadows at gmail.com
Wed Nov 4 16:19:19 UTC 2015


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

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/11983ebe/attachment-0001.html>


More information about the es-discuss mailing list