++ Operator Performance Gotcha

While going through the Programming Elixir Show archive.org snapshot book by Dave Thomas, one of the exercises was to implement Enum.split ( see the docs here Show archive.org snapshot ):

CopyEnum.split(list, count) => { count_elems_from_front, remaining_elems }

My first attempt looked like this:

Copydef split([], _), do: {[], []}
def split(list, 0), do: { [], list }
def split([head | tail], count) do
  _split(tail, count - 1, [head])
end

defp _split([], _, front) do
  { front, [] }
end
defp _split(back, 0, front) do
  { front, back }
end
defp _split([head | tail], count, front) do
  # ++ makes this O(n^2) !!!!!
  _split(tail, count - 1, front ++ [head])
end

(Note: doesn't implement negative split counts like the real one)

There were some distinct smells for me here: my colleague Alan had already said earlier in the week to watch out for too many match functions - it can be a hint that you've done something wrong. Plus I remembered there was something costly about using the ++ (list concat) operator (see myth 2.4 of the The Eight Myths of Erlang Performance Show archive.org snapshot ).

I decided to test out my solution on various input sizes. On small lists it ran acceptably fast. But as the input size grew, it got slower and slower. With a list of only 100,000 elements it took 30 seconds to complete on my MacBook Pro.

Copyiex> big = Enum.to_list(1..100_000)
iex> MyEnum.split(big, 100_000)
# ... 30s ...

Based on what I new about the ++ operator, I assumed that to be the source of the problem. In order to preserve immutability it makes a copy of its left hand operand. Because I'm using it in a recursive loop that visits every element in the list, it's copying everything already seen, in each iteration of the loop. This means that for the worst case, where the split count is equal to the size of the input, its running time will grow quadratically: O(n²).

Copy# Worst case input
iex> MyEnum.split(n_elements, n) => { [...], [] }.

Being new to functional programming, I made several attempts to try and iron this problem out. In an imperative language you would just have two new lists, iterate through filling the first up until the count, then put the remainder into the second. O(n) right? But how to do this in Elixir?

The solution in the end was to compromise on O(2n); twice through the list. I had jumped ahead to the Enum.take exercise:

Copydef take([], _), do: []
def take(_, 0), do: []
def take([head | tail], count) do
  # O(n)
  [head | take(tail, count-1)]
end

Then it occurred to me to implement Enum.drop too:

Copydef drop([], _), do: []
def drop(list, 0), do: list
def drop([_ | tail], count) do
  # O(n)
  drop(tail, count - 1)
end

Then the split could be implemented acceptably fast as:

Copydef faster_split([], _), do: { [], [] }
def faster_split(list, 0), do: { [], list }
def faster_split(list, count) do
  # O(2n) :)
  front = take(list, count)
  back = drop(list, count)
  { front, back }
end

Now the running time for the worst case with 100,000 elements dropped to below a second!

It doesn't matter that it is enumerating the input twice, the fact that the complexity now grows linearly and not quadratically is the most significant factor. So really we can consider this a O(n) solution.

So the lessons learned:

• Although the ++ operator is not always bad, don't use it to append to the end of lists in loops!
• Don't forget to test your implementations with large and small inputs.

PS this still isn't optimal. Looking at Dave Thomas' solution from the PragProg forum Show archive.org snapshot (expand the "A possible solution" bit):

Copydef split(list, count),      do: _split(list, [], count)
defp _split([], front, _),   do: [ Enum.reverse(front), [] ]
defp _split(tail, front, 0), do: [ Enum.reverse(front), tail ]
defp _split([ head | tail ], front, count)  do
  _split(tail, [head|front], count-1)
end

It builds the front list backwards then reverses it when complete. Still technically O(2n) because it swaps my drop for a reverse, which I assume is O(n). However, it uses Tail Recursion which should be more stack space efficient.

So there's another trick to note: don't be afraid to pay the cost of a reverse so that you can build your list efficiently.