This is a pura-Lua memoization function that builds upon what was shown in Programming In Lua’s memoization implementation function.
- 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.
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.
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: