Re: Improve worst case ephemeeron table collection speed

[Roberto Ierusalimschy <roberto@...>]

> the current implementation of ephemeron table collection can show a
> quadratic time behaviour (as seen in the code below) due to the repeated
> visits of ephemeron tables in convergeephemerons until a fixpoint is found.
> This can be improved to linear time by linking all ephemeron table nodes of
> the same key into a list pointed to from the ephemeron key.
> This linking is only done in the atomic phase. When an ephemeron table is
> visited and a white key is found it is marked as an ephemeron key and the
> node from the table is linked into this list by overriding the value
> pointer. The node is also cleared my making the value tag nil and the key
> tag a dead key. This helps to remove the need to find and clean up dead
> nodes in cases where the key is dead in the end.
> When an object is marked and it is an ephemeron key all nodes in the list
> are restored by resetting the key and value tags and restoring the value
> pointer. Furthermore, all values in the nodes are marked upholding the
> invariant.

The worst-case quadratic behaviour for ephemeron tables has been known
since the idea was first proposed [1]. This seems an interesting
idea to solve it. I have some questions about your description:

- When an object is marked, how to know whether it is an ephemeron key?

- Where does it link the nodes in the key? You mentioned an issue
with Udata0, but even in other userdata (plus other objects like
tables and functions) is there free space for another pointer?

- How does it restore the tag of the value?

- Currently, Lua assumes that a dead key keeps its original gcvalue.
This proposal seems to break that: If the key is never marked, its
gcvalue will not be restored. Is that so? Maybe Lua does not need
that assumption?


[1] https://www.jucs.org/jucs_14_21/eliminating_cycles_in_weak/jucs_14_21_3481_3497_barros.pdf

-- Roberto