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?
_______________________________________________
es-discuss mailing list
[email protected]
https://mail.mozilla.org/listinfo/es-discuss
