robinmonjo
Recursion performance: why so slow?
Hello all,
I wanted to implement a simple function that calculates the “hash rate” of my computer. Basically, how many times per second my computer can compute a sha256 hash. So I came up with this simple function:
defmodule HashRate do
def estimate_hash_rate(interval \\ 20) do
start = System.system_time(:second)
n = estimate_hash_rate(interval, start, 0)
n / (interval * 1000) # result in khs
end
def estimate_hash_rate(interval, start, n \\ 0) do
if start + interval < System.system_time(:second) do
n
else
:crypto.hash(:sha256, "data#{n}")
estimate_hash_rate(interval, start, n + 1)
end
end
end
It runs during 20 seconds and count how many times it performs the hash. When I run this function multiple times, I get results like 378.59365, 337.1613
I implemented a similar algorithm in Go and got much faster results : 5236.6924, 5468.282. Here is the code:
func main() {
interval := int32(20)
start := int32(time.Now().Unix())
n := 0
for {
if start + interval < int32(time.Now().Unix()) {
break
}
h := sha256.New()
h.Write([]byte("data" + strconv.Itoa(n)))
n += 1
}
fmt.Println(float32(n) / float32(interval * 1000))
}
I know Elixir/Erlang may be slow for computation, so I commented out the sha256 hash of my code (to just count the number of iteration per seconds) and got these kinds of results:
Go: 90172.62 (k iterations / s)
Elixir: 5476.6122 (k iterations / s)
Again the difference is HUGE. I don’t think I’m doing anything wrong in my tests. I’m aware of “tail recursivity” (and I believe the function I wrote is tail recursive). I tried to run the code with MIX_ENV=prod but got same kind of results.
Any ideas of what is going on ? What makes Elixir so slow compared to Go in this naive test ? Maybe System.system_time(:second) ? Or maybe I’m doing something wrong ??
Marked As Solved
OvermindDL1
A couple things:
If TCO takes place it will indeed prevent the stack from growing, but it does this by destroying everything currently on the stack (basically re-using it), which is a ‘tiny’ bit more expensive then just growing the stack (trivially so in most cases).
The BEAM VM does a ‘reduction’ on every-single-function call, so it can pre-empt an actor when it has used up ‘too many reductions’ to allow others to run.
The BEAM VM is also running a very safe, even if you do absolute horror of code in an actor it will not crash other actors, so there is a lot of state keeping. it is designed to be an ‘Always Running’ System.
The BEAM VM is optimized for IO events, not function calls, and as such it focuses on those in an entirely safe way.
Compare to go where yes it is faster, however a single badly written line of code in some library that you may use that may only get called randomly in production can crash your entire system, this cannot happen on the BEAM VM (and if it could then it is a bug and should be reported).
The BEAM VM is fantastic at slaving out expensive things to calls in native code (even go) while keeping everything running and even restarting native code that can crash.
In general programming on the BEAM VM (whether via Elixir, Erlang, etc…) is similar to python where you first implement the base system on the BEAM VM, trusting it to never die, and if you find something that is worth speeding up then slave that out to a native process via a Port or so, fully managed by the BEAM VM by supervisors just like any other process to do the hard and heavy work.
And an aside, in Go you are probably not calling a function recursively there, it is probably getting optimized in machine code to simple jumps, so you are not testing apples<->apples anyway.







