Weak Graph

Steve Fink sphink at gmail.com
Fri Nov 6 23:29:33 UTC 2015


On 11/04/2015 08:09 AM, Jussi Kalliokoski wrote:
> 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.

Not necessarily. Current Spidermonkey should handle it ok, using a 
linear-time algorithm for weakmap marking. (I think an inverted 
representation would also be good for this? I haven't thought it through.)

> * 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.

The brute-force approach would be to give each node its own weakmap, and 
add an entry for *every* ancestor:

```JS
this.getLineage() = function (node, ancestor) {
   const lineage = [];
   while (node) {
     lineage.push(node);
     if (node == ancestor)
       return lineage;
     node = node.parentForAncestor.get(ancestor);
   }
}

this.addNode = function (node, parent, ancestor) {
   node.parentForAncestor = new WeakMap();
   for (let key of this.getLineage(parent, ancestor))
     node.parentForAncestor.set(key, parent);
};
```

...but notice that addNode now requires an ancestor to be specified, and 
it will only work as far back as that. And of course, this defeats the 
whole point of the exercise, in that it requires space quadratic in the 
number of live nodes. And insertion is linear in the distance from the 
node to the chosen ancestor. Which could still be a win in rare cases, I 
guess, but my point is only to show that the leak could be "fixed".

I should note that in your example, you have a WeakMap with basically 
infinite lifetime. That means that keys always hold values live, in 
which case you might as well store them directly as properties on the 
key (node.parent = parent).

I also pondered what language primitives would fix this case. The 
straightforward approach is to expose something tailored specifically to 
this use case -- call it a WeakList. You cannot look up elements by 
index. You can call WeakList.prototype.get(begin, end) and it will 
return an Array of elements from begin..end (where 'begin' and 'end' are 
actual elements of the list), or undefined if either begin or end is not 
present in the list. Internally, the implementation would allowed to 
discard all leading and trailing dead elements. It would be stored as a 
dag to share space with overlapping lists.

A totally different option is something I'm calling a VagueMap. I should 
mention here that I don't know of any prior art, nor have I looked for 
any, so my apologies if this is known by another name. A VagueMap is 
sort of the dual of a WeakMap, where the value keeps the entry (and key) 
alive rather than the key keeping the value alive. But to avoid exposing 
GC behavior, you cannot just look up values by key (since then if you 
wanted to know when something gets GC'ed, you'd just stick it in a 
VagueMap under a well-known key and look it up periodically.) Instead, 
get(key) returns a "vague value", which can only be used in two ways: 
for equality testing, and as a VagueMap key. VagueMap lookups would 
treat vague values and their equivalent non-vague values identically. 
VagueMap would also support has().

Note that VagueMap does not automatically keep its keys live (as in, 
only the ones with live values will be kept live.) So you still can't 
iterate over the keys.

This still doesn't fix the original example. The simple replacement of 
WeakMap with VagueMap will "work", but getLineage() will return an array 
of vague values, which aren't much use. So I'll need to add another 
funky feature to VagueMap: if you give it a (non-vague) value, it will 
hand you back the non-vague, guaranteed live, key. I'll call it 
VagueMap.prototype.getKey(vkey, value) where vkey is a possibly-vague 
key that maps to value.

We get back very close to the original code, with an added loop to reify 
the vague nodes (oh, and I include the ancestor in the lineage -- which 
means the do/while loop could now easily be a for loop, but I'll stick 
close to the original):

```JS
function WeakGraph () {
     const parentByNode = new VagueMap();

     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 );
         lineage.push(ancestor);

         for (let i = lineage.length; i > 1; i--) {
             lineage[i-2] = parentByNode.getKey(lineage[i-2], lineage[i-1]);
         }

         return lineage;
     };

     this.addNode = function (node, parent) {
         parentByNode.set(node, parent);
     };
}
```

Given the number of failed attempts I've taken at this today, there's 
probably some very obvious problem with all of this. But I *think* this 
all checks out now?



More information about the es-discuss mailing list