技术说明 8
6 分钟阅读
Technical Note 8 技术说明 8
Last update: Mon Aug 12 15:51:45 EST 2002
A fast multiple-inheritance tag method implementation in Lua - 用 Lua 实现的快速多重继承标记方法
by David Jeske
Abstract
This note explains a multiple-inheritance style class system based on Lua’s tag methods which provides performance similar to languages such as Python.
本说明解释了基于 Lua 标记方法的多重继承样式类系统，该系统提供了类似于 Python 等语言的性能。
The Problem
Sometimes it’s desirable to have an inheritance style class system to compose Lua objects. A default single-inheritance scheme dubbed “Inheritance via fallbacks” [1] is proposed in a short article on using Lua. However, as inheritance chains become long, the time to process repeated lookup walks up the parent chain used by this implementation can become undesirable. In addition, sometime it’s convenient to have multiple-inheritance in addition to single inheritance.
有时需要一个继承样式类系统来组合 Lua 对象。一篇关于使用 Lua 的短文中提出了一个名为“通过回退进行继承”[1]的默认单继承方案。但是，随着继承链变长，此实现中使用的重复查找遍历父链所花费的时间可能变得不理想。此外，有时除了单继承之外，还需要多重继承。
The Solution 解决方案
A tag-method inheritance scheme is proposed which provides single and multiple inheritance, and whose implementation drastically speeds up access to inherited data and functions by caching them in a flat hash-table similar to the way languages such as Python flatten inheritance into a single table. This optimized version of the machinery assumes that you will not change base-class methods at run-time.
提出了一种标记方法继承方案，该方案提供了单继承和多重继承，并且其实现通过将继承的数据和函数缓存到类似于 Python 等语言将继承扁平化为单个表的平面哈希表中，从而极大地加快了对继承的数据和函数的访问速度。此优化的机制版本假设您不会在运行时更改基类方法。
The non-caching implementation is rather simple. It uses a _parents = {} member in a table to create an inheritance chain.
非缓存实现相当简单。它在表中使用 _parents = {} 成员来创建继承链。
-- ********************************************************
-- index tag method AdvProtoIndex(t,f)
--
-- This is a 'simple' version of the multiple inheritance
-- tag method. It does not cache and thus it is quite slow.
-- However, if you think something strange is happening, you
-- can fall back to this version and see if the strangeness
-- goes away.
function AdvProtoIndex (t,f)
if f == '_parents' then -- to avoid loop
if (OldIndex) then
return OldIndex(t,f)
else
return nil;
end
end
local p = t["_parents"];
if (type(p) == 'table') then
local cur_index = 1; -- start at 1
local cur_data;
repeat
cur_data = p[cur_index];
if (type(cur_data) == 'table') then
local result = cur_data[f];
if (result ~= nil) then
return result; -- we found a match
end
else
if (OldIndex) then
return OldIndex(t,f);
else
return nil;
end
end
cur_index = cur_index + 1; -- do next parent
until (cur_data == nil);
return nil; -- we didn't find a match
else
return nil;
end
end
I normally setup this fallback tag method for all-tables, which means that creating inheritance is as simple as creating tables with the appropriate members:
我通常为所有表设置此后备标记方法，这意味着创建继承与创建具有适当成员的表一样简单：
a_base = {
a_number = 1
}
b_base = {
b_number = 2
}
ab_class = {
_parents = { a_base, b_base }
}
print(ab_class.a_number); -- yields "1"
print(ab_class.b_number); -- yields "2"
Using the simple implementation above, it’s easy to create inheritance chains which severely impact run-time performance, because an inherited method call or instance data access can result in 2n lookups, where n is the number of base classes inherited from in the whole chain.
使用上述简单实现，很容易创建严重影响运行时性能的继承链，因为继承的方法调用或实例数据访问可能导致 2n 查找，其中 n 是整个链中继承的基本类的数量。
A performance optimized implementation is provided which functions the mostly same but is drastically faster.
提供了经过性能优化的实现，其功能基本相同，但速度大大提高。
----------------------------------------------------------
-- AdvProtoIndexWithCache
--
-- This inheritance tag method handles multiple inheritance via a
-- "_parent = {}" table. It caches information in the top-level table
-- to make lookups fast.
--
-- Example:
--
-- This tag method is applied to all tables, so all you have to do to
-- get a magic inheritance table is to do this:
--
-- BaseObj1 = { a_value = "a" }
-- BaseObj2 = { b_value = "b" }
-- MyClass = { _parents = { BaseObj2, BaseObj1 } }
-- MyInstance = { _parents = { MyClass }
--
function setupMultipleInheritenceForTag(a_tag)
-- I like to setup my tag methods within a function because
-- then stuff like these private declarations can be
-- referenced with upvalues and disappear. :)
local NIL_OBJECT = { magic_nil_object = 1}
local SLOT_REF_TAG = newtag()
local OldIndex = gettagmethod(tag({}),"index")
local debug_mode = nil
AdvProtoIndexWithCache = function (t,f, instance, depth)
if (f == '_parents') or (f == '_slotcache') then -- to avoid loop
if (%OldIndex) then
return %OldIndex(t,f)
else
return nil;
end
end
if instance == nil then
-- we are the instance!
instance = t
end
if depth == nil then
depth = 0
end
-- get out the parent table
local p = rawgettable(t,"_parents")
local cache = rawgettable(instance,"_slotcache");
if cache then
local item = rawgettable(cache,f)
if item then
if item == %NIL_OBJECT then
return nil
elseif tag(item) == %SLOT_REF_TAG then
return item.obj[f]
else
return item
end
end
else
-- if we are the instance AND we had a _parents
-- slot, then create the slot cache!
if (instance == t) and (p) then
cache = {}
rawsettable(t,"_slotcache",cache); -- make the slot cache!
end
end
if (type(p) == 'table') then
local cur_index = 1; -- start at 1
local cur_data;
repeat
cur_data = p[cur_index];
if (%debug_mode) then
print("---------", cur_index, depth)
end
if (type(cur_data) == 'table') then
if (%debug_mode) then
printTables(cur_data)
end
-- local result = cur_data[f];
local result = rawgettable(cur_data,f);
if (%debug_mode and (result ~= nil)) then
print("value: ", result)
end
-- if we found the slot in us, then we need
-- to do the caching, because after we return
-- it's not possible to make a SLOT_REF
if ((result ~= nil) and (cache)) then
rawsettable(instance,f,result);
end
if (result == nil) then
result = AdvProtoIndexWithCache(cur_data,f,instance, depth + 1)
end
if (result ~= nil) then
if (%debug_mode and (result ~= nil)) then
print("value: ", result)
end
return result; -- we found a match
end
else
local result
if (%OldIndex) then
result = %OldIndex(t,f);
else
result = nil;
end
if cache then
if (type(result) == "function") then
rawsettable(cache,f,result);
elseif result == nil then
rawsettable(cache,f,%NIL_OBJECT)
else
local slot_ref = { obj = cur_data }
settag(slot_ref,%SLOT_REF_TAG);
rawsettable(cache,f,slot_ref);
end
end
return result; -- we found a match
end
cur_index = cur_index + 1; -- do next parent
until (cur_data == nil);
if cache then
rawsettable(cache,f,%NIL_OBJECT)
end
return nil; -- we didn't find a match
else
return nil;
end
end
settagmethod(a_tag,"index",AdvProtoIndexWithCache); -- Lua 3.1 method
end
Explanation
The final implementation uses a “_slotcache” table which is creates in any target of a method call. Anytime a method lookup via the _parents multiple inheritance machinery results in a positive lookup, the result is stored in the original target’s “_slotcache”.
最终实现使用 “_slotcache” 表，该表在方法调用的任何目标中创建。通过 _parents 多重继承机制进行方法查找时，如果结果为正查找，则将结果存储在原始目标的 “_slotcache” 中。
In the cache, functions are pointed to directly, and other items are pointed to using something called a “SLOT_REF”. A SLOT_REF is a special kind of table which is a cache by reference instead of by value. It contains a reference to the table and index of the original value so that if the original data value changes, this SLOT_REF will correctly point to the new data-value. This is not done for methods, because it was decided that performance of method lookups is more important than retaining the ability to change methods in base-classes.
在缓存中，函数直接指向，而其他项使用称为“SLOT_REF”的东西指向。SLOT_REF 是一种特殊类型的表，它是一种按引用而不是按值进行缓存的表。它包含对原始值的表和索引的引用，以便在原始数据值发生变化时，此 SLOT_REF 将正确指向新的数据值。对于方法，不会执行此操作，因为已决定方法查找的性能比保留在基类中更改方法的能力更重要。
Another implementation of this machinery could be even faster by doing away with SLOT_REF, and instead using some method to invalidate slotcaches (such as maintaining a reverse-slotcache dependency list). Whenever a base-class method or function was changed, the reverse dependency chain’s slotcaches would be invalidated. This would probably result in only moderate extra data-keeping if the “_slotcache” were changed to occur at the “class” level of the object instead of the “instance” level as it does now.
通过取消 SLOT_REF，而是使用某种方法使 slotcache 无效（例如维护反向 slotcache 依赖项列表），可以使此机制的另一种实现更快。每当更改基类方法或函数时，反向依赖链的 slotcache 将失效。如果将“_slotcache”更改为在对象的“类”级别而不是像现在这样在“实例”级别发生，这可能会导致仅适度的额外数据保留。
Weaknesses 缺点
Because nil in Lua is overridden as the meaning for both false and an absent data-value, some trickery was added to correctly cache inherited nil values. Without this, any instance data or method which is intended to be either missing or false causes the expensive _parents lookup to occur each time. Since the assumption is made that base classes will never be changed, this is a safe optimization. Even when a ‘cached NIL’ value is present in the _slotcache, setting an instance member to some other value will override the ‘cached NIL’, because the _slotcache is only consulted when lookup in the instance table misses.
因为 Lua 中的 nil 被重写为 false 和不存在的数据值的含义，所以添加了一些技巧来正确缓存继承的 nil 值。如果没有这些技巧，任何旨在缺失或为 false 的实例数据或方法都会导致每次发生昂贵的 _parents 查找。由于假设基本类永远不会更改，因此这是一个安全的优化。即使 _slotcache 中存在“缓存的 NIL”值，将实例成员设置为其他值也会覆盖“缓存的 NIL”，因为仅在实例表中的查找失败时才会查阅 _slotcache 。
It’s important to recognize that because the caching version stores information directly in a single flattened table, changes to the base class methods may be ignored if they are already in the cached table. In practice, changing methods of a base class is an infrequent operation. When using this machinery, one should avoid this practice entirely.
重要的是要认识到，由于缓存版本将信息直接存储在单个扁平表中，因此如果缓存表中已存在基本类方法，则可能会忽略对基本类方法的更改。实际上，更改基本类的方法是一种不常见的操作。使用此机制时，应完全避免此做法。
Because Lua (IMO mistakenly) overrides nil as meaning both false and an empty data element, there is no way to override an inherited object member with the nil value. This is because setting self.a = nil will result in the removal of the “a” member, thus causing the missing-index tag method to fire, which consults the _parents or _slotcache tables to find an inherited element “a”. I’ve not yet found a workaround for this problem.
因为 Lua（我认为错误地）将 nil 覆盖为 false 和空数据元素的含义，因此无法使用 nil 值覆盖继承的对象成员。这是因为设置 self.a = nil 将导致删除“a”成员，从而导致丢失索引标记方法触发，该方法查询 _parents 或 _slotcache 表以查找继承元素“a”。我还没有找到解决此问题的解决方法。
Conclusion 结论
This note explains a performance optimized method of implementing multiple inheritance using Lua’s built in tag methods. This makes it possible to make larger and more useful class hierarchies in Lua, without incurring the significant performance penalties of the simplistic ‘parent lookup every time’ implementation.
此说明解释了使用 Lua 的内置标记方法实现多重继承的性能优化方法。这使得在 Lua 中创建更大、更有用的类层次结构成为可能，而不会产生简单“每次都查找父级”实现的显着性能损失。
The full code for the solution, including some helpful utility functions, is provided here.
此处提供了解决方案的完整代码，包括一些有用的实用程序函数。
References 参考文献
[1] R. Ierusalimschy, L. H. de Figueiredo, W. Celes, “Lua-an extensible extension language”, Software: Practice & Experience 26 #6 (1996) 635-652.
R. Ierusalimschy、L. H. de Figueiredo、W. Celes，“Lua——一种可扩展的扩展语言”，软件：实践与经验 26 #6 (1996) 635-652。