Need advice to improve an OOP code to Elixir (make more functional)

[alichoopani]

I came across such a piece of code and tried to implement it functionally. I found various ways to do it and benchmarked them using Benchee and I got some interesting results.
Codes and results can be seen in this gist.

First of all, I realized the huge negative impact of using ++ to add items to the list.
I expected using Enum.reduce/2 and Enum.map_reduce/3 to perform best, followed by tail_recursion_with_reverse/2 and then recursion/2. But the results were almost the opposite.
Now I have some questions that I will ask. Thanks in advance for all the feedback and help.

1. In order to benchmark such questions, what other items should I consider in addition to the average execution time?
2. That being said, is there any situation where ++ is the right choice for working with lists?
3. Is there a better solution to this problem?
4. Is it always better to write recursive functions in general than to use Enum functions?
5. Does ‌Beam perform a special optimization in the recursion/2 function that is written in the code, which performs better than tail_recursion_with_reverse/2?

  def reduce(items, y) do
    {items, _} = Enum.reduce(items, {[], y},
      fn %{height: h} = item, {converted_items, y} -> {converted_items ++ [%{item | y: y}], y + h} end)
    items
  end

  def reduce_with_reverse(items, y) do
    {items, _} = Enum.reduce(items, {[], y},
      fn %{height: h} = item, {converted_items, y} -> {[%{item | y: y} | converted_items], y + h} end)
    Enum.reverse(items)
  end

  def map_reduce(items, y) do
    {items, _} = Enum.map_reduce(items, y, fn item, acc -> {Map.put(item, :y, acc), acc + item.height} end)
    items
  end

  def recursion([], _), do: []
  def recursion([%{height: h} = item | t], y), do: [%{item | y: y} | recursion(t, h + y)]

  def tail_recursion(items, y, converted_items \\ [])
  def tail_recursion([], _y, converted_items), do: converted_items
  def tail_recursion([h | t], y, converted_items), do:
    tail_recursion(t, y + h.height, converted_items ++ [%{y: y, height: h.height}])

  def tail_recursion_with_reverse(items, y, converted_items \\ [])
  def tail_recursion_with_reverse([], _y, converted_items), do: Enum.reverse(converted_items)
  def tail_recursion_with_reverse([h | t], y, converted_items), do:
    tail_recursion_with_reverse(t, y + h.height, [%{y: y, height: h.height} | converted_items])

[mpope]

For point 2, using ++ is relatively cheap when adding a new element to the end of a list, such as:

[1, 2, 3] ++ [4]

Only a single element suffers from the left hand copy in that case.

As for recursion out performing tail_recursion_with_reverse, there is the overhead of the reverse to consider. That is one less n length operation that the function needs to perform. I suggest you checkout The Seven Myths of Erlang Performance. They explain the history behind the assumption that tail recursion is more performant.

As for question 3, I personally prefer pure recursive functions over the standard libraries when the task is simple. The recursion function is simple and elegant. But that is personal preference, and optimization should only be done after measurement in production, so any of the above solutions will be fine in most scenarios.

As for question 1, I’d suggest trying Streams, and maybe ParallelStream, and also trying a recursive solution with a preallocated tuple instead of a list accessed with element/2. Could get a speedup from the spacial cache locality.

Also as a note, function calls and pattern matching aren’t ‘free’. It looks like recursion uses the least amount of both function calls and branches. That could give things a boost as well.

Nice benchmark!

[lud]

In order to benchmark such questions, what other items should I consider in addition to the average execution time?

You may look at Benchee, it’s great.

That being said, is there any situation where ++ is the right choice for working with lists?

When you are mapping / reducing over a list, it’s alway better not to use ++. But sometimes you get a list from elsewere and the only thing you have to do with it is to append. In that case the better choice is ++. This operator is not forbidden A general rule of thumb is “do not use ++ in a loop, only once.”

Is there a better solution to this problem?

I find that your map_reduce implementation is the cleanest of all. There may be other solutions but I would just use the more readable. A tip though: you can put the clauses matching on [] (empty list) below the clause matching on items. There is no need to try this clause at each loop iteration.

Is it always better to write recursive functions in general than to use Enum functions?

I think that “better” depends on what you want. If you need the best performance, then custom recursive function should be faster. If you want clean code, I think Enum.map() is better as you will separate the logic from the unpacking/repacking of the list items. For reduce() it depends.

Does Beam perform a special optimization in the recursion/2 function that is written in the code, which performs better than tail_recursion_with_reverse/2?

There is this note in erlang docs:

A tail-recursive function that does not need to reverse the list at the end is faster than a body-recursive function, as are tail-recursive functions that do not construct any terms at all (for example, a function that sums all integers in a list).

source.

In your case, you have reverse, so it is not certain that it will be faster than the body-recursive function.

@mpope

[1, 2, 3] ++ [4]

Only a single element suffers from the left hand copy in that case.

I don’t think so. This snippets builds a new list like this : [1|[2|[3|[4]]]], it re-builds the full list of 4 items. This is why ++ is generally avoided, because it creates a copy of the left-hand list. If you need to concat 2 lists then it is fine, but it is not recommended to append a few items to a large list.

[al2o3cr]

I personally prefer Enum functions chained together, for instance:

  def enum_chain(items, y) do
    new_ys =
      [y | Enum.scan(items, y, fn item, acc -> item.height + acc end)]

    items
    |> Enum.zip(new_ys)
    |> Enum.map(fn {item, new_y} -> %{item | y: new_y} end)
  end

This produces a little more garbage to collect, due to intermediate results - but each step has a clear responsibility and is readable at a glance (assuming you remember Enum.scan )

If items is large, you could avoid that garbage generation by using Stream:

  def stream_chain(items, y) do
    new_ys =
      Stream.concat([y], Stream.scan(items, y, fn item, acc -> item.height + acc end))

   items
   |> Stream.zip(new_ys)
   |> Enum.map(fn {item, new_y} -> %{item | y: new_y} end)
  end

In this case there are drop-in Stream replacements for Enum functions, so the code doesn’t materially change. This implementation trades off performance for efficiency: no intermediate values to GC but longer runtime because Stream uses lots of anonymous functions.

[alichoopani]

Thanks for the explanation and links. I need to read about Stream and ParallelStream.

[alichoopani]

A tip though: you can put the clauses matching on [] (empty list) below the clause matching on items. There is no need to try this clause at each loop iteration.

I tested something like this but it doesn’t seem to make a difference. Is it possible to introduce me to a source about this?

  def recursion([], _), do: []
  def recursion([%{height: h} = item | t], y), do: [%{item | y: y} | recursion(t, h + y)]

  def recursion_unordered_clause([%{height: h} = item | t], y), do: [%{item | y: y} | recursion_unordered_clause(t, h + y)]
  def recursion_unordered_clause([], _), do: []

and thanks a lot for your advice.

[sabiwara]

@al2o3cr

    items
    |> Enum.zip(new_ys)
    |> Enum.map(fn {item, new_y} -> %{item | y: new_y} end)

I think this could be replaced by Enum.zip_with/3 in Elixir 1.12+:

Enum.zip_with(items, new_ys, fn item, new_y -> %{item | y: new_y} end)

Very often, Enum provides efficient ways of doing operations in one pass without building the intermediate list, for example Enum.map_join/3 is more efficient than Enum.map |> Enum.join.

[alichoopani]

You introduced interesting solutions. I’m new and I don’t know much about the stream and I need to read about it. How can I measure efficiency?
Thank you very much for your guidance.

[lud]

Sorry I don’t know a source for this. I just know that the VM will try all clauses in function heads or case in order of appearance, and use the first that matches.

So if you have a list with 100 items and this code:

def f([]), do: :ok
def f([h | t]), do: stuff(h); f(t)

On each one of the100 items there will be 2 clauses tested and then one last with the empty list, so 201 match attempts. If you reverse the clauses there will be 101 match attempts. That is because [h | _] cannot match an empty list.

Now be warned, %{} will match any map.

[Sebb]

@lud

I just know that the VM will try all clauses in function heads or case in order of appearance, and use the first that matches.

While being fully aware of this (and using it in lots of functions with multiple heads) my recursive functions all have the base case f([]) at the top.

Never thought about it.

… lets do some git branch refact

[sabiwara]

You might not need to

From the efficiency guide

Pattern matching in function head as well as in case and receive clauses are optimized by the compiler. With a few exceptions, there is nothing to gain by rearranging clauses.

There seems to be some gotchas and edge cases, but most of the time this should make no difference.

[lud]

Oh that is good to know.