$ mix profile.fprof -e Demo.load_1
Warmup...
Reading trace data...
..................................................
.................................
End of trace!
Processing data...
Creating output...
Done!
CNT ACC (ms) OWN (ms)
Total 2966862 7384.348 7370.573
:fprof.apply_start_stop/4 0 7384.348 0.013
anonymous fn/0 in :elixir_compiler_1.__FILE__/1 1 7384.319 0.002
Demo.load_1/0 1 7384.317 0.002
Demo.run_load/2 1 7384.315 0.007
List.foldl/3 1 7384.274 0.001
List."-foldl/3-lists^foldl/2-0-"/3 9 7384.273 0.024
anonymous fn/2 in Demo.load_1/0 8 7384.249 0.010
Demo.run_1/2 8 7384.239 0.019
Fib.body/1 2959380 7383.630 7330.228
:garbage_collect 5424 39.637 39.637
:suspend 1708 13.775 0.000
Demo.run_2/2 8 0.590 0.040
Fib.mem/2 9 0.215 0.031
Fib.lco/1 20 0.191 0.038
Fib.mem_fill/2 6 0.175 0.036
Fib.lco/4 105 0.153 0.153
Fib.ets/2 8 0.150 0.020
Fib.mem_fill/5 35 0.120 0.087
Fib.ets_fill/2 6 0.118 0.017
Fib.ets_fill/6 35 0.092 0.070
:maps.put/3 29 0.033 0.033
:maps.find/2 21 0.021 0.021
:ets.lookup/2 14 0.021 0.021
:ets.insert/2 7 0.019 0.019
:fprof."-apply_start_stop/4-after$^1/0-0-"/3 1 0.016 0.006
:ets.delete/1 1 0.015 0.015
Fib.ets_init/1 1 0.012 0.005
:maps.size/1 6 0.007 0.007
Fib.mem/1 1 0.007 0.001
Fib.ets_top/3 7 0.007 0.007
:ets.new/2 1 0.003 0.003
:undefined 0 0.000 0.000
$ mix profile.fprof -e Demo.load_2
Warmup...
Reading trace data...
..................................................
......
End of trace!
Processing data...
Creating output...
Done!
CNT ACC (ms) OWN (ms)
Total 46769 104.538 102.942
:fprof.apply_start_stop/4 0 104.538 0.014
anonymous fn/0 in :elixir_compiler_1.__FILE__/1 1 104.520 0.002
Demo.load_2/0 1 104.518 0.002
Demo.run_load/2 1 104.516 0.006
List.foldl/3 1 102.996 0.001
List."-foldl/3-lists^foldl/2-0-"/3 6 102.995 0.030
anonymous fn/2 in Demo.load_2/0 5 102.965 0.010
Demo.run_2/2 5 102.955 0.028
Fib.mem/2 6 47.658 0.023
Fib.mem_fill/2 5 47.628 0.028
Fib.mem_fill/5 10004 47.584 28.096
Fib.ets/2 5 29.961 0.017
Fib.ets_fill/2 5 29.936 0.015
Fib.ets_fill/6 10004 29.912 16.173
Fib.lco/1 15 25.317 0.033
Fib.lco/4 16600 25.284 24.615
:maps.put/3 9999 13.114 13.114
:garbage_collect 25 12.586 12.586
:ets.insert/2 6 6.606 6.606
:suspend 33 1.596 0.000
:ets.delete/1 1 1.491 1.483
:maps.find/2 16 0.017 0.017
:ets.lookup/2 10 0.017 0.017
Fib.ets_init/1 1 0.013 0.006
Fib.mem/1 1 0.010 0.001
:maps.size/1 5 0.006 0.006
Fib.ets_top/3 6 0.006 0.006
:fprof."-apply_start_stop/4-after$^1/0-0-"/3 1 0.004 0.004
:ets.new/2 1 0.003 0.003
:undefined 0 0.000 0.000
defmodule Demo do
# lib/demo.ex
def load_1() do
run_load([0,1,5,10,15,20,25,30], &run_1/2)
end
def load_2() do
run_load([100,500,1000,5000,10000], &run_2/2)
end
def run_load(load, run_f) do
{_, mem} = Fib.mem(0)
tid = Fib.ets_init(:my_cache)
_state = List.foldl(load, {mem,tid}, run_f)
:ets.delete(tid)
end
def run_1(n, state) do
Fib.body(n)
run_2(n, state) # returns new state
end
def run_2(n, {mem, tid}) do
Fib.lco(n)
{_, next_mem} = Fib.mem(n, mem)
Fib.ets(n, tid)
{next_mem, tid}
end
end
defmodule Fib do
# lib/fib.ex
# 1. body recursion
def body(0),
do: 0
def body(1),
do: 1
def body(n) when n > 1 and is_integer(n),
do: body(n-2) + body(n-1)
# 2. utilizing "last call optimization"
# http://erlang.org/pipermail/erlang-questions/2016-October/090663.html
defp lco(_, acc, i, n) when i == n,
do: acc
defp lco(fi_2, fi_1, i, n) when i < n,
do: lco(fi_1, fi_2 + fi_1, i + 1, n)
def lco(0),
do: 0
def lco(1),
do: 1
def lco(n) when n > 1 and is_integer(n),
do: lco(lco(0), lco(1), 1, n)
# 3. using a result cache
defp mem_fill(_, fi_1, i, mem, n) when i > n do
{fi_1, mem}
end
defp mem_fill(fi_2, fi_1, i, mem, n) do
fi = fi_2 + fi_1
mem_fill(fi_1, fi, i+1, Map.put(mem, i, fi), n)
end
defp mem_fill(n, mem) do
with i <- Map.size(mem),
{:ok, fi_2} <- Map.fetch(mem, i - 2),
{:ok, fi_1} <- Map.fetch(mem, i - 1) do
mem_fill(fi_2, fi_1, i, mem, n)
else
_ -> # unexpected lookup failure - start fresh
mem_fill(0, 1, 2, %{0 => 0, 1 => 1}, n)
end
end
def mem(n, mem \\ %{0 => 0, 1 => 1}) when n >= 0 and is_integer(n) do
with {:ok, result} <- Map.fetch(mem, n) do
{result, mem}
else
_ -> # not found
mem_fill(n, mem)
end
end
# 4. ETS cache
defp ets_top(fib_i1, fib_i, i),
do: {:top, {fib_i1, fib_i, i}}
defp ets_fill(fib_i1, fib_i, i, kvs, tid, n) when i == n do
:ets.insert(tid, [ets_top(fib_i1, fib_i, i) | kvs])
fib_i
end
defp ets_fill(fib_i1, fib_i, i, kvs, tid, n) when i < n do
fib_next = fib_i1 + fib_i
next = i + 1
ets_fill(fib_i, fib_next, next, [{next, fib_next}|kvs], tid, n)
end
defp ets_fill(n, tid) do
with [{_, {fib_i1, fib_i, i}}] <- :ets.lookup(tid, :top) do
ets_fill(fib_i1, fib_i, i, [], tid, n)
else
_ -> # unexpected lookup failure
raise ArgumentError, message: "Provided inconsistent ETS cache"
end
end
def ets_init(name) when is_atom(name) do
tid = :ets.new(name,[:set, :private, {:keypos, 1}])
:ets.insert(tid, [{0, 0}, {1, 1}, ets_top(0,1,1)])
tid
end
def ets(n, tid) do
with [{_ ,fib_n}] <- :ets.lookup(tid, n) do
fib_n
else
_ ->
ets_fill(n, tid)
end
end
end
Edit: Added an ETS version.
