Weak Graph

[Isiah Meadows]

I don't think that's possible with traditional GC. If you can find an
existing implementation in a GC language (like Java) that has the behavior
you want, I'll be interested. Otherwise, the only way is explicit garbage
collection.

On Wed, Nov 4, 2015, 11:34 Jussi Kalliokoski <jussi.kalliokoski at gmail.com>
wrote:

> 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/20151105/bee55d61/attachment.html>