Improving a slow solution for Longest Collatz Sequence

Questions / Help
3

Sometimes an equivalent Ruby code will be faster than its Elixir counterparts. Some reasons I’ve seen are:

  1. Some Ruby functions are powered by C, whereas Elixir functions are not.
  2. There is some cost to pay for immutability.
  3. Integer math is not really fast in Erlang.

In my experience these things rarely matter in the grand scheme of things. In 7 years of working with Erlang in production I didn’t have much needs to move outside of Erlang, the most frequent (but still very rare) example being encoding/decoding of large jsons.

In any case, in these synthetic examples Ruby (and many other langs) might win for some naive implementation, but before discarding Elixir, there are two options to be considered:

  1. Algoritjmical optimization
  2. Technical optimization

If you can do something with 1, then you might get huge improvements to the point where the diff between Elixir and X is insignificant. I’m not familiar with Collatz seq, so I don’t know if there’s some improvement that can be done in the algorithm. So I tried a couple of technical tricks. They are quite ugly, but they did help.

The first thing to do is to not use the time OS command, because that also measures the boot time of the VM, as well as compilation of your code. Instead use :timer.tc to measure the running time of your code. That immediately shaved off half a second on my machine.

The next thing I did is very ugly. I reached for the universally hated process dictionary. I really wouldn’t recommend that in real life, but it did help tremendously here, cutting the running time in half. Finally, for a bit of additional gain, I used Bitwise instead of rem and div. This gained additional ~100msec on my machine.

The final version takes about 900 msec (originally it was about 3 sec). The ruby version takes about 1200 msec on my machine (it’s ruby 2.0). Perhaps there are better (and less ugly) approaches, but this is the best I came up with after a quick hack session.

Before showing the code I want to touch on this:

This is not a problem, it is a property :slight_smile: If you want to crunch a lot of numbers in a one-off computation as fast as possible, Elixir/Erlang are bad choices to begin with, as is Ruby for that matter. I wouldn’t look far beyond C/C++ for those kinds of jobs.

The real problem is to extrapolate that based on this naive example Elixir is always going to be slower than Ruby (or any other X) or worse than Ruby (raw CPU speed is not the only property in software, and in some types of software, such as backend systems, it’s often not the most important one).

In any case, here’s my very hacky take on this. It’s not really tested, and I wouldn’t recommend using these techniques in production :slight_smile:

defmodule Collatz do
  import Bitwise

  def max_len(range) do
    {max, max_len} =
      Enum.reduce(range, {0, 0},
        fn n, {_, max_len} = acc ->
          len = len(n)
          Process.put(n, len)
          if len > max_len, do: {n, len}, else: acc
        end
      )

    %{max: max, max_len: max_len}
  end

  defp len(value) do
    case Process.get(value) do
      nil ->
        case next(value) do
          1 -> 2
          next -> 1 + len(next)
        end
      len -> len
    end
  end

  defp next(x), do:
    if band(x, 1) == 0, do: x >>> 1, else: 3 * x + 1
end

{time, result} = :timer.tc(fn -> Collatz.max_len(1..1_000_000) end)
IO.puts "Time: #{div(time, 1000)}ms"
IO.inspect result

$ elixir test.ex
Time: 864ms
%{max: 837799, max_len: 525}
4 Likes