Get best of the week

大约20行，结果大致相同：Elixir上的wc

六个月前，克里斯·彭纳（Chris Penner）发表了《用80行Haskell：Wc打败C》。序言说：


面临的挑战是在Haskell上用我们最喜欢的高级语言通过垃圾回收程序构建一个智能克隆，优化手动实现工具wc以实现C语言。听起来很简单，对吧？

Chris从使用ByteStrings的简单实现，一直到monoid，内置的monoid，一直到上述的并行多核版本，该版本在运行时在四个内核上击败了一些纯C代码。


几天前，在哈布雷（Habré）上，来自 0xd34df00d C Haskell: wc。作者证明了使用惯用的Haskell和二十（20）行代码来实现该算法的可能性，这比C语言中惯用的实现快了十倍。


同时，我主张使用Haskell（实际上，甚至是Idris，因为它依赖于类型）和Coq来在我们的代码库中真正证明关键概念。但由于其出色的容错性，因此投入生产的所有产品仍然都是100％Elixir / Erlang / OTP。我想确保我不是只喜欢erlang语法的固执的ram，所以我决定检查一下对于惯用的lix剂我们可以做些什么。


在下面，您将看到一些我用来逐渐加快执行速度并将其提高到可接受水平的技巧。我已经成年了，不再相信圣诞老人了，我不怀任何奇迹希望Elixir能够真正击败编译成机器代码的语言。我只是想确保在结束时我们不会在一圈内落后于获胜者。


我将使用完全相同的测试文件如0xd34df00d。所以我下载了它，然后将其与自己粘在一起十次，就像被遗赠的那样。


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

在我的笔记本电脑（8核/ 16G RAM）上，wc大约需要10秒钟来处理它。


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

好吧，让我们看看OTP在此任务中的执行情况会更糟。


一个非常幼稚的尝试


, , , .


@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