Get best of the week

Cerca de 20 linhas, aproximadamente os mesmos resultados: wc no Elixir

Seis meses atrás, Chris Penner publicou Beating C With 80 Lines Of Haskell: Wc . O prefácio diz:


O desafio é criar um clone inteligente otimizado manualmente implementando ferramentas wcpara C em nossa linguagem de alto nível favorita com programa de coleta de lixo - no Haskell ! Parece bastante simples, certo?

Chris passou de uma implementação simples usando ByteStrings , através de monoids, monoids embutidos e finalmente chegou a uma versão multi-core paralela acima, que conseguiu vencer um pouco de código C puro em tempo de execução em quatro núcleos.


Alguns dias atrás, em Habré, foi postada outra nota sobre o mesmo tópico de 0xd34df00d C Haskell: wc. O autor provou a possibilidade de usar idiomática Haskell e 20 (vinte) linhas de código para implementar o algoritmo, que é quase dez vezes mais rápido do que a implementação idiomática em o C .


Enquanto isso, defendo o uso de Haskell (de fato, até Idris por causa de seus tipos dependentes) e Coq para realmente provar conceitos críticos em nossa base de código; mas tudo o que entra em produção ainda é 100% Elixir / Erlang / OTP , devido à sua tolerância fenomenal a falhas. Eu queria ter certeza de que não era um carneiro teimoso que apenas gostasse da sintaxe erlang e, por isso, decidi verificar o que poderíamos fazer com o elixir idiomático para a mesma tarefa.


Abaixo você verá alguns truques que eu usei para acelerar gradualmente a execução, elevando-a a um nível aceitável. Eu já sou adulto e não acredito mais no Papai Noel, e não tinha nenhuma esperança de um milagre que o Elixir pudesse realmente derrotar idiomas que são compilados em código de máquina. Eu só queria ter certeza de que, no final, não ficaremos atrás dos vencedores em um círculo.


Vou usar exatamente o mesmo arquivo de teste que0xd34df00d. Então eu baixei e colei comigo dez vezes, como foi legado.


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

No meu laptop (8 núcleos / 16G RAM), wcleva cerca de 10 segundos para processá-lo.


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

Bem, vamos ver o quanto o OTP terá pior desempenho nesta tarefa .


Uma tentativa muito ingênua


, , , .


@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, ,  — :



.


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 ,



!

More articles:


All Articles