Get best of the week

Ungefähr 20 Zeilen, ungefähr die gleichen Ergebnisse: wc auf Elixir

Vor sechs Monaten veröffentlichte Chris Penner Beating C mit 80 Zeilen von Haskell: Wc . Das Vorwort sagt:


Die Herausforderung besteht darin, einen intelligenten Klon zu erstellen, der für die manuelle Implementierung von Tools wcin C in unserer bevorzugten Hochsprache mit Garbage Collection-Programm optimiert ist - auf dem Haskell ! Klingt einfach genug, oder?

Chris ging den ganzen Weg von einer einfachen Implementierung mit ByteStrings über Monoide, integrierte Monoide und kam schließlich zu einer parallelen Multi-Core-Version des oben genannten, die es schaffte, zur Laufzeit auf vier Kernen ein wenig reinen C- Code zu schlagen .


Vor ein paar Tagen wurde auf Habré eine weitere Notiz zum gleichen Thema von veröffentlicht 0xd34df00d C Haskell: wc. Der Autor bewies die Möglichkeit zu nutzen idiomatische Haskell und zwanzig (20) Codezeilen um den Algorithmus zu implementieren, die fast zehnmal schneller ist als idiomatische Implementierung in der C .


In der Zwischenzeit befürworte ich die Verwendung von Haskell ( aufgrund seiner abhängigen Typen sogar Idris ) und Coq , um kritische Konzepte in unserer Codebasis wirklich zu beweisen. Aber alles, was in Produktion geht , ist aufgrund ihrer phänomenalen Fehlertoleranz immer noch 100% Elixier / Erlang / OTP . Ich wollte sicherstellen, dass ich kein hartnäckiger Widder bin, der nur die Erlang-Syntax mag, und deshalb habe ich beschlossen, zu prüfen, was wir mit dem idiomatischen Elixier für dieselbe Aufgabe tun können .


Im Folgenden sehen Sie einige Tricks, mit denen ich die Ausführung schrittweise beschleunigt und auf ein akzeptables Niveau gebracht habe. Ich bin bereits erwachsen und glaube nicht mehr an den Weihnachtsmann. Ich hatte keine Hoffnung auf ein Wunder, dass Elixir Sprachen, die zu Maschinencode kompiliert wurden, wirklich besiegen kann. Ich wollte nur sicherstellen, dass wir im Ziel nicht im Kreis hinter den Gewinnern zurückbleiben.


Ich werde genau die gleiche Testdatei verwenden wie0xd34df00d. Also habe ich es heruntergeladen und zehnmal mit mir selbst verklebt, wie es hinterlassen wurde.


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

Auf meinem Laptop (8 Kerne / 16 GB RAM) wcdauert die Verarbeitung ca. 10 Sekunden.


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

Mal sehen, wie viel schlechter OTP bei dieser Aufgabe abschneidet .


Ein sehr naiver Versuch


, , , .


@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