Soliciting criticism of memoize function

classic Classic list List threaded Threaded
14 messages Options
Reply | Threaded
Open this post in threaded view
|

Soliciting criticism of memoize function

Norman Ramsey-2
I would be pleased if readers of this list could think of any improvements
to the following memoize function:

  function memoize (f) 
    -- f must take at most one argument and return at most one result
      local cache = setmetatable({ }, { __mode = 'k' })
      local function update(x, v, ...) -- f(x) returns v, ... 
        assert(select('#', ...) == 0)
        cache[x] = v
        return v
      end

      return function (x, ...)
               assert(select('#', ...) == 0) -- cache works with at most one arg
               local v = cache[x]
               if v ~= nil then
                 return v
               else
                 return update(x, f(x))
               end
             end
  end

I'm especially concerned whether I have the cache's __mode metamethod
set correctly, as I always get confused about the semantics of weak
keys and weak values.


Norman

Reply | Threaded
Open this post in threaded view
|

Re: Soliciting criticism of memoize function

Patrick Donnelly-3
On Wed, May 14, 2008 at 7:40 PM, Norman Ramsey <[hidden email]> wrote:
> I would be pleased if readers of this list could think of any improvements
> to the following memoize function:
>
>  function memoize (f)
>    -- f must take at most one argument and return at most one result
>      local cache = setmetatable({ }, { __mode = 'k' })
>      local function update(x, v, ...) -- f(x) returns v, ...
>        assert(select('#', ...) == 0)
>        cache[x] = v
>        return v
>      end
>
>      return function (x, ...)
>               assert(select('#', ...) == 0) -- cache works with at most one arg
>               local v = cache[x]
>               if v ~= nil then
>                 return v
>               else
>                 return update(x, f(x))
>               end
>             end
>  end
>
> I'm especially concerned whether I have the cache's __mode metamethod
> set correctly, as I always get confused about the semantics of weak
> keys and weak values.
>
>
> Norman
>


I would move the metatable construction outside memoize because it
never changes. You could also do this instead:

do
  local FUNC = {}; -- key holder
  local mt = {
    __mode = "k",
    __index = function(t, k)
      t[k] = t[FUNC](k);
      return t[k];
    end
  };
  function memoize (f)
    -- f must take at most one argument and return at most one result
    local cache = setmetatable({[FUNC] = f}, mt)
    return function (x, ...)
      assert(select('#', ...) == 0) -- cache works with at most one arg
      return cache[x];
    end
  end
end

The __mode look ok to me.

-- 
-Patrick Donnelly

"One of the lessons of history is that nothing is often a good thing
to do and always a clever thing to say."

-Will Durant

Reply | Threaded
Open this post in threaded view
|

Re: Soliciting criticism of memoize function

Norman Ramsey-2
 > I would move the metatable construction outside memoize because it
 > never changes.

I understand the impulse, but since I'm already allocating a table at
every call, I don't mind allocating a second table at every call.

 > You could also [use the __index metamethod instead of testing for nil]

I like this idea; I hope my colleague will like it as well.  It makes
the code a little cleaner and the 'fast path' (a hit in the cache)
will be a little faster.   But notice it's even nicer if you just
capture the function lexically:

  function memoize (f)
    local function index(t, k)
      local function update(v, ...)
        assert(select('#', ...) == 0)
        t[k] = v
        return v
      end
      return update(f(k))
    end
    local cache = setmetatable({ }, { __mode = 'k', __index = index })
    return function (x, ...)
             assert(select('#', ...) == 0)
             return cache[x]
           end
  end

And if you're willing to lose should f return multiple results, as in
your example code, it becomes even simpler:

  function memoize (f)
    local function index(t, k)
      t[k] = f(k)
      return t[k]
    end
    local cache = setmetatable({ }, { __mode = 'k', __index = index })
    return function (x, ...)
             assert(select('#', ...) == 0)
             return cache[x]
           end
  end

I myself would rather have the extra protection, since it occurs only
on the slow path anyway.


Norman

Reply | Threaded
Open this post in threaded view
|

Re: Soliciting criticism of memoize function

Gé Weijers
In reply to this post by Norman Ramsey-2
Is there anything wrong with the following:

local function memoize(f)
    local function index(t, x)
        local v = f(x)
        t[x] = v
        return v
    end

    local cache = setmetatable({}, {__mode = 'k', __index = index})

    return function(x)
        return cache[x]
    end
end


On May 14, 2008, at 6:40 PM, Norman Ramsey wrote:

I would be pleased if readers of this list could think of any improvements
to the following memoize function:

  function memoize (f)
    -- f must take at most one argument and return at most one result
      local cache = setmetatable({ }, { __mode = 'k' })
      local function update(x, v, ...) -- f(x) returns v, ...
        assert(select('#', ...) == 0)
        cache[x] = v
        return v
      end

      return function (x, ...)
assert(select('#', ...) == 0) -- cache works with at most one arg
               local v = cache[x]
               if v ~= nil then
                 return v
               else
                 return update(x, f(x))
               end
             end
  end

I'm especially concerned whether I have the cache's __mode metamethod
set correctly, as I always get confused about the semantics of weak
keys and weak values.


Norman

--
Gé Weijers
[hidden email]





Reply | Threaded
Open this post in threaded view
|

Re: Soliciting criticism of memoize function

Peter Cawley
Gé Weijers: It doesn't check that f takes a single argument

2008/5/16 Gé Weijers <[hidden email]>:
> Is there anything wrong with the following:
>
> local function memoize(f)
>    local function index(t, x)
>        local v = f(x)
>        t[x] = v
>        return v
>    end
>
>    local cache = setmetatable({}, {__mode = 'k', __index = index})
>
>    return function(x)
>        return cache[x]
>    end
> end
>
>
> On May 14, 2008, at 6:40 PM, Norman Ramsey wrote:
>
>> I would be pleased if readers of this list could think of any improvements
>> to the following memoize function:
>>
>>  function memoize (f)
>>    -- f must take at most one argument and return at most one result
>>      local cache = setmetatable({ }, { __mode = 'k' })
>>      local function update(x, v, ...) -- f(x) returns v, ...
>>        assert(select('#', ...) == 0)
>>        cache[x] = v
>>        return v
>>      end
>>
>>      return function (x, ...)
>>               assert(select('#', ...) == 0) -- cache works with at most
>> one arg
>>               local v = cache[x]
>>               if v ~= nil then
>>                 return v
>>               else
>>                 return update(x, f(x))
>>               end
>>             end
>>  end
>>
>> I'm especially concerned whether I have the cache's __mode metamethod
>> set correctly, as I always get confused about the semantics of weak
>> keys and weak values.
>>
>>
>> Norman
>
> --
> Gé Weijers
> [hidden email]
>
>
>
>


Reply | Threaded
Open this post in threaded view
|

Re: Soliciting criticism of memoize function

Eric Tetz
In reply to this post by Norman Ramsey-2
On Wed, May 14, 2008 at 6:40 PM, Norman Ramsey <[hidden email]> wrote:
> I would be pleased if readers of this list could think of any improvements
> to the following memoize function:

Your code isn't testing for 'f' returning no values (which may or may
not be what you want).

I don't see why the 'update' closure is needed. Wouldn't it be more
straightforward to just say:

   function memoize (f)
      -- f must take at most one argument and return at most one result
      local cache = setmetatable({ }, { __mode = 'k' })
      return function (x, extra)
         assert(extra == nil) -- cache works with at most one arg
         local v = cache[x]
         if not v then
            v, extra = f(x)
            assert(extra == nil) -- cache works with at most one return value
            cache[x] = v
         end
         return v
      end
   end

Also, it's easy to allow f to return any number of values (unless
there's a reason you forbid that):

   function memoize (f)
      -- f must take at most one argument
      local cache = setmetatable({ }, { __mode = 'k' })
      return function (x, extra)
         assert(extra == nil) -- cache works with at most one arg
         local v = cache[x]
         if not v then
            v = { f(x) } -- save all return values
            cache[x] = v
         end
         return unpack(v)
      end
   end

Cheers,
Eric

Reply | Threaded
Open this post in threaded view
|

Re: Soliciting criticism of memoize function

Fidelis Assis
In reply to this post by Norman Ramsey-2
On Thu, May 15, 2008 at 9:38 PM, Norman Ramsey <[hidden email]> wrote:
>  > I would move the metatable construction outside memoize because it
>  > never changes.
>
> I understand the impulse, but since I'm already allocating a table at
> every call, I don't mind allocating a second table at every call.
>
>  > You could also [use the __index metamethod instead of testing for nil]
>
> I like this idea; I hope my colleague will like it as well.

Yes, I like it too. Nice idea  :-)

-- 
Fidelis Assis

Reply | Threaded
Open this post in threaded view
|

Re: Soliciting criticism of memoize function

Mark Hamburg-5
Some issues to deal with in getting a generic memoize to work correctly:

1. Do you need to support memoization for f( nil )? If so, you potentially need to handle this separately (but see below).

2. Do you handle nil results from f correctly? Efficiently?

The easiest way to deal with nil is to use a magic value in its place. For example, a custom table. We also need to cope with NaN as a parameter since it can't be used as a table key. This leads to something like the following (untested):

local kNil = { }
local kNaN = { }

local kCacheMode = 'k' -- but see note below

local function encodeKey( k )
	if k == nil then
		return kNil
	elseif k ~= k then
		return kNaN
	else
		return k
	end
end

local decodeHelper = { kNil = kNil, kNaN = 0 / 0 }

local function decodeKey( k )
	local v = decodeHelper[ k ]
	if not v then
		return k
	end
	if v == kNil then
		return nil
	else
		return v
	end
end

local function encodeValue( v )
	if v == nil then
		return kNil
	else
		return v
	end
end

local function decodeValue( v )
	if v == kNil then
		return nil
	else
		return v
	end
end

function memoize( f )

	local function update( t, k, ... )
		assert( select( '#', ... ) == 1 )
		local v = ...
		t[ k ] = v
		return v
	end

	local function index( t, k )		
		return update( t, k, encodeValue( f( decodeKey( k ) ) )
	end

local cache = setmetatable( { }, { __mode = kCacheMode, __index = index } )

	return function( x, ... )
		assert( select( '#', ... ) == 0 )
		return decodeValue( cache[ encodeKey( x ) ] )
	end

end

(Hey. If you are going to check the number of arguments, you ought to handle nil and NaN correctly as well...)

3. Cache mode gets tricky for a couple of reasons.

The first is that semi-weak tables can lead to cyclic situations since all of the values get marked. For example, if we memoize:

	function( x ) return { x } end

then nothing will ever get collected.

The second is that strings are considered values and hence will tend to get marked anyway as keys even if they aren't referenced elsewhere. Hence, a safer choice though it results in a memoization cache that doesn't last as long is to use a fully weak table.

Mark


Reply | Threaded
Open this post in threaded view
|

Re: Soliciting criticism of memoize function

Patrick Donnelly-3
On Sat, May 17, 2008 at 12:12 AM, Mark Hamburg <[hidden email]> wrote:
> Some issues to deal with in getting a generic memoize to work correctly:
>
> 1. Do you need to support memoization for f( nil )? If so, you potentially
> need to handle this separately (but see below).
>
> 2. Do you handle nil results from f correctly? Efficiently?
> ...

That's a little overly complicated, you can deal with it like this
(using my previous example):

do
 local FUNC = {}; -- key holder
 local NIL = {}; -- nil key
 local NaN = {} -- NaN
 local mt = {
   __mode = "k",
   __index = function(t, k)
     if k == nil then
       if t[NIL] then return t[NIL] end
       t[NIL] = t[FUNC](k);
       return t[NIL];
     elseif k ~= k and type(k) == "number" then
       if t[NaN] then return t[NaN] end
       t[NaN] = t[FUNC](k);
       return t[NaN];
     else
       t[k] = t[FUNC](k);
       return t[k];
     end
   end
 };
 function memoize (f)
   -- f must take at most one argument and return at most one result
   local cache = setmetatable({[FUNC] = f}, mt)
   return function (x, ...)
     assert(select('#', ...) == 0) -- cache works with at most one arg
     return cache[x];
   end
 end
end


On Thu, May 15, 2008 at 6:38 PM, Norman Ramsey <[hidden email]> wrote:
>  > You could also [use the __index metamethod instead of testing for nil]
>
> I like this idea; I hope my colleague will like it as well.  It makes
> the code a little cleaner and the 'fast path' (a hit in the cache)
> will be a little faster.   But notice it's even nicer if you just
> capture the function lexically:

I noticed this, but I wanted to keep the metatable outside of the
memoize function. This is of course up to you (make a new metatable
for each memoized function or not).

Cheers,

-- 
-Patrick Donnelly

"One of the lessons of history is that nothing is often a good thing
to do and always a clever thing to say."

-Will Durant

Reply | Threaded
Open this post in threaded view
|

Re: Soliciting criticism of memoize function

Norman Ramsey-2
In reply to this post by Eric Tetz
 > I don't see why the 'update' closure is needed. Wouldn't it be more
 > straightforward to just say:
 > 
 >    ...  v, extra = f(x); assert(extra == nil) ...

I'm more paranoid than that.  f might return multiple arguments, some
of which are nil.  You'll note that even the standard library
functions do this, although not with nil in the second position.

 > Also, it's easy to allow f to return any number of values ...
 > 
 >   ...  v = { f(x) } -- save all return values
 >   ...
 >   return unpack(cache[x])

Yes, this is probably worth doing, although I'm a little reluctant to
pay the overhead of 'unpack' on the fast path when *none* of the
applications I have in mind need it.


Norman


Reply | Threaded
Open this post in threaded view
|

Re: Soliciting criticism of memoize function

Norman Ramsey-2
In reply to this post by Mark Hamburg-5
 > Some issues to deal with in getting a generic memoize to work correctly:
 > 
 > 1. Do you need to support memoization for f( nil )? If so, you  
 > potentially need to handle this separately (but see below).
 > 
 > 2. Do you handle nil results from f correctly? Efficiently?

Nasty questions, both of them.  Well done!  The answers are that 

  1. memoize(f)(nil) causes a run-time error
  2. For every x such that f(x) is nil,
     memoize(f)(x) == f(x) but is more expensive than f(x).

Because I'm not willing to muck up the common case for something I
expect never to occur, I will add to the specification of memoize that
it is a checked run-time error to pass nil to memoize(f).

 > The easiest way to deal with nil is to use a magic value in its place.  
 > For example, a custom table. We also need to cope with NaN as a  
 > parameter since it can't be used as a table key. 

Argh!  That must have happened when I wasn't paying attention :-(

 > This leads to something like the following (untested):
 > 
 > ...	return decodeValue( cache[ encodeKey( x ) ] ) ...

I'm not willing to pay this additional overhead on the fast path.

Background for those who are curious: we're most interested in passing
tables to f, and we had been memoizing results of f by using an
__index metamethod that would 'create fields on demand' by calling f.
Switching to memoize simplifies the interface and metamethod
significantly, and equally important, it makes it easier to for us to
experiment with different functions f.  But we want not to take a big
hit in performance.  Our old cost was

  - field access

Our new cost is

  - function call
  - check select('#', ...)  -- for safety
  - field access

I'm reluctant to add something like encode and decode, which do actual
work, and moreover which have to be explained.  

 > (Hey. If you are going to check the number of arguments, you ought to  
 > handle nil and NaN correctly as well...)

Our 'checking' amounts to an assertion failure.  What we want is for
the program to halt if memoize is misused.  This will happen if nil or
NaN is used as an argument to memoize(f), so it's OK...

 > 3. Cache mode gets tricky for a couple of reasons.
 > 
 > The first is that semi-weak tables can lead to cyclic situations since  
 > all of the values get marked. For example, if we memoize:
 > 
 > 	function( x ) return { x } end
 > 
 > then nothing will ever get collected.
 > 
 > The second is that strings are considered values and hence will tend  
 > to get marked anyway as keys even if they aren't referenced elsewhere.  
 > Hence, a safer choice though it results in a memoization cache that  
 > doesn't last as long is to use a fully weak table.

This is an area where I really don't understand the issues.  It sounds
like what you're saying is that it's bad to have string keys because
strings are not likely to be reused, yet the associations will clutter
up the table.   But we have weak keys, so the strings and values can
be collected, no?  What am I missing here?  Are you thinking that
having results alive will keep the string arguments alive and in the
table unnecessarily?


Norman

Reply | Threaded
Open this post in threaded view
|

Re: Soliciting criticism of memoize function

Mark Hamburg-5

On May 17, 2008, at 10:54 AM, Norman Ramsey wrote:

Some issues to deal with in getting a generic memoize to work correctly:

1. Do you need to support memoization for f( nil )? If so, you
potentially need to handle this separately (but see below).

2. Do you handle nil results from f correctly? Efficiently?

Nasty questions, both of them.  Well done!  The answers are that

 1. memoize(f)(nil) causes a run-time error
 2. For every x such that f(x) is nil,
    memoize(f)(x) == f(x) but is more expensive than f(x).

True. You don't need to encode nil as stored as a result in the memoize table but it means that anything with a nil result will produce nil over and over again.

I'm reluctant to add something like encode and decode, which do actual
work, and moreover which have to be explained.

Relatively speaking, the encode and decode are probably cheaper than the checks being done with select. Remember that assert does not compile out.

Another approach to dealing with NaN as an argument is to observe that the behavior will be that table lookups using NaN as a key will fail and hence just let it force you over to the slow path.

This is an area where I really don't understand the issues.  It sounds
like what you're saying is that it's bad to have string keys because
strings are not likely to be reused, yet the associations will clutter
up the table.   But we have weak keys, so the strings and values can
be collected, no?  What am I missing here?  Are you thinking that
having results alive will keep the string arguments alive and in the
table unnecessarily?

Basically weak tables are always a bit tricky and semi-weak tables are doubly so. Essentially weakness means that some of the keys and values won't be marked via the table and hence may get collected, but that word "some" is important to understand.

Mark


Reply | Threaded
Open this post in threaded view
|

Re: Soliciting criticism of memoize function

Norman Ramsey-2
 > True. You don't need to encode nil as stored as a result in the  
 > memoize table but it means that anything with a nil result will  
 > produce nil over and over again.

Indeed so.

 > > I'm reluctant to add something like encode and decode, which do actual
 > > work, and moreover which have to be explained.
 > 
 > Relatively speaking, the encode and decode are probably cheaper than  
 > the checks being done with select. Remember that assert does not  
 > compile out.

I haven't looked closely at the Lua VM since the ... construct was
introduced, so I don't really know what the select is likely to cost.
I would hope the compiler would be clever about it, but I don't know.
The assert is the other call I referred to.

 > > This is an area where I really don't understand the issues.  It sounds
 > > like what you're saying is that it's bad to have string keys because
 > > strings are not likely to be reused, yet the associations will clutter
 > > up the table.   But we have weak keys, so the strings and values can
 > > be collected, no?  What am I missing here?  Are you thinking that
 > > having results alive will keep the string arguments alive and in the
 > > table unnecessarily?
 > 
 > Basically weak tables are always a bit tricky and semi-weak tables are  
 > doubly so. Essentially weakness means that some of the keys and values  
 > won't be marked via the table and hence may get collected, but that  
 > word "some" is important to understand.

Yes.  I don't understand.  I have never understood.  It's one place
where I think both the reference manual and PIL fall down, because the
explanation is with respect to a model that's not written down anywhere.
I have long wanted a formal semantics of some fragment of Lua, and the
semantics of garbage collection is right up there with things that
I would like to see formalized.


Norman


Reply | Threaded
Open this post in threaded view
|

Re: Soliciting criticism of memoize function

Roberto Ierusalimschy
>  > Basically weak tables are always a bit tricky and semi-weak tables are  
>  > doubly so. Essentially weakness means that some of the keys and values  
>  > won't be marked via the table and hence may get collected, but that  
>  > word "some" is important to understand.
> 
> Yes.  I don't understand.  I have never understood.  It's one place
> where I think both the reference manual and PIL fall down, because the
> explanation is with respect to a model that's not written down anywhere.
> I have long wanted a formal semantics of some fragment of Lua, and the
> semantics of garbage collection is right up there with things that
> I would like to see formalized.

We may define a predicate SA ("strongly accessible") inductively:

- the main thread is SA;

- all values refered by local variables of a SA thread are SA;

- the environment of a SA thread is SA;

- bla-bla-bla (for closures, registry, etc.)

- if a table is SA and it does not have weak keys, then all its keys
are SA;

- if a table is SA and it does not have weak values, then all its values
are SA;

- only values proven SA by the previous rules are SA.

Then GC goes like this:

- any value that is not SA is eventually collected;

- once a value is collected, any entry in any table with that value
as a key or as a value is removed from the table.

(If you want finalizers the model is more complex, but not too much.)

-- Roberto