lua-users home
lua-l archive

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


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

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
    return obj

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