Re: linear-time weak-map gc

2011-03-22 Thread felix
On Sun, Mar 20, 2011 at 8:14 AM, Jason Orendorff jason.orendo...@gmail.com wrote: On Sun, Mar 20, 2011 at 5:12 AM, felix feli...@gmail.com wrote: I haven't tried implementing this, so no idea how well it works in practice. I thought of this. It would definitely work. However, it requires an

linear-time weak-map gc

2011-03-20 Thread felix
so, the gc algorithm described at   http://wiki.ecmascript.org/doku.php?id=harmony:weak_maps#abstract_gc_algorithm has a worst-case runtime of O(L+W*W) where L is the number of live objects, and W is the number of entries in live weak maps. O(W*W) happens because the algorithm scans all weak-map

Re: linear-time weak-map gc

2011-03-20 Thread David Herman
Hi Felix, I have a note on the wiki page offering a less algorithmic approach to specifying weak maps. I don't think we should be putting GC algorithms in the spec at all; that would be overspecification. Instead, we should just focus on defining reachability, and leave implementors free to

Re: linear-time weak-map gc

2011-03-20 Thread Jason Orendorff
On Sun, Mar 20, 2011 at 5:12 AM, felix feli...@gmail.com wrote: I haven't tried implementing this, so no idea how well it works in practice. I thought of this. It would definitely work. However, it requires an extra conditional branch for each object marked by the GC. So relative to the

Re: linear-time weak-map gc

2011-03-20 Thread David Herman
Come to think of it, evaluating implementations for proper tail calls is a little easier, at least in implementations with fixed-size stacks and stack overflow exceptions. I'm not quite sure how you write weak map tests that check memory consumption, unless implementations expose heap size

Re: linear-time weak-map gc

2011-03-20 Thread David Herman
Fair enough -- just interpret my email as an aside. :) Dave On Mar 20, 2011, at 8:57 AM, Mark S. Miller wrote: Hi Dave, I think you misunderstand the purpose of posting this algorithm. Before Felix's algorithm, to the best of my knowledge all documented and/or implemented ephemeron

Re: linear-time weak-map gc

2011-03-20 Thread Allen Wirfs-Brock
typically this is seen as a quality of implementation issue. Note the we (and most other language specs.) don't say much (or anything) about GC in general. In one sense we don't need to say anything else about WeakMaps because it would be a lower quality implementation to retain objects in one

Re: linear-time weak-map gc

2011-03-20 Thread Oliver Hunt
On Mar 20, 2011, at 6:53 PM, David Herman wrote: typically this is seen as a quality of implementation issue. Note the we (and most other language specs.) don't say much (or anything) about GC in general. In one sense we don't need to say anything else about WeakMaps because it would be