Побеждая C двадцатью строками Haskell: пишем свой wc20.02.2020 19:38

?v=1

Привет, Хабр.

На днях Siemargl предложил мне перевести любопытную статью о победе над юниксовым wc при помощи хаскеля. Переводить её я, конечно же, не буду, и по нескольким причинам:


  • автор выжал из однопоточной версии далеко не всё, и однопоточная версия была существенно медленнее wc,
  • в той статье для победы потребовалось воспользоваться многопоточностью (что само по себе немного читерство и победа скорее над здравым смыслом, а не над wc),
  • для этого автору пришлось углубляться в трихомонады и моноиды — не, это отличная иллюстрация прелестей моноидального мышления, но ИМХО немного перебор для такой задачи, тем более, что из-за этого
  • код получился излишне объёмным,
  • да и вообще, соревноваться с wc, которая имеет кучу опций и фич, реализуя её ну очень игрушечный аналог, вообще как-то странно и даже немного глуповато.

Тем не менее, заниматься странными делами — дело хорошее, поэтому сегодня мы попробуем исправить первый из пунктов выше и улучшим результат Криса (так звать автора исходной статьи).

Опять же, как мы выяснили в прошлый раз, код на C я писать не умею, так что писать его и не буду, а в качестве конкурента хаскель-реализации у меня (как и у Криса) выступает сишный wc из GNU Coreutils. Те чуваки уж точно на C писать умеют, коду этому не один десяток лет, да и о производительности они позаботились, судя по таким кусочкам: 

/* If the average line length in the block is >= 15, then use
   memchr for the next block, where system specific optimizations
   may outweigh function call overhead.
   FIXME: This line length was determined in 2015, on both
   x86_64 and ppc64, but it's worth re-evaluating in future with
   newer compilers, CPUs, or memchr() implementations etc.  */

Спойлер: мы обгоним сишный wc примерно на порядок без всяких проблем, получив вполне идиоматичный код и потратив менее получаса на изменения и оптимизацию оригинального кода.


Условия эксперимента

Итак, сначала обсудим экспериментальную установку.


Данные

Я скачал этот файл и склеил его с собой же, так что суммарный размер составляет примерно 1.8 гигабайта: 

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

Кстати, test.txt размещается на tmpfs-разделе, и оперативной памяти более чем достаточно, так что здесь нет никакого дискового IO.


Железо и софт

Всё это счастье запускается под Gentoo Linux на Core i7 4770 с 32 гигабайтами оперативной памяти.

Для хаскель-кода используется ghc 8.8.2.

wc взят из coreutils 8.31, собранных gcc 9.2 с -O2 -march=native: 

% wc --version
wc (GNU coreutils) 8.31
Packaged by Gentoo (8.31-r1 (p0))

Кстати, этот вот -march=native — лёгкая поблажка в пользу C, так как хаскель-код собирается без каких-либо аналогичных опций, что имеет свои преимущества: полученный бинарник сможет работать на любой x86_64-машине, тогда как wc из coreutils может работать только на моём процессоре и более новых (если компилятор решил воспользоваться соответствующими SIMD-инструкциями, конечно же).

Кроме того, я пробовал собирать руками с -O3 вместо -O2 — результаты различаются несущественно, так что оставим дефолтовый -O2.


Измерения

Измерения производятся просто, используя time. time показывает время и в юзерспейсе, и в ядре, но мы будем сравнивать только первое, так как


  1. время в ядре с хорошей точностью и стабильностью равно примерно 0.3 секунды,
  2. я не бенчмаркаю ядро, и меня интересует лишь то, сколько времени выполняется мой код.

Как и с любым другим полностью детерминированным бенчмарком, каждый исполняемый файл запускается несколько (в данном случае пять) раз, и записывается минимальное время из всех запусков.


Стартовая точка

От чего мы оттакливаемся? Запустим wc!

Так как мы далее будем игнорировать большую часть Unicode (и не рассматривать отдельно особые уникодовые символы), для честности и отсутствия претензий выставим C-локаль, запуская wc как LANG=C LC_ALL=C wc /path/to/test.txt. Время работы? 10.4 секунды. Это мы и возьмём за базовый результат.

Интересно, что с моей дефолтовой локалью (ru_RU.UTF-8) wc работает быстрее (7.20 секунд), но почти каждый, кому я показывал статью перед публикацией, сказал, что правильнее сравнивать с C-локалью — значит, так тому и быть.

Кроме того, если мы запустим только подсчёт строк (что всё равно заставит прогнать весь файл через шину памяти), то время работы окажется равным примерно 0.2 секунды — то есть, это далеко не IO-bound-задача.


Haskell

Итак, с чем нам придётся работать?

Я возьму эту версию из поста Криса, попутно переименовав функцию и заменив имя cs на bs (раз уж мы считаем байты, а не символы): 

import qualified Data.ByteString.Lazy.Char8 as BS
import Data.Char

wc :: BS.ByteString -> (Int, Int, Int)
wc s =
    let (bs, ws, ls, _) = BS.foldl' go (0, 0, 0, False) s
     in (bs, ws, ls)
  where
    go :: (Int, Int, Int, Bool) -> Char -> (Int, Int, Int, Bool)
    go (!bs, !ws, !ls, !wasSpace) c =
        let addLine | c == '\n' = 1
                    | otherwise = 0
            addWord | wasSpace = 0
                    | isSpace c = 1
                    | otherwise = 0
         in (bs + 1, ws + addWord, ls + addLine, isSpace c)

Да, у него есть более эффективные однопоточные версии, но вот этот конкретный код наиболее дружественен к последующим изменениям (да и он всё ещё достаточно краток и идиоматичен).

Как бы то ни было, Крис пишет, что эта версия работает в 9 раз медленнее wc. У меня эти результаты воспроизвести не удалось: на моей машине эта версия отрабатывает за 31.2 секунду, или 306% от wc. Не 9 раз, конечно, но всё равно не фонтан.

Кроме того, эта версия имеет маленький баг (она не учитывает последнее слово, если файл не заканчивается переводом строки или иным пробельным символом), но я это починю потом, тем более, что фикс тривиален, и мы исправим эту проблему в финальной версии.

Так как улучшить эту версию?


Записи спешат на помощь

Во-первых, я не люблю большие туплы, особенно большие туплы из элементов одинакового типа — мне с моим микроскопическим фокусом внимания слишком легко там сделать ошибку и перепутать элементы. Так что давайте начнём с замены тупла на полноценный тип данных: 

{-# LANGUAGE Strict #-}
{-# LANGUAGE RecordWildCards #-}

import qualified Data.ByteString.Lazy.Char8 as BS
import Data.Char

data State = State
  { bs :: Int
  , ws :: Int
  , ls :: Int
  , wasSpace :: Bool
  }

wc :: BS.ByteString -> (Int, Int, Int)
wc s = (bs, ws, ls)
  where
    State { .. } = BS.foldl' go (State 0 0 0 False) s

    go State { .. } c = State (bs + 1) (ws + addWord) (ls + addLine) (isSpace c)
      where
        addLine | c == '\n' = 1
                | otherwise = 0
        addWord | wasSpace = 0
                | isSpace c = 1
                | otherwise = 0

Мы больше не используем bang-паттерны, так как поля структуры по факту строгие из-за прагмы {-# LANGUAGE Strict #-}. Такая замена не должна особо поменять на производительность, не так ли?

На самом деле нет, она влияет, и ещё как — код ускорился примерно в 4 раза! Эта версия работает 7.56 секунд, или 75% от wc, так что мы уже более чем на уровне! Как так получилось?

На самом деле тут всё понятно, и Крис даже сам делает намёк на причины подобного поведения в исходном посте: как только мы определили запись со строгими полями, компилятору стало легче определить, что он мог бы распаковать значения этих полей. Так что по факту компилятор за нас сделал что-то вроде

data State = State
  { bs :: {-# UNPACK #-} !Int
  , ws :: {-# UNPACK #-} !Int
  , ls :: {-# UNPACK #-} !Int
  , wasSpace :: !Bool
  }

что избавляет нас от ещё одной аллокации и перехода по указателю для каждого Int-поля и даёт искомый выигрыш. И это несмотря на то, что аллокации в nursery area, то есть, в нулевом поколении почти всегда настолько же дешёвые, как аллокации на стеке — видимо, в данном случае роль лишнего перехода по указателю оказывается достаточно высокой.


CSE

Заметим, что мы вычисляем isSpace c как минимум один раз для каждого символа, а чаще всего — два раза. Давайте удостоверимся, что мы здесь не делаем лишней работы, переписав внутреннюю функцию go как: 

    go State { .. } c = State (bs + 1) (ws + addWord) (ls + addLine) isSp
      where
        isSp = isSpace c
        addLine | c == '\n' = 1
                | otherwise = 0
        addWord | wasSpace = 0
                | isSp = 1
                | otherwise = 0

Результат? Время работы уменьшилось более чем вдвое — до 2.93 секунд, или 28% от wc.

Почему потребовалась эта оптимизация? Почему ghc не может сделать её за нас, учитывая, что эта оптимизация никогда не увеличивает объём выполняемой работы? Моё впечатление — isSpace инлайнится (со всеми вытекающими последующими оптимизациями) перед тем, как компилятор имеет шанс сделать common subexpression elimination.


Опции компилятора и прагмы

Другое направление улучшения производительности — опции компилятора (можно ограничиться уровнем оптимизации и используемым кодогенератором). Кроме того, мы можем заставить компилятор заинлайнить wc и посмотреть, что получится. Тут нет какого-то хорошего системного подхода, поэтому мы просто перепробуем всевозможные комбинации из следующих вещей:


  1. LLVM-кодогенератор (через -fllvm) — он скорее помогает на хардкорных числодробилках, но может оказаться полезным и здесь.
  2. Уровень оптимизации (через -O2) — в большинстве случаев более простой -O достаточно хорош, и чаще всего разницы в производительности между ним и -O2 особо нет, но почему бы не попробовать?
  3. Явное требование инлайнинга функции (через прагму {-# INLINE wc #-}). Не думаю, что это как-то особо поможет в данном случае, так как функция вызывается лишь единожды, и потому оверхед от её вызова несущественен, да и трудно придумать какие-то дополнительные возможности для оптимизации после её инлайнинга. Но, опять же, попробуем и посмотрим, что получится.

Код функции я не показываю, так как во всех этих случаях он, как и следовало ожидать, не меняется.

Результаты в табличной форме:

Можно сделать следующие выводы. Во-первых, инлайнинг таки помогает. Кроме того, -O2 в данной задаче идёт на пользу, и очень сильно, а вот LLVM-бекенд либо никак не влияет, либо вообще делает хуже (когда используется сам по себе).

В любом случае, здесь вполне можно остановиться и разворачивать эту версию на прод. Это всё ещё вполне идиоматичный хаскель, и C уже вполне себе выглядит побеждённым (19%!). Если бы моей целью было показать элегантность функционального программирования вместе с его эффективностью, я бы показывал эту версию.

Но давайте продолжим.


Больше распаковки

Улучшение, что мы получили от замены тупла на запись State, намекает на ещё одну возможность оптимизации.

Заметим, что тип Bool одного из полей в нашей записи не подлежит распаковке, так как он состоит из двух конструкторов. Что, если мы его заменим Intом, где 1 будет обозначать True, а 0 — False? Конечно, немножко уродливо, но зато всё прямо как в С! 

data State = State
  { bs :: Int
  , ws :: Int
  , ls :: Int
  , wasSpace :: Int
  }

wc :: BS.ByteString -> (Int, Int, Int)
wc s = (bs, ws, ls)
  where
    State { .. } = BS.foldl' go (State 0 0 0 0) s

    go State { .. } c = State (bs + 1) (ws + addWord) (ls + addLine) isSp
      where
        isSp | isSpace c = 1
             | otherwise = 0
        addLine | c == '\n' = 1
                | otherwise = 0
        addWord | wasSpace == 1 = 0
                | isSp == 1 = 1
                | otherwise = 0

Само по себе время работы это не меняет (видимо, компилятор хорошо постарался над предыдущей версией с Bool), но это открывает дополнительные возможности для оптимизации. В частности, заметим, что выражение для addWord может быть преобразовано из guard’ов (которые по факту вложенные if) в единое арифметическое выражение: 

        addWord = (1 - wasSpace) * isSp

Доказательство эквивалентности предлагается читателю в качестве упражнения.

Каково влияние этой оптимизации? Ну, время работы уменьшилось весьма заметно, до 1.91 секунды, или 18% от времени работы wc. Прелести кода без условных переходов, ага.


Меньше юникода

Что, если мы хотим ещё чуточку быстрее?

Разумным компромиссом выглядит игнорирование пробельных символов за границами ASCII, что позволит отказаться от функции isSpace. Тем более, что в подавляющем большинстве практических приложений мне эти юникодовые пробельные символы и так не нужны. Кроме того, очень важно отметить, что это не помешает нам корректно считать количество юникодовых символов, как мы увидим во второй части статьи.

Кроме того, будем импортировать Data.ByteString.Lazy вместо Data.ByteString.Lazy.Char8, чтобы избежать переупаковки байтов в неизоморфные им Char.

Итого получаем: 

{-# LANGUAGE Strict #-}
{-# LANGUAGE RecordWildCards #-}

module Data.WordCount where

import qualified Data.ByteString.Lazy as BS

data State = State
  { bs :: Int
  , ws :: Int
  , ls :: Int
  , wasSpace :: Int
  }

wc :: BS.ByteString -> (Int, Int, Int)
wc s = (bs, ws, ls)
  where
    State { .. } = BS.foldl' go (State 0 0 0 0) s

    go State { .. } c = State (bs + 1) (ws + addWord) (ls + addLine) isSp
      where
        isSp | c == 32 || c - 9 <= 4 = 1
             | otherwise = 0
        addLine | c == 10 = 1
                | otherwise = 0
        addWord = (1 - wasSpace) * isSp
{-# INLINE wc #-}

Это изменение приводит к достаточно весомому ускорению, уменьшая время работы до 1.45 с, или 14% от времени работы wc.

Думаю, что это — лучшее, что можно получить малой кровью, так что давайте здесь и остановимся.


Исправление ошибки

Упомянутый ранее баг вызван тем, что мы не учитываем последнее слово, если за ним не следует пробельный символ. К счастью, исправить это легко: нужно просто учесть значение поля wasSpace и установить его начальное значение в единицу, например, таким образом: 

wc s = (bs, ws + 1 - wasSpace, ls)
  where
    State { .. } = BS.foldl' go (State 0 0 0 1) s
    ...

Очевидно, что это никак не влияет на производительность.


Бонус: уменьшение времени ядра

Помните те 0.35 секунды в ядре, которые мы договорились не учитывать? А можно ли всё-таки их как-то тоже уменьшить?

Начнём с того, что я ещё не показывал, как именно используется функция wc. Пора исправиться: 

main :: IO ()
main = do
  [path] <- getArgs
  contents <- BS.readFile path
  print $ wc contents

readFile тратит довольно много циклов на ненужное копирование данных из ядра в пространство пользователя. Можно избавиться от этого оверхеда при помощи mmap. Возьмём пакет bytestring-mmap, предоставляющий ByteString'и поверх mmap-ированных файлов с нулевым копированием, и заменим main на

main :: IO ()
main = do
  [path] <- getArgs
  contents <- unsafeMMapFile path
  print $ wc contents

Кроме того, так как unsafeMMapFile возвращает строгую ByteString, поменяем наш модуль с описанием функции wc, чтобы он импортировал строгие строки вместо ленивых. Конечно, вместо этого мы могли бы использовать вариант unsafeMMapFile, возвращающий ленивые строки, но для mmap-файлов это бессмысленно, лень и так обеспечивается ядром.

Результат — существенное уменьшение времени ядра, которое теперь составляет 0.04–0.06 секунды вместо 0.35 секунды ранее. Впрочем, это не повлияло сколь угодно значимым образом на время самой нашей программы в юзерспейсе.

Одно из стандартных возражений против строк поверх mmap в хаскеле в том, что они ломают ссылочную прозрачность: если файл на диске поменяется, то поменяется и содержимое строки, а это неприятно. Однако, в данном конкретном случае это неважно: мы наблюдаем строку всего один раз, поэтому у нас нет шанса отличить изменяемую во время выполнения строку от неизменяемой.


Итого

Что в итоге у нас получилось?

Мы потратили менее получаса, чтобы улучшить предыдущие результаты и почти на порядок обойти время работы сишной версии, которую наверняка видели сотни глаз серьёзных Unix-хакеров, и которая была довольно серьёзно оптимизирована. Мы сделали это при помощи пары десятков строк вполне себе идиоматичного хаскеля, с чистыми функциями, без монады ST и тому подобных вещей.

Однако, стоит ещё раз повторить, что это изначально довольно глупая затея: наша версия умеет делать куда меньше, чем умеет полноценный wc, и эти результаты не означают, что «готовая к продакшену» версия wc на хаскеле будет работать так же быстро, как то, что мы получили здесь. Эти результаты лишь доказывают, что это принципиально возможно.

Ну и, чтоб уж не томить, обсудим планы на будущее: в следующей статье мы займёмся чем-то существенно более интересным, где хаскель действительно будет сиять. Конкретнее, мы модуляризуем то, что у нас получилось сегодня, посмотрим, как сделать наш игрушечный haskell wc чуть менее игрушечным, а также оценим, как это повлияет на производительность.

© Habrahabr.ru