Why is Elixir slowest among Ruby and Go in solving Project Euler #5?

Question

Update: Elixir isn't slow, my algorithm was. My algorithms weren't even apples to apples comparison. See Roman's answers below for Ruby and Go equivalent algorithms. Also thanks to José, my slow algorithm can be significantly sped up by just prefixing MIX_ENV=prod. I've updated the stats in the question.

Original question: I'm working on Project Euler problems in multiple languages just to see how productive and how fast languages are. In problem #5, we are asked to find the smallest positive number that is evenly divisible by all of the numbers from 1 to 20.

I implemented the solution in multiple languages. Here are the stats:

1. Go 1.4.2 : 0.58s
2. Ruby 2.2 MRI : 6.7s
3. Elixir 1.0.5 (my first algorithm) : 57s
4. Elixir 1.0.5 (my first algorithm with MIX_ENV=prod prefix): 7.4s
5. Elixir 1.0.5 (Roman's Go equivalent algorithm) : 0.7s
6. Elixir 1.0.5 (Roman's Ruby equivalent algorithm) : 1.8s

Why is Elixir's performance so slow? I tried using the same optimizations in all languages. Caveat: I'm a FP and Elixir newbie.

Is there anything I can do to improve the performance in Elixir? If you used any profiling tools in figuring out a better solution, could you please include them in the response?

In Go:

func problem005() int {
  i := 20
outer:
  for {
    for j := 20; j > 0; j-- {
      if i%j != 0 {
        i = i + 20
        continue outer
      }
    }
    return i
  }
  panic("Should have found a solution by now")
}

In Ruby:

def self.problem005
  divisors = (1..20).to_a.reverse

  number = 20 # we iterate over multiples of 20

  until divisors.all? { |divisor| number % divisor == 0 } do
    number += 20
  end

  return number
end

In Elixir:

def problem005 do 
  divisible_all? = fn num ->
    Enum.all?((20..2), &(rem(num, &1) == 0))
  end

  Stream.iterate(20, &(&1 + 20))
  |> Stream.filter(divisible_all?)
  |> Enum.fetch! 0
end

Hillery

I can't explain your Elixir, but there are almost certainly better ways to solve that problem, e.g. try and construct the number rather than just scan for it. – Bindle

Thanks, Rup. I'll try that suggestion. However, my question here is purely related to performance of a similar logic is 3 different languages. – Hillery

If you are benchmarking Elixir code, please make sure you are benchmarking it with MIX_ENV=prod so Elixir compiles your project as efficiently as possible. Otherwise, you are getting suboptimal performance. – Strathspey

Answer 1

My first answer was about implementing the same algorithm that you have implemented in Ruby. Now, here is a version in Elixir of your algorithm in Go:

defmodule Euler do
  @max_divider 20
  def problem005 do 
    problem005(20, @max_divider)
  end

  defp problem005(number, divider) when divider > 1 do
    if rem(number, divider) != 0 do
      problem005(number+20, @max_divider)
    else
      problem005(number, divider-1)
    end
  end
  defp problem005(number, _), do: number
end

It takes about 0.73s on my laptop. These algorithms are different, so I'm sure that Ruby also could play better here.

I guess, the general rule here: if you have code in Elixir that has performance like 80% from Go code or better, that's ok. In other cases most likely you have algorithmic error in your Elixir code.

Update about Ruby:

As bonus, here is Go equivalent algorithm in Ruby:

def problem_005
  divisor = max_divisor = 20
  number = 20 # we iterate over multiples of 20

  while divisor > 1 do
    if number % divisor == 0 
      divisor -= 1
    else
      number += 20
      divisor = max_divisor
    end
  end

  number
end

It performs in 4.5 times faster, so I guess it could show ~ 1.5 s on your computer.

Fallal

Thanks again for answering! This takes ~0.7s on my system. – Hillery

Excellent! Was glad to help you :-) – Fallal

Answer 2

Try this version:

defmodule Euler do
  def problem005 do 
    problem005(20)
  end

  @divisors (20..2) |> Enum.to_list 
  defp problem005(number) do
    if Enum.all?(@divisors, &(rem(number, &1) == 0)) do
      number
    else
      problem005(number+20)
    end
  end
end

It takes about 1.4 sec on my laptop. The main issue of your solution is conversion of a range to a list at each iteration. It's a huge overhead. Besides, there is no need to create "infinite" stream here. You didn't do something like that in other languages.

Fallal

Thanks, Roman! Your algorithm takes ~1.8s on my system. The biggest culprit was indeed range to list conversion. Creating the list from range just once brought down the runtime from 57s to 2.7s. – Hillery

It is worth noting that MIX_ENV=prod would speed up the range to list conversion considerably (because we inline those) and ranges in Elixir 1.1 will also be faster. – Strathspey

Thanks, José! I did see a significant improvement (57.0s to 7.4s) by prefixing MIX_ENV=prod in my embarrassingly slow algorithm. I've updated the stats in the question. – Hillery

Answer 3

Your code may be fine, but the math makes my teeth hurt. There is a simple recursive solution that matches nicely to the elixir way of doing things. It also shows how you can just do recursion in elixir and not worry about the performance problems that recursion causes in other languages.

defmodule Euler_5 do
@moduledoc """
Solve the smallest number divisible by 1..X using Greatest Common Divisor.
"""

  def smallest(1), do: 1
  def smallest(2), do: 2

  def smallest(n) when n > 2 do
    next = smallest(n-1)
    case rem(next, n) do
      0 -> next
      _ -> next * div(n,gcd(next,n))
    end
  end

  def gcd(1,_n), do: 1

  def gcd(2,n) do
    case rem(n,2) do
      0 -> 2
      _ -> 1
    end
  end

  def gcd( m, n) do
    mod = rem(m,n)
    case mod do
      0 -> n
      _ -> gcd(n,mod)
    end
  end

end

For what it's worth, this takes 8 microsecs on my computer

iex> :timer.tc(Euler_5, :smallest, [20])
{8, 232792560}

Not really a fair comparison to other languages since it doesn't include the time to load up the VM and do the I/O.

Mantellone

Thanks, Fred. 8 microseconds is impressive! I'm trying not to peek at your solution so I can try the GCD approach myself. I will include the stats from you solution after I work on my own solution. – Hillery

Answer 4

I like this solution for its simplicity:

#!/usr/bin/env elixir
defmodule Problem005 do
  defp gcd(x, 0), do: x
  defp gcd(x, y), do: gcd(y, rem(x, y))

  defp lcm(x, y) do
    x * y / gcd(x, y)
  end

  def solve do
    1..20
    |> Enum.reduce(fn(x, acc) -> round(lcm(x, acc)) end)
  end
end

IO.puts Problem005.solve

It's very fast as well.

./problem005.exs  0.34s user 0.17s system 101% cpu 0.504 total

As for Ruby, this can be solved in one line:

#!/usr/bin/env ruby
puts (1..20).reduce { |acc, x| acc.lcm(x) }

(lcm -> http://ruby-doc.org/core-2.0.0/Integer.html#method-i-lcm)

Aesthesia

and to go further with ruby... (1..20).inject(&:lcm) – Margitmargo

Answer 5

Fred's solution is great. This is more inneficient, (32 microseconds) but more clear. Maybe with meomization, it could run order of magnitude faster.

defmodule Euler5 do
  def smallest(n) when n > 0 do
    Enum.reduce(1..n, &(lcm(&1, &2)))
  end
  def smallest(n), do: n

  def lcm(x, y), do: div((x * y), gcd(x, y))

  def gcd(x, 0), do: x
  def gcd(x, y), do: gcd(y, rem(x, y))
end

Scoles