About 20 lines, about the same results: wc on Elixir

Six months ago, Chris Penner published Beating C With 80 Lines Of Haskell: Wc . The preface says:

The challenge is to build a smart clone optimized manually implementing tools wcto C in our favorite high-level language with garbage collection program - on the Haskell ! Sounds simple enough, right?

Chris went all the way from a simple implementation using ByteStrings , through monoids, built-in monoids, and finally came to a parallel multi-core version of the above, which managed to beat a little pure C- code at run time on four cores.

A few days ago on Habré was posted another note on the same topic from 0xd34df00d C Haskell: wc. The author proved the possibility to use idiomatic Haskell and twenty (20) lines of code to implement the algorithm, which is almost ten times faster than idiomatic implementation in the C .

Meanwhile, I advocate using Haskell (in fact, even Idris because of its dependent types) and Coq to really prove critical concepts in our code base; but everything that goes into production is still 100% Elixir / Erlang / OTP , because of their phenomenal fault tolerance. I wanted to make sure that I was not a stubborn ram who just liked the erlang syntax, and so I decided to check what we can do with the idiomatic elixir for the same task.

Below you will see some tricks that I used to gradually speed up the execution, bringing it to an acceptable level. I am already an adult and no longer believe in Santa Claus, and I did not cherish any hope of a miracle that Elixir can really defeat languages ​​that are compiled into machine code. I just wanted to make sure that at the finish we won’t lag behind the winners in a circle.

I am going to use exactly the same test file as0xd34df00d. So I downloaded it and glued it with myself ten times, as was bequeathed.

% for i in `seq 1 10`; cat part.txt >> test.txt
% du -sh test.txt
1.8G    test.txt

On my laptop (8 cores / 16G RAM), wcit takes about 10 seconds to process it.

time LANG=C LC_ALL=C wc data/test.txt 
  15000000   44774631 1871822210 data/test.txt
LANG=C LC_ALL=C wc data/test.txt  9,69s user 0,36s system 99% cpu 10,048 total

Well, let's see how much worse OTP will perform in this task .

A very naive attempt

, , , .

@acc %{bc: 0, wc: 1, lc: 0, ns?: 1}

@type acc :: %{
        bc: non_neg_integer(),
        wc: non_neg_integer(),
        lc: non_neg_integer(),
        ns?: 0 | 1
      }

@spec parse(<<_::_*8>>, acc()) :: acc()
def parse("", acc), do: acc

def parse(
      <<?\n, rest::binary>>,
      %{bc: bc, wc: wc, lc: lc, ns?: ns}
    ),
    do: parse(rest, %{bc: bc + 1, wc: wc + ns, lc: lc + 1, ns?: 0})

def parse(
      <<?\s, rest::binary>>,
      %{bc: bc, wc: wc, lc: lc, ns?: ns}
    ),
    do: parse(rest, %{bc: bc + 1, wc: wc + ns, lc: lc, ns?: 0})

def parse(<<_, rest::binary>>, acc),
  do: parse(rest, %{acc | bc: acc.bc + 1, ns?: 1})

File.read!/1, File.stream!/3:

@spec lazy(binary) :: acc()actually
def lazy(file),
  do: file |> File.stream!() |> Enum.reduce(@acc, &parse/2)

@spec greedy(binary) :: acc()
def greedy(file),
  do: file |> File.read!() |> parse(@acc)

, , . ; , wc . , ( μs).

iex|1> :timer.tc fn -> Wc.lazy "data/part.txt" end
#⇒ {16_737094, %{bc: 185682221, lc: 1500000, ns?: 1, wc: 4477464}}
iex|2> :timer.tc fn -> Wc.greedy "data/part.txt" end
#⇒ {13_659356, %{bc: 187182221, lc: 1500000, ns?: 1, wc: 4477464}}

, , ? , , .

- -

, ? , . , ?\s ?\n —  —  . , , , . , - ( .)

@prehandle 42
@sink @prehandle + 1

@spec parse(<<_::_*8>>, acc()) :: acc()

Enum.each(0..@prehandle, fn i ->
  def parse(
        <<_::binary-size(unquote(i)), ?\n, rest::binary>>,
        %{bc: bc, wc: wc, lc: lc, ns?: ns}
      ),
      do: parse(rest, acc!(unquote(i), bc, wc, lc + 1, ns))

  def parse(
        <<_::binary-size(unquote(i)), ?\s, rest::binary>>,
        %{bc: bc, wc: wc, lc: lc, ns?: ns}
      ),
      do: parse(rest, acc!(unquote(i), bc, wc, lc, ns))
end)

def parse(<<_::binary-size(@sink), rest::binary>>, acc),
  do: parse(rest, %{acc | bc: acc.bc + @sink, ns?: 1})

Enum.each(@prehandle..0, fn i ->
  def parse(<<_::binary-size(unquote(i))>>, acc),
    do: %{acc | bc: acc.bc + unquote(i), ns?: 1}
end)

acc!  —  , , .

, ,  — ? , -, . 130 (43 EOL, ,  — :

• Taumatawhakatangi­hangakoauauotamatea­turipukakapikimaunga­horonukupokaiwhen­uakitanatahu,
• Llanfair­pwllgwyngyll­gogery­chwyrn­drobwll­llan­tysilio­gogo­goch,

.

iex|1> :timer.tc fn -> Wc.greedy "data/part.txt" end      
#⇒ {2_569929, %{bc: 187182221, lc: 1500000, ns?: 1, wc: 4477464}}
iex|2> :timer.tc fn -> Wc.lazy "data/part.txt" end  
#⇒ {6_616190, %{bc: 185682221, lc: 1500000, ns?: 1, wc: 4477464}}

, , , wc (, 2.5 ).

, , , , . , , . , NIF, ,  —  . , . , Erlang/OTP , , , . - ( ), . , ; , Flow.

12% ,

, , , (, , - ). mix.exs ( escript, , ).

def project do
  [
    app: :wc,
    version: "0.1.0",
    elixir: "~> 1.9",
    start_permanent: Mix.env() == :prod,

    escript: [main_module: Wc.Main],
    deps: [{:flow, "~> 1.0"}]
  ]
end

.

@chunk 1_000_000

@spec flowy(binary()) :: acc()
def flowy(file) do
  file
  |> File.stream!([], @chunk)
  |> Flow.from_enumerable()
  |> Flow.partition()
  |> Flow.reduce(fn -> @acc end, &parse/2)
  |> Enum.to_list()
end

( ) , , 1M. .

!

iex|1> :timer.tc fn -> Wc.flowy "data/part.txt" end
#⇒ {0_752568, %{bc: 187182221, lc: 1500000, ns?: 1, wc: 4477464}}
iex|2> :timer.tc fn -> Wc.flowy "data/test.txt" end
#⇒ {7_815592, %{bc: 1871822210, lc: 15000000, ns?: 1, wc: 44774631}}

! , (1.8 ). , , wc , , , , . , , : , , . mix escript.build , , .

time LANG=C LC_ALL=C wc data/test.txt
  15000000   44774631 1871822210 data/test.txt
LANG=C LC_ALL=C wc data/test.txt  9,71s user 0,39s system 99% cpu 10,104 total

time ./wc data/test.txt
    15000000    44774631    1871822210  data/test.txt
./wc data/test.txt  41,72s user 2,31s system 706% cpu 6,355 total

.

( main, escript) —  . , , —  20 ,

!