Erlang/Elixir string performance - can this be improved?

Welcome to the forum,

There is a better implementation

PS: You might have a look at Flow as the example is about counting words in a textfile.

Could you share a link to the input?

I tried generating it and

➜  llvm-8.0.0.src find . -type f | xargs cat | tr -sc 'a-zA-Z0-9_' ' ' | ../lines > words.txt
tr: Illegal byte sequence

To be precise, what is slow in this case is not the string processing, but the fact that Map is a immutable data-structure. For example, using :ets.update_counter/4 should speed up things considerably. The documentation for Flow talks about this too.

For me

% find . -type f | xargs cat | LANG="en_US.ISO-8859-1" tr -sc 'a-zA-Z0-9_' ' ' | ../lines > words.txt

did work. I put it on my server as well (http://teralink.net/\~serpent/words.txt).

For reference, your original code took 1:54 total on my machine.

Simply running

IO.stream(:stdio, :line)
|> Stream.flat_map(&(String.split(&1)))
|> Stream.run()

takes around 35s on my machine. So just reading from IO and splitting is already slower than the full ruby implementation.

Switching to IO.binstream speeds it up from 35 to 25s , so that’s one step. The difference is that we don’t have UTF8 support, which I assume most of the implementations don’t bother with anyway.

Next lets take a look at @josevalim’s suggestion of using ETS

# Create the ETS table
:ets.new(:words, [{:write_concurrency, true}, :named_table])

# setup input stream for reading and tokenisation
IO.binstream(:stdio, :line)
|> Stream.flat_map(&String.split(&1))
# Insert and update counters for each word in table
|> Enum.each(fn word -> :ets.update_counter(:words, word, {2, 1}, {word, 0}) end)

# Read all rows from the table
:ets.match_object(:words, {:"$0", :"$1"})
|> Enum.sort(fn {_, a}, {_, b} -> b < a end)
# print it beautifully
|> Enum.each(fn {word, count} ->
  IO.puts(String.pad_leading(Integer.to_string(count), 8) <> " " <> word)
end)

This runs in 42s on my machine, so we’ve made a big improvement from 114s. We can shave another 2s off by replacing the last line with building an iolist.

|> Enum.map(fn {word, count} ->
  [String.pad_leading(Integer.to_string(count), 8), " ", word, "\n"] end)
|> IO.puts

But we’re still not really using the concurrency available to Elixir. @kokolegorille suggested using Flow, which lets us easily run on more than one core. Using almost the exact example posted in the documentation for Flow I ran

IO.binstream(:stdio, :line)
|> Flow.from_enumerable()
|> Flow.flat_map(&String.split(&1))
|> Flow.partition()
|> Flow.reduce(fn -> %{} end, fn word, acc ->
  Map.update(acc, word, 1, & &1 + 1)
end)
|> Enum.sort(fn {_, a}, {_, b} -> b < a end)
|> Enum.map(fn {word, count} ->
  [String.pad_leading(Integer.to_string(count), 8), " ", word, "\n"] end)
|> IO.puts

which finishes in 21s. That means we’ve caught up with ruby. But I dropped ETS, so lets bring it back.

:ets.new(:words, [{:write_concurrency, true}, :named_table, :public])

IO.binstream(:stdio, :line)
|> Flow.from_enumerable()
|> Flow.flat_map(&String.split(&1))
|> Flow.partition()
|> Flow.each(fn word ->
  :ets.update_counter(:words, word, {2, 1}, {word, 0})
end)
|> Flow.run()

:ets.match_object(:words, {:"$0", :"$1"})
|> Enum.sort(fn {_, a}, {_, b} -> b < a end)
|> Enum.map(fn {word, count} ->
  [String.pad_leading(Integer.to_string(count), 8), " ", word, "\n"] end)
|> IO.puts

This doesn’t run any faster than the previous Flow version, still clocking in at 21s (saw some variance, maybe 20-22s, not surprising since I’m using around 7/8 virtual cores and I have lots of apps running). I’m not really sure why it’s not faster, considering we’re avoiding updating a Map. I’m curious if there’s a smarter way of reading the ETS table, maybe even in a sorted fashion?

Finally, the original post claims to allow VMs startup time before measuring, which your examples of using time does not. Timing the code from start to finish gives me an actual time of at least 0.6s less than what time reports. If you want to get more accurate than that you’ll need to use a proper testing harness like GitHub - bencheeorg/benchee: Easy and extensible benchmarking in Elixir providing you with lots of statistics! · GitHub

ps fun note about ETS, without {:write_concurrency, true} the final version takes 120s instead of 21s

pps noticed I forgot an unnecessary .partition in the final version. Removing it yields a run time of ~17s.

Not sure if we can get sorting but using Erlang’s relatively new :counters module should be even faster than ETS in this case.

Great summary @jola!

Note that If you are using ETS, you don’t need partition. So the previous version was also correct. In fact, if you don’t need partition for this example, you likely don’t need flow either and IO.binstream+Task.async_stream will most likely be fine.

For reading ETS, you can also use :ets.tab2list to get the whole table as a list, but I am not sure if it makes a big difference.

counters require an index (integer) as a key, so you would need a way to convert words into integers which may end-up offsetting the benefits you would get from counterss.

Forenote: I’m on Windows using Git Bash so my IO is garbage

I tried some of the code, first I used the words.txt file that @serpent provided and since I’m dumb and I don’t know how to feed from cat to elixir I used File.stream!/1 sorry!
But the points that I want to shared that at least occurred on my machine was :

• String.split/3 on: |> Stream.flat_map(&String.split(&1, " ")) is faster than String.split/1 for splitting at spaces
• Printing the values also adds a lot of overhead

I came to the loose conclusion that iterating and strings are not the weak point but the IO devices are?

Here is the code:

# file: wc.exs


# removes 20ms from creation
:ets.new(:words, [{:write_concurrency, true}, :named_table])

c = fn ->

  File.stream!("words.txt")
  |> Stream.flat_map(&String.split(&1, " ")) # using space decrease from approx half than using split/1
  |> Enum.each(fn word -> :ets.update_counter(:words, word, {2, 1}, {word, 0}) end)
  :ets.match_object(:words, {:"$0", :"$1"})
  |> Enum.sort(fn {_, a}, {_, b} -> b < a end)
  # print it beautifully
  |> Enum.each(fn {word, count} ->
    # print does add overhead from 187 to 2282
    IO.puts(String.pad_leading(Integer.to_string(count), 8) <> " " <> word)
  end)
end

# only time code execution, not vm start
{micro, :ok} = :timer.tc(c)
IO.puts("#{micro/1000}ms")

Run with: $ elixir wc.exs

You can do this to verify. Replace this:

|> Enum.each(fn {word, count} ->
  IO.puts(String.pad_leading(Integer.to_string(count), 8) <> " " <> word)
end)

by this:

|> Enum.map(fn {word, count} ->
  [String.pad_leading(Integer.to_string(count), 8), " ", word, "\n"]
end)
|> IO.write()

Eked out a another 3s improvement by compiling a pattern for String.split. Now down to 14s run time. Also, if I switch to File.stream! instead of IO.binstream I’m down to 12s, but I’ll stick with the original code since that was part of the challenge.

defmodule App do
  def run do
    :ets.new(:words, [{:write_concurrency, true}, :named_table, :public])
    space = :binary.compile_pattern([" ", "\n"])

    IO.binstream(:stdio, :line)
    |> Flow.from_enumerable()
    |> Flow.flat_map(&String.split(&1, space))
    |> Flow.each(fn word ->
      :ets.update_counter(:words, word, {2, 1}, {word, 0})
    end)
    |> Flow.run()

    :ets.match_object(:words, {:"$0", :"$1"})
    |> Enum.sort(fn {_, a}, {_, b} -> b < a end)
    |> Enum.map(fn {word, count} ->
      [String.pad_leading(Integer.to_string(count), 8), " ", word, "\n"]
    end)
    |> IO.puts
  end
end

IO.puts(:stderr, elem(:timer.tc(&Aapp.run/0), 0))

in comparison the Flow-less synchronous version runs in 25s

defmodule App do
  def run do
    :ets.new(:words, [{:write_concurrency, true}, :named_table])
    space = :binary.compile_pattern([" ", "\n"])

    IO.binstream(:stdio, :line)
    |> Stream.flat_map(&String.split(&1, space))
    |> Enum.each(fn word -> :ets.update_counter(:words, word, {2, 1}, {word, 0}) end)

    :ets.match_object(:words, {:"$0", :"$1"})
    |> Enum.sort(fn {_, a}, {_, b} -> b < a end)
    |> Enum.map(fn {word, count} ->
      [String.pad_leading(Integer.to_string(count), 8), " ", word, "\n"] end)
    |> IO.puts
  end
end

IO.puts(:stderr, elem(:timer.tc(&App.run/0), 0))