[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: Possible Lua enhancements (mostly for private data)
- From: Doug Currie <doug.currie@...>
- Date: Thu, 18 Dec 2008 17:58:00 -0500
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.