Would this be possible with a mixture of weak references and weak collections?
On Wed, Nov 4, 2015, 11:09 Jussi Kalliokoski <[email protected]> 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 > [email protected] > https://mail.mozilla.org/listinfo/es-discuss >
_______________________________________________ es-discuss mailing list [email protected] https://mail.mozilla.org/listinfo/es-discuss
