Hi guys!
I’ve been learning Elixir for some time now, and recently I’ve noticed something weird while playing with benchee
.
I was creating different implementations for factorial calculation and measuring their time and memory consumption. Here are two of them:
- simple reduce of a range:
def factorial_with_reduce(n) when is_integer(n) and n >= 0 do 1..n//1 |> Enum.reduce(1, &*/2) end
- split by chunks, reduce them, then reduce the reduced results:
def factorial_with_reduce_on_chunks(n, chunk_size \\ 4) when is_integer(n) and n >= 0 do 1..n//1 |> Stream.chunk_every(chunk_size) |> Stream.map(fn list -> Enum.reduce(list, 1, &*/2) end) |> Enum.reduce(1, &*/2) end
I’ve also created some benchmarks and results surprised me very much.
As I expected, factorial_with_reduce
consumed only a constant amount of memory. However, it consumed almost 2.5x more time than factorial_with_reduce_on_chunks
.
I created a repo on Github specifically for this question (benchmarks are provided in README.md), please take a closer look if you wish: GitHub - IhorTsoi/factorial_implementations_question: This repo holds the code for performance related elixir question..
My question is: how can the second implementation be faster, if we still need to do n-1 multiplications + create intermediate chunks? How can it be 2.5x faster? Simple reduce does linear multiplication and nothing more, doesn’t it? What’s the problem with it (or my implementation of the function / its benchmark)?
I used small (5’000), medium (100’000) and large inputs (500’000). And at each point, factorial_with_reduce_on_chunks
was significantly faster…
I’m really confused about it. Could you please help me on this?