👓 🕎 🙌🏾 Environ 20 lignes, à peu près les mêmes résultats: wc sur Elixir 📌 🗳️ 🦍

Il y a six mois, Chris Penner a publié Beating C With 80 Lines Of Haskell: Wc . La préface dit:

Le défi est de construire un clone intelligent optimisé implémentant manuellement des outils wcen C dans notre langage de haut niveau préféré avec programme de collecte des ordures - sur le Haskell ! Cela semble assez simple, non?

Chris est allé d'une implémentation simple à l'aide de ByteStrings , à des monoïdes, des monoïdes intégrés, et est finalement arrivé à une version multicœur parallèle de ce qui précède, qui a réussi à battre un peu de code C pur au moment de l'exécution sur quatre cœurs.

Il y a quelques jours sur Habré a été publié une autre note sur le même sujet 0xd34df00d C Haskell: wc. L'auteur a prouvé la possibilité d'utiliser idiomatiques Haskell et vingt (20) lignes de code pour mettre en œuvre l'algorithme, ce qui est dix fois presque plus rapide que la mise en œuvre idiomatiques dans C .

Pendant ce temps, je préconise d'utiliser Haskell (en fait, même Idris en raison de ses types dépendants) et Coq pour vraiment prouver les concepts critiques dans notre base de code; mais tout ce qui entre en production est toujours 100% Elixir / Erlang / OTP , en raison de leur tolérance aux pannes phénoménale. Je voulais m'assurer que je n'étais pas un bélier têtu qui aimait juste la syntaxe erlang, et j'ai donc décidé de vérifier ce que nous pouvons faire avec l' élixir idiomatique pour la même tâche.

Ci-dessous, vous verrez quelques astuces que j'ai utilisées pour accélérer progressivement l'exécution, l'amenant à un niveau acceptable. Je suis déjà adulte et je ne crois plus au Père Noël, et je ne chérissais aucun espoir de miracle qu'Elixir puisse vraiment vaincre les langages compilés en code machine. Je voulais juste m'assurer qu'à l'arrivée nous ne prendrons pas de retard sur les vainqueurs dans un cercle.

Je vais utiliser exactement le même fichier de test que0xd34df00d. Je l'ai donc téléchargé et collé avec moi-même dix fois, comme cela a été légué.

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

Sur mon ordinateur portable (8 cœurs / 16 Go de RAM), wcil faut environ 10 secondes pour le traiter.

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

Eh bien, voyons à quel point le protocole OTP sera pire dans cette tâche .

Une tentative très naïve

, , , .

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

Environ 20 lignes, à peu près les mêmes résultats: wc sur Elixir

Une tentative très naïve

- -

12% ,

More articles: