Hacker News new | past | comments | ask | show | jobs | submit login
Ephemerons explained (squeakfoundation.org)
30 points by kencausey on June 9, 2022 | hide | past | favorite | 11 comments



Modern JavaScript also supports ephemerons.

There it's the WeakMap type: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...

WeakMap prevents observing when the weakly referenced key objects are garbage collected. It does this by being deliberately non-enumerable (see the MDN link). So it may be considered missing part of the definition of ephemerons. It has the weak-key part without the finalizer part.

But modern browsers support WeakRef and FinalizationRegistry, which eventually reveal when objects have been garbage collected. https://v8.dev/features/weak-references, https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe... and https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...

So this part of the WeakMap design is just an annoying obstacle which can be worked around.

(Note, as FinalizationRegistry is designed to accompany WeakRef, it's intriguing that MDN lists Opera as supporting FinalizationRegistry but not WeakRef.)


That's a complete but quite a long explanation, and talks in terms of Squeak which I'm unfamiliar with. I'm much more familiar with JavaScript WeakMaps, where I would probably describe it something like:

A WeakMap M is a table of entries, each of which maps a key K to a value V. If you have the M and K in hand, you can use them to look up V. (And if you don't have either one, then you can't!)

From a GC perspective, each entry is an edge that says that V is alive if both M and K are alive[1]. (And if either of them dies, then the entry no longer serves to keep anything alive. Note the parallelism with the above parenthetical.)

They're mostly useful for associating a value V with some other object K without modifying K. They're sort of an annotation mechanism. If you tried to do that with a regular Map, then you would have to manually remove any Ks that you wanted to go away.

In implementation terms, ...y'know, why don't I write it up as a blog post: https://blog.mozilla.org/sfink/2022/06/09/ephemeron-tables-a...

[1] Note that WeakMaps are not "weak" in the sense of weak references; the name WeakMap is a bit of a misnomer. Normal weak things can be skipped during marking. After liveness is determined, you'll check to see if they're still alive. You can't skip ephemeron edges like this! They're strong edges and it's invalid to throw away a V if its M and K are live. But EphemeronTable is a bit long...


I clicked on this thinking it would be about philosophy but I was delighted to be once again thrust into Squeakland. God bless you Dan Ingalls!


Neat idea. Would moving the dependents list to an instance variable holding a weak array avoid the need for ephemerons here?


Where would the weak array be stored? Ephemerons are often used when you can't attach data directly to either the key object or the value object. It's the simplest efficient primitive that lets you encode "if object A is reachable, object B also is" without otherwise affecting the visibility of A (or B), altering A, or needing multiple GC cycles to settle.


Except that the implementation described in the post does use multiple GC cycles to settle if I read it correctly. It will only be an issue if you have reference cycles through ephemeron edges, though, like a key associated with a value that is itself or refers to an otherwise-dead WeakMap which contains a key associated with... etc.

Multiple cycles are not fundamental to ephemeron collection, though. If you keep all of your unmarked keys (specifically, keys of ephemeron tables that have been marked) in a lookup table, then in theory every time you mark anything you could look it up in that table to see if you need to traverse an ephemeron edge. In practice, you probably don't want to do those lookups until you've traversed the "easy" part of the heap that doesn't require traversing ephemerons to get to.

Source: that's how I implemented it in SpiderMonkey: https://searchfox.org/mozilla-central/rev/552bfc6334b797d92f...


On the instance. My understanding is that in this example, the instance itself is the key and is only stored in a dictionary owned by the related class. Maybe there are other or broader use cases, but for this particular case, storing dependents on the instance seems to (AFAICS) solve the problem without adding complexity.


Agreed. If the dictionary is owned by the related class, and classes aren't collected themselves, then there's no point in using an ephemeron table. From a GC perspective, an ephemeron table entry can be seen as a tuple <M, K, V> where V is alive if both M and K are alive. Sort of a strong edge to V from the conjunction of M and K. (A regular strong edge is a tuple <K, V> where V is alive if K is alive.) So if the ephemeron table M is known to be alive, then it collapses down to a regular strong edge, the simplest forms of which are plain properties or dictionaries mapping Ks to Vs.


I have to admit, given the obviousness of that solution, I decided that they must have some constraint we don't know preventing it. I don't know why they didn't use it here. The broader design and use-cases have been better described by sfink in these threads.


AKA, a single entry in a WeakKeyDictionary


Well, WeakMap implementations (like WeakKeyDictionary) that don't delay GC significantly do indeed use ephemerons.




Join us for AI Startup School this June 16-17 in San Francisco!

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: