Get best of the week

Cerca de 20 líneas, casi los mismos resultados: wc en Elixir

Hace seis meses, Chris Penner publicó Beating C With 80 Lines Of Haskell: Wc . El prefacio dice:


El desafío es construir un clon inteligente optimizado manualmente implementando herramientas wcpara C en nuestro lenguaje favorito de alto nivel con el programa de recolección de basura - en Haskell ! Suena bastante simple, ¿verdad?

Chris pasó de una implementación simple usando ByteStrings , a través de monoides, monoides incorporados, y finalmente llegó a una versión paralela de múltiples núcleos de lo anterior, que logró vencer un poco de código C puro en tiempo de ejecución en cuatro núcleos.


Hace unos días en Habré se publicó otra nota sobre el mismo tema de 0xd34df00d C Haskell: wc. El autor demostró la posibilidad de utilizar idiomática Haskell veinte (20) líneas de código y para implementar el algoritmo, que es casi diez veces más rápido que la implementación idiomática en el C .


Mientras tanto, defiendo el uso de Haskell (de hecho, incluso Idris debido a sus tipos dependientes) y Coq para probar realmente los conceptos críticos en nuestra base de código; pero todo lo que entra en producción sigue siendo 100% Elixir / Erlang / OTP , debido a su fenomenal tolerancia a fallas. Quería asegurarme de que no era un carnero terco al que solo le gustaba la sintaxis de erlang, por lo que decidí verificar qué podemos hacer con el elixir idiomático para la misma tarea.


A continuación verá algunos trucos que usé para acelerar gradualmente la ejecución, llevándola a un nivel aceptable. Ya soy un adulto y ya no creo en Santa Claus, y no tenía ninguna esperanza de un milagro de que Elixir realmente pudiera derrotar a los idiomas que se compilan en código máquina. Solo quería asegurarme de que al final no nos quedaremos atrás de los ganadores en un círculo.


Voy a usar exactamente el mismo archivo de prueba que0xd34df00d. Así que lo descargué y lo pegué conmigo diez veces, como fue legado.


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

En mi computadora portátil (8 núcleos / 16G de RAM), wctoma alrededor de 10 segundos procesarla.


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

Bueno, veamos cuánto peor OTP realizará en esta tarea .


Un intento muy ingenuo


, , , .


@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