Standard Libraries vs Tail-Recursion

jgarrido

Hi, i have been working on a code that counts words on a file. I mostly used standard libraries from Elixir, then tried to run some tests to see how it responds. I tried a simple text with few words and something absolutely ireal with 500k lines of text.. And i tought it’s probably becouse of not using tail-call recursion instead of Enum and Map. The first thing i noticed is that memory usage is very high (on large file) but also that keeps some memory in use even when it finishes. Does tail-call solve this? Why is that memory still runing? how would you improve the code?
Here is my code:

defmodule RepeatedWords do

  def word_count(readFile) do
     readFile
     |> File.stream!
     |> sanitize
     |> count
     |> order
  end

  defp sanitize(words) do
    words
    |> Stream.map(&String.split(&1, ~r/(*UTF)\W/, trim: true))
    |> Enum.to_list
    |> List.flatten
    |> Enum.map(&String.downcase(&1))
  end

  defp count(words) when is_list(words) do
    Enum.reduce(words, %{}, &count_acc/2)
  end

  defp count_acc(word, acc) do
    Map.update(acc, String.to_atom(word), 1, &(&1 + 1))

  end

  defp order(words_count) do
    words_count
    |> Map.to_list()
    |> Enum.sort_by(&(elem(&1, 1)), :desc)
  end

end

7 comments

#performance #tail-call

1 1249 7

2022-03-21 13:05:59 UTC

Showing Posts 1 to 7

Show Best Posts
Show All (oldest first)
Show All (newest first)

NobbZ

You probably want to :binary.copy/1 individual chunks, to avoid keeping refs to the containing binary forever. The earlier you copy, the earlier the upper refs can be GC’d

Also, words |> Strem.map/2 |> Enum.to_list can be written as words |> Enum.map/2. The Enum.to_list/0 call forces the stream anyway.

Never do this! Just use the string as the key.

Post #1

alejolcc

String.to_atom(word)

Here is your answer, as @NobbZ says, try to avoid this. The atoms on the beam are not collected by the garbage collector, and that might be the cause of your memory increasing even after the code finished

Post #2

al2o3cr

A general note about using Stream functions: the benefit of streaming is not holding the whole file in memory. Calling Enum.to_list on the stream totally eliminates that benefit.

For instance:

readFile
|> File.stream!
|> Stream.flat_map(&String.split(...))
|> Stream.map(&String.downcase/1)
|> Enum.frequencies()

At runtime, this will only ever hold onto one “line” worth of memory along with the map of words → counts.

Post #3

NobbZ

This still has the references problem, as no explicit copy of the split substrings happens.

Post #4

al2o3cr

Looks like String.downcase reassembles the string from individual codepoints:

github.com/elixir-lang/elixir

lib/elixir/unicode/unicode.ex

18c44e2e4


      
          end
          
          def downcase(<<byte, rest::bits>>, acc, mode) do
            if byte >= ?A and byte <= ?Z do
              downcase(rest, [byte + 32 | acc], mode)
            else
              downcase(rest, [byte | acc], mode)
            end
          end
          
          def downcase("", acc, _mode), do: IO.iodata_to_binary(:lists.reverse(acc))
          
          # Sigma handling
          
          defp cased_letter_binary?(<<codepoint::utf8, rest::bits>>) do
            if case_ignorable?(codepoint) do
              cased_letter_binary?(rest)
            else
              cased_letter?(codepoint)
            end
          end

That should lose any reference to the original un-split binary, right?

Post #5

NobbZ

Indeed that should do it.

Post #6

jgarrido

Thanks all for the answers! I updated the code with some of your advices. It runs so efficiently now!

Here you can see it:

defmodule RepeatedWords do

  def word_count(readFile) do
     readFile
     |> File.stream!
     |> sanitize
     |> count
     |> order
  end

  defp sanitize(words) do
    words
    |> Stream.flat_map(&String.split(&1, ~r/(*UTF)\W/, trim: true))
    |> Stream.map(&String.downcase(&1))
  end

  defp count(words) do
    Enum.frequencies(words)
  end


  defp order(words_count) do
    words_count
    |> Enum.sort_by(&(elem(&1, 1)), :desc)
  end

end

I will still work more updates onto this, but im fascinated for the memory reduction with these changes (went from 3gb memory on large file to not going up of 25mb no matter what).

Post #7

— All posts loaded —