memoize.lua

This is a pura-Lua memoization function that builds upon what was shown in Programming In Lua’s memoization implementation function.

Main characteristics:

• Caches the results based on multiple parameters instead of just 1.
• Doesn’t rely on tostring; instead, it uses operator == on all the parameters (this is accomplished by structuring the cache in a tree-like structure, where each tree node corresponds to one parameter).
• Works correctly with functions returning multiple values, i.e. x,y = getPosition()

Partially inspired by this StackOverflow question

Examples of use

memoize.lua can be used to avoid stack overflow & slow performance on recursive functions, in exchange for memory. In some cases it might be necessary to `seed the function` before using it.

function triangle(x)
  if x == 0 then return 0 end
  return x+triangle(x-1)
end

print(triangle(40000)) -- stack overflow: too much recursion

local memoize = require 'memoize'

triangle = memoize(triangle) -- make triangle memoized, so it "remembers" previous results

for i=0, 40000 do triangle(i) end -- seed triangle's cache

print(triangle(40000)) -- 800020000, instantaneous result

Another use for memoize.lua is on resource-loading functions. Let’s say you have an image-loading function called load_image. You’d like to use the image loaded by that function on two different places in your code, but you are unsure of which of those places will call load_image first; and you don’t want to load two images.

function load_image(path)
  ...
  return image
end

function f()
  local image = load_image(path)
  ...
end

function g()
  local image = load_image(path)
  ...
end

You can just memoize load_image; the image will be loaded the first time load_image is called, and will be recovered from the cache on subsequent calls.

local memoize = require 'memoize'

function load_image(path)
  ...
  return image
end

load_image = memoize(load_image)

function f()
  local image = load_image(path)
  ...
end

function g()
  local image = load_image(path)
  ...
end

Gotchas / Warnings

• nil return values are considered cache-misses and thus are never cached; If you need to cache a function that doesn’t return anything, make it return a dummy not-nil value (false, ’’, 0 or any other non-nil value will work just fine).
• If you need to liberate the memory used by a memoized function, memoize it again:

mf = memoize(f);
mf(1)
mf(2)
mf(3)
memoize(f) -- this cleans up the cache

• This function does not use weak tables for caching; the memory devoted to memoizing is thus not-recuperable until the program halts/stops. If you are going to use this function extensively, you might want to modify insertInCache so that it uses weak tables.
• There’s a (small) linear performance & memory penalty for every additional parameter used. Try to keep the parameter numbers low.

Installation

Just copy the memoize.lua file somewhere in your projects (maybe inside a /lib/ folder) and require it accordingly.

Remember to store the value returned by require somewhere! (I suggest a local variable named memoize)

local memoize = require 'memoize'

Also, make sure to read the license file; the text of that license file must appear somewhere in your projects’ files.

Specs

This project uses telescope for its specs. If you want to run the specs, you will have to install telescope first. Then just enter the spec folder and execute tsc:

tsc spec/*