lua and fib
Randomly wrote fib function. One with a backing store and one without... needless to say the slow one is really slow compared to the cached version.
local compute_count = 0
-- backing store with first 2 fib numbers
local backing = {0,1}
-- fairly standard way to compute fib
function slowfib(n)
-- check the backing for the first cases
if n==1 then
return backing[1]
elseif n==2 then
return backing[2]
else
compute_count = compute_count + 1
-- otherwise recursive call to get the values
-- this can be slow just from the number of calls
return slowfib(n-1) + slowfib(n-2)
end
end
-- faster version
-- using the backing store when it is avail
-- like memoization ... or maybe it is really
-- using a cache like a boss
function fib(n)
-- if it is 1 or 2 then these are hardcoded into the backing storage
if n==1 then
return backing[1]
elseif n==2 then
return backing[2]
else
-- otherwise check if the backing has it
-- and use that if possible
if backing[n] ~= nil then
return backing[n]
else
-- compute it blech
compute_count = compute_count + 1
-- recursive call here
-- but in this case if we already have the value
-- it is no cost! the joy of caching
local v = fib(n-1)+fib(n-2)
-- save it since we took the hit on the work
backing[n] = v
-- return the value
return v
end
end
end
-- something to hold the coroutines
local workers = {}
for i=1,30 do
-- make them and save them
-- this does not start the work
-- they start suspended
local co = coroutine.create(fib)
table.insert(workers,co)
end
-- do the work
-- print the result
for i,v in ipairs(workers) do
print(coroutine.resume(v,i))
end
-- dump the backing store to console
for i,v in ipairs(backing) do
print("backing", i,v)
end
-- how many times did we really do work?
-- on slowfib it is a lot
-- on fib it is very low
print("total compute count",compute_count)