Improve worst case ephemeeron table collection speed

[Xmilia Hermit <xmilia.hermit@...>]

Hi,

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.

This will ensure that in the atomic phase all ephemeron tables are 
visited only one time and the number of keys in all ephemeron lists is 
bound by all ephemeron table nodes resulting in linear runtime.

However, to get this working the Udata0 optimization needs to be dropped 
as the Udata0 case does need space for a pointer to the first link in 
the list if it is an ephemeron key.

The implementation of this improvement can be found at 
https://github.com/XmiliaH/lua/tree/fast-ephemeron.

The following code shows the worst case behaviour:

local t1 = setmetatable({}, {__mode="k"})
local t2 = setmetatable({}, {__mode="k"})

local function make_long_chain(len, obj)
    while len > 0 do
        len = len - 1
        local k = {}
        t1[k] = obj
        obj = {}
        t2[obj] = k
    end
    return obj
end

local x = make_long_chain(10000, {})
collectgarbage("collect")
assert(next(t1) ~= nil)
x = nil
collectgarbage("collect")
assert(next(t1) == nil)

Regards,
XmiliaH