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

Abs picture Abs · Sep 7, 2015 · Viewed 7.8k times · Source

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

Answer

Roman Smirnov picture Roman Smirnov · Sep 7, 2015

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.