Примерно 20 строк, примерно такие же результаты: wc на Elixir
Полгода назад Крис Пеннер опубликовал Beating C With 80 Lines Of Haskell: Wc. В предисловии говорится:
Задача состоит в том, чтобы построить более шустрый клон оптимизированной вручную реализации утилиты wc на C в нашем любимом высокоуровневом языке программирования со сборкой мусора — на Haskell! Звучит достаточно просто, не так ли?
Крис прошел весь путь от простой реализации при помощи ByteStrings, через моноиды, встроенные моноиды и, наконец, пришел к параллельной многоядерной версии вышеописанного, которой и удалось немного побить чистый C-код во время выполнения на четырех ядрах.
Несколько дней назад на Хабре была размещена еще одна заметка на ту же тему от 0xd34df00d Побеждая C двадцатью строками Haskell: пишем свой wc. Автор доказал возможность пользования идиоматического хаскеля и в 20 (двадцати) строках кода реализовал алгоритм, который почти в десять раз быстрее, чем идиоматическая реализация на C.
Между тем, я выступаю за использование Haskell (на самом деле, даже Idris из-за его зависимых типов) и Coq, чтобы действительно доказывать критические концепции в нашей кодовой базе;, но все, что идет в продакшн, пока еще — на 100% Elixir/Erlang/OTP, из-за их феноменальной отказоустойчивости. Мне захотелось убедиться, что я не упертый баран, которому просто нравится синтаксис эрланга, и поэтому я решил проверить, что мы сможем сделать с идиоматическим эликсиром для той же самой задачи.
Ниже вы увидите некоторые трюки, которые я использовал, чтобы постепенно ускорять выполнение, доведя его до приемлемого уровня. Я уже взрослый человек и больше не верю в Деда Мороза, поэтому я был далек от веры в чудо, будто Elixir действительно может победить языки, которые компилируются в машинный код. Я просто хотел убедиться, что на финише мы не отстанем от победителей на круг.
Я собираюсь использовать ровно тот же тестовый файл, что и 0xd34df00d. Так что я скачал его и склеил с самим собой десять раз, как и было завещано.
% 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(
<>,
%{bc: bc, wc: wc, lc: lc, ns?: ns}
),
do: parse(rest, %{bc: bc + 1, wc: wc + ns, lc: lc + 1, ns?: 0})
def parse(
<>,
%{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 строк,
Удачного подсчета пробелов!
