 |
lua-l archive |
|
|
||
|
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: http://www.inf.puc-rio.br/~roberto/docs/ry08-06.pdf
In Code-4's function traverseephemeron(e) shouldn't 3: if key(pair) is marked then be 3: if key(pair) is marked and value(pair) is not marked thenotherwise 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.
e