Полгода назад Крис Пеннер опубликовал Beating C With 80 Lines Of Haskell: Wc ^[1]. В предисловии говорится:

Задача состоит в том, чтобы построить более шустрый клон оптимизированной вручную реализации утилиты wc на C в нашем любимом высокоуровневом языке программирования со сборкой мусора — на Haskell! Звучит достаточно просто, не так ли?

Крис прошел весь путь от простой реализации при помощи ByteStrings, через моноиды, встроенные моноиды и, наконец, пришел к параллельной многоядерной версии вышеописанного, которой и удалось немного побить чистый C-код во время выполнения на четырех ядрах.

Несколько дней назад на Хабре была размещена еще одна заметка на ту же тему от 0xd34df00d ^[2] Побеждая C двадцатью строками Haskell: пишем свой wc ^[3]. Автор доказал возможность пользования идиоматического хаскеля и в 20 (двадцати) строках кода реализовал алгоритм, который почти в десять раз быстрее, чем идиоматическая реализация на C.

Между тем, я выступаю за использование Haskell (на самом деле, даже Idris ^[4] из-за его зависимых типов) и Coq ^[5], чтобы действительно доказывать критические концепции в нашей кодовой базе; но все, что идет в продакшн, пока еще — на 100% Elixir/Erlang/OTP, из-за их феноменальной отказоустойчивости. Мне захотелось убедиться, что я не упертый баран, которому просто нравится синтаксис эрланга, и поэтому я решил проверить, что мы сможем сделать с идиоматическим эликсиром для той же самой задачи.

Ниже вы увидите некоторые трюки, которые я использовал, чтобы постепенно ускорять выполнение, доведя его до приемлемого уровня. Я уже взрослый человек и больше не верю в Деда Мороза, поэтому я был далек от веры в чудо, будто Elixir действительно может победить языки, которые компилируются в машинный код. Я просто хотел убедиться, что на финише мы не отстанем от победителей на круг.

Я собираюсь использовать ровно тот же тестовый файл ^[6], что и 0xd34df00d ^[2]. Так что я скачал его и склеил с самим собой десять раз, как и было завещано.

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

На моем ноутбуке (8 ядер / 16G оперативки), 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 ^[7], или ленивая File.stream!/3 ^[8]:

@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, столько же для соответствия следующему пробелу, еще столько же для корректного подсчета байтов в хвосте — и дескриптор для списка топонимов Уэльса и Новой Зеландии:

• Taumatawhakatangi­hangakoauauotamatea­turipukakapikimaunga­horonukupokaiwhen­uakitanatahu ^[9], НЗ
• Llanfair­pwllgwyngyll­gogery­chwyrn­drobwll­llan­tysilio­gogo­goch ^[10], Уэльс

Пора вернуться к замерам времени.

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 ^[11].

Давайте использовать больше 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 строк ^[12],

---

Удачного подсчета пробелов!

Автор: Aleksei Matiushkin

Источник ^[13]