Lua: technical note 8

Technical Note 8

A fast multiple-inheritance tag method implementation in 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.

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.

The Solution

A tag-method inheritance scheme is proposed which provides single and multiple inheritance, and whose implementation drastically speeds up aclearcase/" target="_blank" >ccess 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.

The non-caching implementation is rather simple. It uses a _parents = {} member in a table to create an inheritance chain.

-- ********************************************************
-- 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.

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".

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.

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.

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.

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.

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.

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.

---

原文转自：http://www.ltesting.net