Ephemerons - hope it is right this time :)

 
I have corrected implementation, hope it is right this time :)

If Ephemeron's key is almost-collectable (reachable only by ephemeron itself),
then it is reported to image side.
Then VM continues tracing ephemeron as object with all strong slots,
and if there are other ephemerons
which need to be reported as well, same procedure will be done for them.
It will loop until no other ephemerons with almost-collectable keys
can be found and nothing left to be traced.

See
http://code.google.com/p/cog/issues/detail?id=44

for the code.

(I will upload the VMMaker package with changes now).

--
Best regards,
Igor Stasenko AKA sig.

There is one slight thing, which i had doubts about.
Initially, when i was revising the algorithm, i followed the same road
as in paper:
"
In the third phase, the collector traces the remaining objects,
beginning at the ephemerons still on the queue. Any ephemerons
encountered in this phase are treated as ordinary objects, and all
fields traced’.
"

It means that VM will report only the topmost ephemerons (which has
keys non-reachable from roots),
but not consider ephemerons which are reachanble from those ones,
which will be discovered later, when queue will be processed.

The difference is, whether VM should also report nested ephemeron or not.
Consider a following test:

testNestedEphemerons

        " test that we will get a notification from nested ephemeron"
       
        | e key key2 val list count |

        list := WeakFinalizationList forEphemerons.

        e := Ephemeron newForList: list.

        key := Object new.
        key2 := Object new.

        e key: key value: (
                Array with: (
                (Ephemeron newForList: list)
                        key: key2 value: 1@2 )
        ).

        key := key2 := nil.
        Smalltalk garbageCollect.

        count := 0.
        list finalizationAction: [:eph | count := count + 1].
        list finalizeValues.
       
        self assert: count = 2
       

Here, the top ephemeron (e)
should be reported as one which having almost-collectable key.
But then VM has to mark its fields (otherwise they will be lost, and
we don't want that before image can handle it),
and discovers a nested ephemeron.
But nested one also has its key almost-collectable.
So, here the difference: should VM trace this ephemeron as usual
object (with all slots as strong references, like paper says),
or it should also report this ephemeron as one with almost-collectable key.

By following a paper description, at this stage, a nested ephemeron
should not be reported (so, in above test , a resulting count must be
== 1, but not 2).

This is quite obscure case (usually ephemerons not form a nested
loops), since then it is a question, which one should be finalized
first, and which one second.
So, for most use cases, this difference will not affect anything.
But if this will happen, it may lead to situation, that nested
ephemeron won't be finalized, so you could forget to free external
resources etc.
That's why i think, its better to report even nested ephemerons.
Otherwise if you finalize the topmost ephemeron and set its key (or
values) to nil,
then there will be no other references to nested ephemeron and it will
be garbage collected without any notice.
But if we report it, then image side can decide if it needs to be
finalized or not, regardless that the only reference to given
ephemeron are coming
from another ephemeron , which also needs to be finalized.

--
Best regards,
Igor Stasenko AKA sig.

 
Hi Igor,

 
Hi Igor,

On 2 June 2011 21:38, Eliot Miranda <[hidden email]> wrote:
> And that reminds me, in your implementation how is an object marked as being an ephemeron?  Is it a header bit or does it depend on a class?

i didn't wanted to add new special object, so to tell if given object
as ephemeron there are multiple checks:
  - an object has weak slots
  - an object has at least 2 inst vars
  - first inst var points to an instance of ClassWeakFinalizer
the above conditions are same as for weak finalization scheme which i
introduced before.
Now, if instance of ClassWeakFinalizer has 2nd instance variable == true, then
the object in question is ephemeron.

(the list of conditions is a bit long, but i just don't want to add
new special object(s), and actually the overhead is not that much ;)

Btw, i think that i found a generic "object markers" scheme, which
allows to mark an object as a special one, but dont put too much
constraints to the object itself:
imagine that an object is special, if its first ivar points to an
instance of ClassSpecialObject
and then that instance could also contain an instance variable, like a
small int number , which denoting, what kind of special object it is.

With such markers, we easily could have 2^31 various kinds of special
objects, without need of extending special objects array at all.
Another way is to use unique instances of ClassSpecialObject to denote
a kind of special object. But then image side needs to have a
registeration mechanism and communicate with VM for registering them.
Anyways,by putting in a first inst var an instance of
ClassSpecialObject, it quite cheap to check then, if given object is a
"special one".

> If it depends on a class that's an unsatisfactory, but acceptable limitation, since we can't create different types of ephemeron for different tasks.

As you can see from the list of conditions above, you can use any
class for ephemeron. Or just subclass Ephemeron class, which is what i
expect will be most often used.

> Instead, if we want different mourn behaviours they have to be based on some mapping from ephemeron to something else, such as the >dictionary an ephemeron is in (ephemerons are specifically designed to look like Associations so they can liv comfortably in Dictionaries).

Sure, at image side there is a way to decide how to mourn ephemerons
one way or another.
VM are not participating in it (it just reports ones), so there is
virtually nothing which prevents you from implementing various
mourning actions.

My implementation allows to have ephemerons with any number of
variable slots >= 1 , means:
key only
key and value
key and many values , as many as you want

> HTH
> Eliot
>

--
Best regards,
Igor Stasenko AKA sig.

On 2 June 2011 21:44, Eliot Miranda <[hidden email]> wrote:
Yes, i felt that this "third" phase are not quite consistent with
purpose of ephemerons.
And moreover, i think , its not hurts to report something in advance
to what one expecting.
It's much worse when you don't receive a notification, when you expecting it.

Kewl. Then i made right decision, despite that paper says don't :)


--
Best regards,
Igor Stasenko AKA sig.