Get best of the week

Sekitar 20 baris, tentang hasil yang sama: wc di Elixir

Enam bulan lalu, Chris Penner menerbitkan Beating C With 80 Lines Of Haskell: Wc . Kata pengantar mengatakan:


Tantangannya adalah membangun klon cerdas yang dioptimalkan secara manual untuk mengimplementasikan alat wcke C dalam bahasa tingkat tinggi favorit kami dengan program pengumpulan sampah - di Haskell ! Kedengarannya cukup sederhana, bukan?

Chris pergi jauh-jauh dari implementasi sederhana menggunakan ByteStrings , melalui monoids, built-in monoids, dan akhirnya sampai pada versi multi-core paralel di atas, yang berhasil mengalahkan kode C kecil murni pada waktu run time pada empat core.


Beberapa hari yang lalu di Habré diposting catatan lain tentang topik yang sama dari 0xd34df00d C Haskell: wc. Penulis terbukti kemungkinan untuk menggunakan idiom Haskell dan dua puluh (20) baris kode untuk menerapkan algoritma, yang hampir sepuluh kali lebih cepat dari implementasi idiomatic di C .


Sementara itu, saya menganjurkan menggunakan Haskell (pada kenyataannya, bahkan Idris karena jenis ketergantungannya) dan Coq untuk benar-benar membuktikan konsep kritis dalam basis kode kami; tetapi segala sesuatu yang masuk ke produksi masih 100% Elixir / Erlang / OTP , karena toleransi kesalahan mereka yang fenomenal. Saya ingin memastikan bahwa saya bukan domba jantan yang keras kepala yang hanya menyukai sintaks erlang, jadi saya memutuskan untuk memeriksa apa yang bisa kami lakukan dengan elixir idiomatik untuk tugas yang sama.


Di bawah ini Anda akan melihat beberapa trik yang saya gunakan untuk secara bertahap mempercepat eksekusi, membawanya ke tingkat yang dapat diterima. Saya sudah dewasa dan tidak lagi percaya pada Santa Claus, dan saya tidak menghargai harapan keajaiban bahwa Elixir benar-benar dapat mengalahkan bahasa yang dikompilasi ke dalam kode mesin. Saya hanya ingin memastikan bahwa pada akhirnya kami tidak akan ketinggalan di belakang para pemenang dalam lingkaran.


Saya akan menggunakan persis sama file tes sebagai0xd34df00d. Jadi saya mengunduhnya dan menempelkannya pada diri saya sendiri sepuluh kali, sebagaimana diwariskan.


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

Di laptop saya (8 core / 16G RAM), wcdibutuhkan sekitar 10 detik untuk memprosesnya.


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

Baiklah, mari kita lihat seberapa buruk kinerja OTP dalam tugas ini .


Upaya yang sangat naif


, , , .


@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