Shared activation records are cheaper!

[Edgar Toernig <froese@...>]

Hi,

The following article was sitting unfinished in my drafts folder
for a while now but seeing the recent posts about recursive local
functions and upvalues I think it's time to finish it.  So here
it is...

      -----------------------------------------------------

I once wrote that it would be very expensive to have shared activation
records to implement lexical scoping.  I have to correct myself:
It costs at max the same as upvalues and is normally cheaper.  Under
some conditions even up to a couple of magnitudes cheaper!  Let me
explain:

I noticed some time ago that the handling of the function statements has
changed from 3.2 to 4.0.  In 3.2 the function object is used directly
unless it uses upvalues in which case a closure object is generated.
In 4.0 this was simplified to always create a closure object.

But only now I though about the consequences of this simplification.
Well, the first thing you notice is that executing a function state-
ment costs more for functions not using upvalues.  For static (global)
functions this normally makes no difference.  But for local functions,
especially within loops, this may make a real difference.  Because
the closure is a garbage collected object (gc-obj) it trashes the
memory pool too.  Some examples:

Ex 1)
	function foo()
	   local bar = function() ... end
	   ...
        end

   This one creates one gc-obj each time the statement "local bar = function"
   is executed.  That is, one per invocation of foo.


Ex 2)
	function foo()
	   local bar = function() ... end
	   local baz = function() ... end
	   ...
	end

   This one creates two gc-objs (one for each function()) each time foo is
   called.

Ex 3)
	function foo()
	   for i=1,N do
	      bar(function() ... end)
	   end
	   ...
	end

   And this one is really bad.  It creates N gc-objs!  One for each
   iteration of the loop.

(Please note: lua 3.2 has the same behavior if these functions use
upvalues.  Without upvalues, no gc-objs will be created.)

The global function foo is no problem.  It creates a closure object,
but it has a long lifetime and will not really trash the mempool.
But the local functions all have a short lifetime and fill the mempool
with unused objects forcing the garbage collector to run more often.
And of course it's a little bit slower because you have to allocate
the object.


Now, lets look at a simple version of shared activation records:  you
split the locals in two groups - normal locals and shared locals.
The normals locals are only accessed by the function itself and are
stored on the stack as it is done now.  The shared locals are the
ones additionally accessed by any local functions.  They are stored
in a special gc-obj.  This object is created on function entry and
tagged to all local functions.  So you don't attach the frozen value
of some locals to a function as it is done with the upvalues but a
reference to the storage for the accessed locals itself.

What does it give?  All examples above would only allocate at most
one gc-obj independent of how many local functions are defined.  So
you may get a better behavior then with Lua 3.2.  And if you do not
allocate an obj if there are no shared locals you'll always get a
better behavior.

But you get more.  All functions access the same object.  So, if a
local function modifies an upper local, the enclosing function sees
it.  Example:

   function foo()
      local i=0
      local inc = function() i=i+1 end
      inc() inc() inc() print(i)		--> 3
   end

And recursive local functions:

   function foo()
      local bar = function(n)
         if n<2 then return 1 end
         return n*bar(n-1)
      end
      print(bar(3))
   end

The syntax "function bar(n)" would even make sense here.  And you have
all the properties of upvalues for free:

   function foo(name)
      local fd = openfile(name, "r")
      return function(pat) read(fd, pat) end
   end
   x = foo("test")
   print(x"*w", x"*n", x"*n")

(I've not used a %-syntax to access outer locals.  IMO that would be
superfluous because everyone will expect the right behavior even with-
out a %-sign.)


Of course, the implementation is not that easy as it sounds.  But I think
it's less work then what has been done on the code generator.  There's
just one implementation detail I would like to mention at the moment:
How to tag the object containing the shared locals to a function?  If
it's done like the upvalue mechanism it would not save you anything.
But if you store it as an additional field in the TObject struct (well,
actually in the Value union) you are done.  And afaics, the memory
used by TObject/Value does not increase (sizeof(double)>=2*sizeof(void*)).

The only question the remains (for me -- at the moment *g*) is, is Lua
supposed to go in that direction?  If not in 4.0 maybe in later versions?

Even if not, I would like to discuss some implementation details on the
list because then I'll try to do it when Lua 4.0 is out ;)


Puh, that's another long one.  If I continue that way, you get a
completely wrong impression from me - I don't like writing prose :-)

Ciao, ET.