lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

On Dec 18, 2008, at 6:09 AM, Roberto Ierusalimschy wrote:

The problem with inside-out objects is the susceptibility to weak-
table-based cycles. I gather those are being addressed in 5.2, but I
don't know at what cost.

The paper about it has some cost estimates:

In Code-4's function traverseephemeron(e)


3: if key(pair) is marked then


3: if key(pair) is marked and value(pair) is not marked then

otherwise traverseephemeron(e) will always return true for tables with any marked keys, and convergeephemerons(ephemeron) will never terminate.

Basically, the costs are low unless you do something weird (such as a
long chain of key1->value1->key2->value2->...).

Regarding quadratic behavior in the worst case, is it worth exploring/ mentioning the algorithm Hayes mentions in his paper ([Hayes 1997] Hayes, B.: “Ephemerons: a New Finalization Mechanism”; In Proc. of the 12th ACM SIGPLAN Conference on Ob ject-Oriented Programming, Systems, Languages, and Applications, New York, NY (1997), 176–183.)?

Ephemerons can be recovered in time strictly pro-
portional to the number of ephemerons. To do this,
build distinct delay queues for each unique key that
has not yet been visited. When the trace encounters
an ephemeron, if the key has already been traced,
there will be no delay queue, and’the ephemeron
should be traced immediately. If the key has not
been traced, there will be a delay queue and the
ephemeron should be enqueued.
When any object which is a key for some delayed
ephemerons is found to be reachable, its associated
queue of delayed ephemerons should be traced at
that time, and the queue deleted.