技術ノート 8

Luaにおける高速な多重継承タグメソッド実装

概要

問題点

解決策

キャッシュを使用しない実装は非常にシンプルです。_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

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"

ほとんど同じ機能を持ちながら、大幅に高速なパフォーマンス最適化実装を提供します。

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

説明

キャッシュ内では、関数は直接指し示され、その他の項目は「SLOT_REF」と呼ばれるものを使用して指し示されます。SLOT_REFは、値ではなく参照によるキャッシュである特殊な種類のテーブルです。元のテーブルと元の値のインデックスへの参照が含まれているため、元のデータ値が変更された場合でも、このSLOT_REFは新しいデータ値を正しく指し示します。これはメソッドには行われません。メソッドルックアップのパフォーマンスが、基底クラスのメソッドを変更する機能よりも重要であると判断されたためです。

SLOT_REFを廃止し、代わりにslotcacheの無効化を行う方法（逆slotcache依存リストを維持するなど）を使用することで、この機構の別の実装をさらに高速化できます。基底クラスのメソッドまたは関数が変更されるたびに、逆依存関係チェーンのslotcacheが無効になります。"_slotcache"を現在の「インスタンス」レベルではなく「クラス」レベルで発生させるように変更した場合、これはおそらく適度な追加データ保持に繋がるでしょう。

弱点

キャッシュバージョンは情報を単一のフラット化されたテーブルに直接保存するため、基底クラスのメソッドの変更は、既にキャッシュされたテーブルにある場合は無視される可能性があることに注意することが重要です。実際には、基底クラスのメソッドを変更することはまれな操作です。この機構を使用する場合は、この慣習を完全に避けるべきです。

Luaは（私の意見では誤って）`nil`を偽と空のデータ要素の両方の意味としてオーバーライドしているため、継承されたオブジェクトメンバーを`nil`値で上書きする方法がありません。これは、self.a = nilを設定すると、「a」メンバーが削除され、欠落インデックスタグメソッドが起動し、_parentsまたは_slotcacheテーブルを参照して継承された要素「a」を検索するためです。この問題に対する回避策はまだ見つかっていません。

結論

いくつかの便利なユーティリティ関数を含む、ソリューションの完全なコードはこちらで提供されています。

参考文献