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

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


    На днях 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 #-}). Не думаю, что это как-то особо поможет в данном случае, так как функция вызывается лишь единожды, и потому оверхед от её вызова несущественен, да и трудно придумать какие-то дополнительные возможности для оптимизации после её инлайнинга. Но, опять же, попробуем и посмотрим, что получится.

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


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


    LLVM -O2 Инлайнинг Время, с % времени wc
    2.93 28
    3.96 38
    2.61 26
    2.59 25
    2.23 21
    2.02 19
    2.01 19
    2.01 19

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


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


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


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


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


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


    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 чуть менее игрушечным, а также оценим, как это повлияет на производительность.

    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 116

      +1

      А ByteString в хаскеле разве поддерживатет mbcs? Кажется это основное что тормозит в wc: https://github.com/coreutils/coreutils/blob/master/src/wc.c#L398 .

        0

        Нет, поэтому я сразу написал, что мы ограничимся ASCII и для честности будем запускать wc с сишной локалью.

          0

          Так там же нет отдельного кода без mbrtowc/is_basic? Т.е. такакя оптимизация в wc отсутствует.

            0

            Не уверен: там даже комментарий есть типа


              /* If in the current locale, chars are equivalent to bytes, we prefer
                 counting bytes, because that's easier.  */

            Но да, там подсчёт выполняется одной большой функцией на 400 строк с кучей локального состояния и не самой мелкой цикломатической сложностью, может, я читаю её неправильно. Если такой оптимизации там и нет, то я не удивлён, почему.

              0

              Отдельного оптимизированного цикла под кейс не вижу, есть только проверка на is_basic без mbrtowc и установка n = 1; wide_char = *p; wide = false;, прогоняя это дальше через универсальный код. При этом is_basic вижу может быть в 2х вариантах:


              MBCHAR_INLINE bool
              is_basic (char c)
              {
                return (is_basic_table [(unsigned char) c >> 5] >> ((unsigned char) c & 31))
                       & 1;
              }
              
              #else
              
              MBCHAR_INLINE bool
              is_basic (char c)
              {
                switch (c)
                  {
                  case '\t': case '\v': case '\f':
                  case ' ': case '!': case '"': case '#': case '%':
                  case '&': case '\'': case '(': case ')': case '*':
                  case '+': case ',': case '-': case '.': case '/':
                  case '0': case '1': case '2': case '3': case '4':
                  case '5': case '6': case '7': case '8': case '9':
                  case ':': case ';': case '<': case '=': case '>':
                  case '?':
                  case 'A': case 'B': case 'C': case 'D': case 'E':
                  case 'F': case 'G': case 'H': case 'I': case 'J':
                  case 'K': case 'L': case 'M': case 'N': case 'O':
                  case 'P': case 'Q': case 'R': case 'S': case 'T':
                  case 'U': case 'V': case 'W': case 'X': case 'Y':
                  case 'Z':
                  case '[': case '\\': case ']': case '^': case '_':
                  case 'a': case 'b': case 'c': case 'd': case 'e':
                  case 'f': case 'g': case 'h': case 'i': case 'j':
                  case 'k': case 'l': case 'm': case 'n': case 'o':
                  case 'p': case 'q': case 'r': case 's': case 't':
                  case 'u': case 'v': case 'w': case 'x': case 'y':
                  case 'z': case '{': case '|': case '}': case '~':
                    return 1;
                  default:
                    return 0;
                  }
              }

              Отдельный не-mbcs вариант явно будет быстрее.

                0

                Есть это, и судя по структуре кода, оно здесь должно использоваться (MB_CUR_MAX ведь 1 для сишной локали?).


                И возможно ли малой кровью переписать код так, чтобы оно не считало то, что пользователь не просил — непонятно. На хаскеле-то это не так сложно.

                  0

                  MB_LEN_MAX/MB_CUR_MAX это же константа, MB_LEN_MAX=1 — это mbcs отключен при компиляции, от локали никак не зависит. Вот перекомпилить gnulib и wc с MB_LEN_MAX=1 можно попробовать, да.

                    0

                    Так не MB_LEN_MAX, а MB_CUR_MAX. man MB_CUR_MAX говорит


                    The MB_CUR_MAX macro defines an integer expression giving the maximum number of bytes needed to represent a single wide character in the current locale. This value is locale dependent and therefore not a compile-time constant.
                      0

                      Проблема в том, что fallback код все равно использует mbcs версии isprint и isspace. Ну тоесть fallback конечно явно быстрее, но чтобы включить оптимизацию до конца — надо оба пересобрать, wc и gnulib.


                      А MB_CUR_MAX или MB_LEN_MAX от локали автоматом все равно не изменятся, их надо или рередефайнить для wc, или от пересобранного gnulib они сами единичные подтянутся.

                        0

                        А разве isprint и компания работает с полным mbcs-оверхедом, если выставлена сишная локаль?

                          0

                          Да, кажется я ошибся, isprint/isspace уже в glibc, а не gnulib, если их конечно не переопределили на mb_isprint/mb_isspace. Тогда достаточно только чтобы fallback включился.

                            0

                            Ну точнее ну как достаточно, glibc наверно получит локаль, пойдет в табличку и проверит там флаг. Магически isspace до == ' ' не оптимизируется. Оптимизируется только если на этапе сборки там поддерживается отключение локалей и оптимизация этих функций до ascii.

                              0

                              Не думаю, что соответствующий бранчинг или indirection ответственен хотя бы за половину разницы в производительности.


                              В любом случае, это вопрос quality of implementation. Почему выбирать между memchr или написанием соответствующего кода руками у людей ресурсы есть, а написать свой isspace — нет — хороший вопрос.

                                0

                                Да качество вроде нормальное, просто если локаль поддерживать, то никуда не деться от того чтобы ее из tls взять и заглянуть.


                                То что это вряд ли большая доля это да, я думаю переход на fallback дает куда больше. Но все равно надо проверять, и лишнее из switch тоже удалить, что в хаскель варианте отсутствует. Все же такой inner loop вещь тонкая на любом языке.

                                  +1
                                  Но все равно надо проверять, и лишнее из switch тоже удалить, что в хаскель варианте отсутствует. Все же такой inner loop вещь тонкая на любом языке.

                                  Именно!


                                  И тут ещё один ключевой вопрос, снова его озвучу — как бы сделать так, чтобы и inner loop лишнего не делал, и поддерживалось всё то же, что и в текущей реализации wc.


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

                                    0

                                    Ну я с этим и не спорю, хаскель выглядит куда компактнее.
                                    Про кодогенерацию только не понял, что на си, что на хаскеле же тоже 2 варианта иннер лупа надо будет сделать? Там чистая подстановка mbcs\ascii вариантов функций в один и тот же код плохо ложится т.к. mbrtowc может переводить состояния, потому там fallback отдельно и сделан. В общем суть про n вариантов и причем тут си не уловил.

                                      0

                                      Ну в общем случае, если у вас есть N разных статистик (включая разные варианты подсчёта слов, например, с/без учётом юникода), то в идеале вы бы хотели написать 2^N — 1 версий основного цикла, который бы считал только то, что вы у него попросили посчитать (на самом деле всё ещё интереснее, но это уже детали следующего порядка точности). Дело не только в однобайтовой или мультибайтовой кодировке, но и в том, скажем, чтобы не считать максимальную ширину строки, если не просили, не считать число слов, если не просили, и так далее.


                                      Руками же ведь вы это писать не будете?

                                        0

                                        Ну вообще в кодеках такое сплошь и рядом на си, там где motion compensation и надо его 100500 вариантов. Если вы про то что сишный препроцессор неудобнее для всяких групповых подстановок — то да, все верно. С++, Хаскель и многие другие языки тут могут поудобнее и покомпактнее быть (иногда ценой что подстановка не всегда compile time), но принципиальных сложностей там с этим нет.

                                          0

                                          В плюсах темплейты гарантируют то, что это сделается на этапе компиляции просто по построению языка.


                                          Хаскель, да, не гарантирует, но если вас не смущает завязка на ghc (который всё равно де-факто единственный компилятор хаскеля), то там это тоже делается.

                                      0

                                      Ответ на этот вопрос для Си дали в С++ :)

                                        0

                                        Темплейтами оно, наверное, всё же будет стрёмнее выглядеть, чем это.

                                          0

                                          А кто обещал что будет легко, я же написал что это как бы для Си решение.

                                          0
                                          Что вы имеете ввиду? Если шаблоны — то это все же немножко не то…
                                            0

                                            Почему? — с поставленной задачей справляется

                                              0

                                              Надо будет в следующей статье в заключении предложить сделать это на шаблонах в качестве развлечения для читателя.


                                              И, кстати, у меня есть впечатление, что качественный JIT тут тоже хорошо справится. Но я не знаю ни одного языка с JIT'ом, увы.

                                        0
                                        Создание оконечного блока/лямбды(доступно для сей в ллвм) в зависимости он набора ключей тоже попадает под кодогенерацию?
                                          0

                                          Это скорее ближе к JIT, наверное.


                                          А как это будет выглядеть?

                                            0
                                            Технически синтаксис тут en.wikipedia.org/wiki/Blocks_(C_language_extension)

                                            А я щас подумал что можно через va_list нафигачить функцию, которая сожрет произвольное число блоков и будет их запускать — причем можно наивно через for, а можно просто склеить их код — и видимо компилятор нафигачит сам все возможные комбинации.
                                              0

                                              Я вот не думаю, что компилятор сам нафигачит. Но на результат было бы интересно посмотреть.

          • НЛО прилетело и опубликовало эту надпись здесь
              0

              Хорошая идея! Мне в голову не приходило.


              Но, увы, время работы статистически значимо не меняется.

              • НЛО прилетело и опубликовало эту надпись здесь
                  0

                  Сделать в хаскеле во время компиляции таблицу, чтобы при обращении к ней в рантайме не было лишнего indirection'а — увы, не так просто, как в С. Я этим более подробно займусь где-то ближе к третьей части этой серии (код для которой ещё не написан, в отличие от второй), когда попробую адекватно обрабатывать уникодовые пробелы, для чего мне понадобится построенный в компилтайме trie.

              +3

              Простой вопрос: у вас в хаскеле GC есть? Если есть, то как решается проблема остановки мира?


              Есть такая игра: https://benchmarksgame-team.pages.debian.net/


              n-body problem
              GHC: 21.87s
              Rust: 6.07s
              C: 7.30s


              mandelbrot
              GHC: 4.87s
              Rust: 1.7s
              C: 1.64s


              Разумеется, вы можете предложить свою версию, которая позволит сделать GHC хоть сколько-то быстрым.

                +2
                Простой вопрос: у вас в хаскеле GC есть?

                Есть. В этой задаче у него нулевой оверхед, кстати.


                Если есть, то как решается проблема остановки мира?

                Хороший вопрос. Есть, например, такое для низкой latency сборки мусора.


                Ну и, разумеется, StW GC не означают автоматически большие цифры в бенчмарках — они плохи для latency, а не для общего времени работы. Для числодробилки StW куда более вероятно будет более эффективным.


                А по вашей ссылке у меня что-то 404, а то я бы посмотрел, конечно.

                  0
                    +2

                    Открыл топовую реализацию mandelbrot на хаскеле — не, так писать нельзя, одни примопсы и ручная работа в IO. Идиоматичный пример неидиоматичного хаскеля прям.


                    Интересно, что получится из более чистой реализации. Погляжу, спасибо за подкинутую задачу!

                      0

                      Если что, это бенчмарк гейм. Тут скорость важнее идеоматичности. Вы можете попробовать написать быстрее.


                      (При том, что список задач там довольно ограниченный, это довольно важный сайт для определения, чья Тьюринг-машина длиннее).

                        +1

                        Я вот прям на прошедших выходных зачем-то сделал возможность писать инлайн-ассемблер в коде на хаскеле. Насколько читерством будет пользоваться этой библиотекой?

                          +1
                          Насколько читерством будет пользоваться этой библиотекой?

                          Там увы все решает левая пятка создателя этой игры.

                            +2

                            Да без проблем. Только как вы будете адаптироваться под процессор… Под какую из архитектур arm'а будет ваш ассемблер?

                  0

                  Каждый раз, читая ваши статьи, нахожу что-то новое.
                  Интересно, раз у нас уже есть bytestring в памяти за бесплатно, может можно подключить стратегии и работать параллельно намвсех ядрах.
                  Надо только придумать как склеить результаты.

                    0

                    Спасибо за фидбек!


                    Результаты как раз в оригинальной статье моноидами склеивали — эта часть мне вполне понравилась, ИМХО интересное чтение. Одно плохо — текущая версия уже прожёвывает больше гигабайта в секунду на ядро, а топовые NVMe SSD дают ЕМНИП около 3 гигабайт/с. Лично я бы скорее начал с параллельной обработки разных файлов (но тут минус в том, что часто надо посчитать статистику всего лишь по одному файлу).

                      0
                      После первого прогона у вас весь файл дисковом кэше в оперативной памяти, поэтому скоростью диска вы не ограничены. Можете ориентироваться на скорость оперативной памяти
                    +1
                    в той статье для победы потребовалось воспользоваться многопоточностью (что само по себе немного читерство и победа скорее над здравым смыслом, а не над wc)

                    кстати стоит напомнить, что Линус Торвальдс регулярно агитирует пользоваться форками и пайпами вместо тредов с мьютексами. И многие линуксовые утилиты однопоточны вовсе не потому что их авторы что-то не осилили, а именно из-за ориентации на такой сценарий использования.

                      +2

                      Можно пожалуйста ссылочку на оригинал?

                      +3

                      C — это язык, максимально приближенный к железу. Ближе только ассемблер. Язык C я изучал после ассемблера, довольно своеобразным способом. Писал код на C, а потом смотрел результат работы компилятора на ассемблере — получилось ли то, что я хотел. Поэтому заголовок статьи звучит для меня примерно так: "Побеждая процессор i7 двадцатью строками Haskell: пишем свой wc" :)
                      А вообще, плюсую однозначно, такие бенчмарки полезны в изучении того же Haskell.

                        +3

                        Выкинули 90% функционала wc (оставив 10%) и получили ускорение в 10 раз. Тут всё сходится. Чтобы делать реальные бенчмарки надо начинать с четкого тз и тестовых данных к нему. А не с "посчитайте пробелы".

                          +2

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


                          Ну и да, почему ж выкинули и оставили 10%?


                          Да, нет поддержки аргументов командной строки ­— но их парсинг не повлияет на производительность, не так ли?
                          Да, нет подсчёта количества символов или максимальной длины строки, но я и wc не просил их считать. Если wc считает что-то ещё, что её не просили, и делает это неоптимально, то это проблема в реализации wc, не так ли?


                          Тут ещё можно обсудить, насколько легко, например, менять wc, но такие вещи адекватно сравнивать уже сложнее. 400 строк основной функции wc действительно делают сильно больше, чем 20 строк предложенного кода. Вот если вы скажете, что сравнивать объём текущей хаскель-реализации с сишной реализацией нечестно, то я буду более чем согласен.

                            0
                            Да, нет подсчёта количества символов или максимальной длины строки, но я и wc не просил их считать.

                            А как вы запускали? Мне тоже лень читать тот си код, есть ли там отдельная реализация для вашего сценария — строки + слова?


                            Во вторых поддержка разных локалей.


                            Ну и смогло ли оно сделать инлайны в сишной версии я не знаю.


                            UPD: А ещё и mmap сравнили с read под конец.

                              0
                              А как вы запускали?

                              Как в статье написано: LC_ALL=C LANG=C wc file.txt. Оно тогда считает байты, слова и строки.


                              Мне тоже лень читать тот си код, есть ли там отдельная реализация для вашего сценария — строки + слова?

                              Мне тот код тяжело читать. Он пытается считать не всё, что попросили, но я не знаю, насколько успешно. Всё ж 400 строк из кучи if/else/switch/goto, отслеживать поток исполнения чуть сложнее, чем могло бы быть.


                              Во вторых поддержка разных локалей.

                              От которой я явно отказался, попросив сишную локаль.

                                0

                                Ну да только на код на си это не повлияло. Вы же сами видели что утф8 работает быстрее LANG=C что явно говорит что той оптимизации там нет. Насколько я могу судить по исходнику там эта оптимизации только на этапе компиляции включается. Кстати судя по ману хаскеля isSpace умеет только latin1.

                                  0
                                  Вы же сами видели что утф8 работает быстрее LANG=C что явно говорит что той оптимизации там нет.

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


                                  Насколько я могу судить по исходнику там эта оптимизации только на этапе компиляции включается.

                                  Там есть if (MB_CUR_MAX > 1) ... else ..., а это рантайм-константа (смотрите ветку обсуждения под первым комментом к статье).

                                    +1

                                    Естественно я вам ничего не запрещаю. Просто часто происходит что заточенный под одну задачу алгоритм работает быстрее более общего, в этом был посыл моего первого комментария. Наверное на хаскеле с дженериками или как там у вас это называется тайпклассы делать общий код будет легче чем на си.


                                    Только с C-локалью wc себя ведёт так, как будто оно ничего не знает про юникод

                                    Но это не значит что там есть шорткат для этого случая.

                                      +1
                                      Просто часто происходит что заточенный под одну задачу алгоритм работает быстрее более общего, в этом был посыл моего первого комментария. Наверное на хаскеле с дженериками или как там у вас это называется тайпклассы делать общий код будет легче чем на си.

                                      Именно! И поэтому, ИМХО, это куда больше говорит о языке, чем сырая производительность на одной конкретной задаче. Производительность-то выжать получится, а как потом это поддерживать и добавлять новую функциональность?


                                      Но это не значит что там есть шорткат для этого случая.

                                      Если его нет, то это очень плохо. По крайней мере, я не могу вспомнить, когда мне надо было бы пользоваться wc на больших файлах с учётом юникода.


                                      Но добавлять я его не рискну, там больно функция подсчёта большая и сложная.

                                        +1

                                        wc -l должен быстрее отрабатывать. Если wc -lw то там еще оно рассчитывает самую длинную строку и всякие символы типа \t

                                          +1

                                          Там \t все равно в свиче есть, даже если mbcs отключить. Просто надежны на оптимизированность были напрасными. Если бы я делал такой упрощенный ascii only wc на си — я бы делал по-другому.

                                            0
                                            wc -l должен быстрее отрабатывать.

                                            Да, быстрее.


                                            А вы статью точно читали? Там про это написано.


                                            Если wc -lw то там еще оно рассчитывает самую длинную строку

                                            Зачем? Я его не просил, и эти результаты он мне не показывает.

                                              0
                                              Зачем? Я его не просил, и эти результаты он мне не показывает.

                                              Не дооптимизировали походу. Но я читал по диагонали как и статью.

                            0

                            А почему вы в isSp написали isSp | c == 32 || c - 9 <= 4 = 1 вместо isSp | c == 32 || c <= 13 = 1? На скорость это навряд ли влияет, а мне, как человеку, который не помнит коды ASCII наизусть, сильно понятнее не стало.

                              +1

                              Потому что символы до 9 пробельными не являются, а Word8 — беззнаковый тип, и 8 - 9 = 255.

                                +1

                                Ох уж эти branch-free вычисления. А эта wrapping-семантика гарантирована или же зависит от системы?

                                  +1

                                  Тут-то как раз branch-free нет, просто сравнений меньше — c >= 9 && c <= 13 требует два сравнения, а c - 9 <= 4 обходится одним. Вероятно, вычитание дешевле сравнения — может, нагрузка на branch predictor меньше, или спекулятивного выполнения нужно меньше, или ещё что. Я недостаточно хорошо разбираюсь в этом уровне работы железа, чтобы с уверенностью сказать что-то умное, но меня результаты не удивляют и согласуются с моей интуицией.


                                  А wrapping-семантика гарантирована, да.

                              +1
                              C-вариант отрабатывает примерно за аналогичное время
                              #include <sys/stat.h>
                              #include <stdlib.h>
                              #include <stdint.h>
                              #include <stdio.h>

                              int main(int argc, char ** argv) {

                              struct stat st; if (argc != 2 || stat(argv[1], &st) != 0) return 1;
                              FILE *fp = fopen(argv[1], "rb"); uint8_t *p = malloc(st.st_size), *P = p + st.st_size;
                              if (fp == NULL || p == NULL || fread(p, 1, st.st_size, fp) != st.st_size) return 1;

                              uint64_t lc = 0, wc = 0; _Bool w = 0;

                              for(; p < P; p++) {

                              if (*p == 10) { lc++; if (w) { w = 0; wc++; } }
                              else if (*p == 32 || (uint8_t)(*p - 9) <= 4) { if (w) { w = 0; wc++; } }
                              else { w = 1; }

                              }

                              if (w) wc++;

                              printf("lc: %20lu\nwc: %20lu\nbc: %20ld\n", lc, wc, st.st_size);

                              return 0;
                              }

                                +1

                                Это ожидаемый результат.


                                Но вот сделать поддержку подсчёта лишь отдельных статистик из этого будет уже сложновато.

                                  0

                                  Ну вот и напишите на хаскель, заодно расскажиете как там девиртализируются тайпклассы.

                                    0

                                    Чтобы их девиртуализировать, их надо сначала виртуализировать, а это по умолчанию не происходит.

                                      +2
                                        0

                                        Спасибо. А оно несколько раз что ли файл проходит или каждый счётчик принимает по байту за одну итерацию? А если юникод и надо по два байта считывать? Вообщем я к сожалению мало понимаю в хаскель коде, c виду выглядит модульно. Но по-моему это только одна ветка if/else из си кода. А самая интересная часть этот диспатч для меня просто китайская грамота.

                                          0
                                          А оно несколько раз что ли файл проходит или каждый счётчик принимает по байту за одну итерацию?

                                          Да, по байту за итерацию.


                                          А если юникод и надо по два байта считывать?

                                          В рамках этой задачи много байт сразу считывать не надо. Но нужно было бы по два — можно было бы по два, почему нет.


                                          Но по-моему это только одна ветка if/else из си кода.

                                          Не совсем. На С это просто были бы отдельные функции, по функции на каждый флаг wc.

                                            0
                                            Не совсем. На С это просто были бы отдельные функции, по функции на каждый флаг wc.

                                            Я имею ввиду это та ветка из wc.c которая считает сразу всё в случае ASCII кодировки. Вы ее улучшили и не считаете то что пользователь не просит.


                                            На си тоже можно было бы сделать массив функций и в зависимости от 3-ёх флагов его формировать, потом пробегаться нему и вызывать каждый счетчик. Но это не так интересно как кодо-генерация когда массив есть только в компайл-тайме а для рантайма генерируются 2^3 функций. Я так понимаю хаскель делает второе?


                                            В рамках этой задачи много байт сразу считывать не надо.

                                            В wc.c там есть ещё memchr для случая подсчета только строк и отдельная ветка для юникода. Собственно если для подсчёта только строк действительно полезнее использовать memchr то на ваш абстрактный код это не ляжет. И юникода тоже я пока не увидел (поправьте если это не так).

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

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


                                              Но это и в хаскеле плохая идея — вот, например, мой вопрос (последние 4 абзаца там).


                                              Но это не так интересно как кодо-генерация когда массив есть только в компайл-тайме а для рантайма генерируются 2^3 функций. Я так понимаю хаскель делает второе?

                                              Типа того, да.


                                              Собственно если для подсчёта только строк действительно полезнее использовать memchr то на ваш абстрактный код это не ляжет.

                                              Нет, использовать memchr очень плохая идея, особенно когда \n часто. Я бенчмаркал: если символ для поиска встречается, например, с частотой 0.8%, то memchr отрабатывает за примерно 310 мс (на файле в 1.8 гиг в памяти). Частота в 1.6% ухудшает время до 425 мс, а частота в 10% — до 1100 мс. На SIMD можно сделать 250 мс с SSE 4.2 или 125 мс с AVX2.


                                              Но не суть. Суть в том, что ляжет: не зря там есть ByteOnlyComputer для тех случаев, когда нужно считать по байту (как слова), и есть ChunkedComputer, когда можно смотреть на всю строку целиком (для того, чтобы посчитать её размер/количество конкретных символов). При этом если запрошенные статистики все обходятся строкой целиком, то на отдельные байты никто смотреть не будет, и соответствующий цикл даже не запустится. Если же хотя бы одна из статистик требует смотреть на отдельные байты, то всё деградирует до байтов (так оказывается эффективнее, чем что-то считать по байтам, а что-то — по чанкам).


                                              И юникода тоже я пока не увидел (поправьте если это не так).

                                              Юникодовые символы оно считать вполне умеет. Пробелы вот игнорирует, да, но это решается написанием ещё одной статистики, до чего у меня когда-нибудь таки дойдут руки.

                                                0

                                                Понятно что будет медленно.


                                                Типа того, да.

                                                А как это выражается? Вот этот оператор ::: склеивает все? Может я забегаю на перед и вы планируете это описать подробнее позже.

                                                  +2

                                                  Если вкратце, ::: позволяет это сделать, но не гарантирует этого. Написать подробно, как это работает — половина следующей статьи. Надеюсь, что через этак неделю у меня получится адекватный и оформленный в статью ответ.

                                    +9
                                    Жесть форматирование, как и вставка кода.
                                    Сразу вспомнились лабы из нулевых с распечаткой кода в ворде без подсветки синтаксиса.
                                    Прямо в холодный пот.
                                      0

                                      Ниже C-вариант который отрабатывает в 3-4 раза быстрее, без магии.

                                      0

                                      На вашем процессоре (Core i7 4770) действительно "оптимизированная хакерами" версия wc "на C" обработает 1.8G из tmpfs где-то за 0,5 — 0,072 секунды (зависит от компилятора и memory bandwidth), что и будет отражать реальное соотношение "скорости" Хаскель/Си в подобных "задачах".


                                      На всякий: Си будет быстрее не потому что он "хороший", или "Хаскель плохой", а потому что позволяет не делать ничего лишнего и получать машинно-оптимальный код. Подобный вариант на Си конечно потребует больше работы человека. Поэтому такая оптимизация мало где задействуется, а болезный wc хороший тому пример ;)

                                        +1
                                        действительно "оптимизированная хакерами" версия wc "на C" обработает

                                        То есть, в coreutils не оптимизированная версия?


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

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

                                          +1
                                          То есть, в coreutils не оптимизированная версия?

                                          В это можно вкладывать очень разный смысл, особенно формулируя требования/критери переносимости и прозрачности кода, и т.п. Говоря про оптимизированную версию для упомянутого процессора я конечно имел в виду использование всех его возможностей.


                                          Если посмотреть на wc из coreutils, то там простой, переносимый и легко-поддерживаемый код, в который добавлена пара "свистелок" (например, подсчитывается максимальная "печатная" длина строк). Его можно ускорить, особенно если отказаться от чего-либо из перечисленного.


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

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


                                          Использование интринсиков, с моей точки зрения, является штатным средством оптимизации. В том числе, потому что является штатным вызовом функции с точки зрения синтаксиса и семантики языка.

                                            +1
                                            Если посмотреть на wc из coreutils, то там простой, переносимый и легко-поддерживаемый код

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


                                            в который добавлена пара "свистелок" (например, подсчитывается максимальная "печатная" длина строк).

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


                                            Человеком это не реализуется потому что дорого, в остальном актуальные компиляторы более-менее справляются.

                                            Даже на очень тривиальной задаче можно руками написать очень тупой и топорный код с парой SIMD-функций, который будет этак в 2.7 быстрее того, что сгенерирует компилятор. Задача ну прям совсем тривиальная, напишу про неё после публикации второй части этой статьи, что мы сейчас обсуждаем.


                                            Использование интринсиков, с моей точки зрения, является штатным средством оптимизации. В том числе, потому что является штатным вызовом функции с точки зрения синтаксиса и семантики языка.

                                            Но эти функции не описаны в стандарте языка и не реализуемы на этом языке, если не брать ассемблерные вставки.


                                            А если ассемблерные вставки брать (а чем они хуже интринсиков, кстати?), то… ну я вон выше давал ссылку на библиотеку, которую я сделал для написания инлайн-ассемблера в коде на хаскеле :)

                                              0
                                              в который добавлена пара "свистелок" (например, подсчитывается максимальная "печатная" длина строк).

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

                                              Причем тут композиция. Задачи и объем вычислений разный. "Быстрая" реализация на Хаскеле не выполняет ту же работу, в результате было сделано сравнение теплого с мягким.


                                              Даже на очень тривиальной задаче можно руками написать очень тупой и топорный код с парой SIMD-функций, который будет этак в 2.7 быстрее того, что сгенерирует компилятор.

                                              Опять я вас не понимаю. Если точечное, но правильное и по-месту, применение SIMD дает ускорение в разы — то это примерно идеальный вариант оптимизации (максимальный результат при минимальных усилиях).


                                              Более того, если язык или компилятор не позволяет такое (в том числе не умеют zero const abstraction), то они не подходят для задач требующих предельной производительности.


                                              Получается вот такой Хаскель-флеш ;)

                                                0
                                                Причем тут композиция. Задачи и объем вычислений разный. "Быстрая" реализация на Хаскеле не выполняет ту же работу, в результате было сделано сравнение теплого с мягким.

                                                И какую работу она не выполняет?


                                                wc показывает строки, слова и символы, хаскель-реализация тоже показывает строки, слова и символы.


                                                Если точечное, но правильное и по-месту, применение SIMD дает ускорение в разы — то это примерно идеальный вариант оптимизации (максимальный результат при минимальных усилиях).

                                                Вариант-то отличный, только что там от С остаётся? Аллокация регистров, пожалуй, да и всё?

                                                  0
                                                  И какую работу она не выполняет?

                                                  Штатный wc подсчитывает "печатную длину" строк, но выводит только если попросили опциями. Да, тупо делается лишняя работа, ибо никто не заморачивался.
                                                  Тем не менее, при "сравнении скоростей" не корректно сравнивать реализации с и без этой "особенности развития".


                                                  Вариант-то отличный, только что там от С остаётся? Аллокация регистров, пожалуй, да и всё?

                                                  Ну много что остается (типы данных, циклы).
                                                  Тем не менее, разве должна быть какая-то "пятая нога"?

                                                    +1
                                                    Штатный wc подсчитывает "печатную длину" строк, но выводит только если попросили опциями. Да, тупо делается лишняя работа, ибо никто не заморачивался.

                                                    Потому что заморочиться сложно, не так ли?


                                                    Тем не менее, при "сравнении скоростей" не корректно сравнивать реализации с и без этой "особенности развития".

                                                    Корректно: просто мы бенчмаркаем не только качество конкретного компилятора, но и выразительность языка.


                                                    И, собственно, как раз это куда корректнее выглядит как сравнение языков.


                                                    Тем не менее, разве должна быть какая-то "пятая нога"?

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


                                                    Плюс, наличие интринсиков автоматически делает ваш код непортабельным даже в рамках одной архитектуры (в смысле семейства x86_64, например).

                                                      0
                                                      Корректно: просто мы бенчмаркаем не только качество конкретного компилятора, но и выразительность языка.

                                                      Так чем вариант yleo вам не выразителен? Для си вполне обычный код, если бы вы взяли исходный более сложный счетчик на хаскеле с локалями и писали бы статью написав вот такой урощенный на си — ничего же не поменялось бы.

                                                        0
                                                        Так чем вариант yleo вам не выразителен?

                                                        Он выразителен, но речь о том, что в исходный wc почему-то не завезли оптимизацию для того, чтобы не считать длину строки (которая вообще выключена по умолчанию).


                                                        Кроме того, вариант yleo, конечно, существенно быстрее wc, но почему-то на моей машине работает за 2 секунды (см. ниже).

                                        0

                                        Промазал таки, del.

                                          +1
                                          Хотелось бы понимание того, почему получилось быстрее. С точки зрения ассемблера.
                                            +2

                                            Уже обсудили в комментариях. Если кратко — wc даже при сишной локали в дефолтной сборке использует mbcs. Там есть фоллбэк MB_CUR_MAX=1, который можно включить на этапе сборки, но даже его включение — это более сложный код, чем предложенный на хаскеле. В комментах приведен си код упрощенный до того же состояния и производительности сравнялись.


                                            В целом это ожидаемо, т.к. 99.99% использвание wc будут без изменения env переменных. А какая локаль будет включена в дистрибутиве? Ну явно не сишная, 99% — utf8, только для каких-то облегченных дистров с musl включится фоллбэк и будет только простые локали поддерживать. Это можно было бы проверить и до написания ститьи.

                                              +1
                                              Уже обсудили в комментариях. Если кратко — wc даже при сишной локали в дефолтной сборке использует mbcs. Там есть фоллбэк MB_CUR_MAX=1, который можно включить на этапе сборки, но даже его включение — это более сложный код, чем предложенный на хаскеле.

                                              Но я же думал, что уже обсудили...


                                              Я не поленился и добавил printf("FALLBACK!!\n"); в wc.c в кусок с фоллбеком. Запуск LANG=C LC_ALL=C wc ожидаемо выдаёт FALLBACK!!. Ничего для включения пересобирать не нужно.

                                                0

                                                Да, вы правы. Я думал что это константа, а это оказался вызов функции:


                                                #define MB_CUR_MAX  (__ctype_get_mb_cur_max ())
                                                  0

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

                                            0

                                            Дисклаймер: Этот комментарий добавлен не для того чтобы показать "тормознутось" Хаскеля или "превосходство" C (ибо у каждого языка свое назначение), но чтобы обратить внимание что чуть менее чем все подобные "хайповые" бенчмарки и сравнения содержат достаточно недочетов чтобы не принимать их всерьез. При этом всё же уместно напомнить тезис, что языки без zero cost abstraction никогда не смогут конкурировать по скорости кода с теми, где zero cost abstraction есть.


                                            Ниже под спойлером чистый "сишный" функциональный аналог кода на Haskell, без SIMD и прочей "магии". На моём пристарелом ноуте c i7-4600U 2.10GHz он отрабатывает за секунду:


                                            $ clang -Wall -Wextra -Wpedantic -Ofast -march=native naive_wc.c -o naive_wc
                                            
                                            $ ./naive_wc /dev/shm/test.txt
                                            lines 15000000, words 44774631, chars 1871822210
                                            took 1.038524 seconds
                                            
                                            $ clang --version
                                            clang version 8.0.1- (branches/release_80)
                                            Target: x86_64-pc-linux-gnu
                                            
                                            $ grep "model name" /proc/cpuinfo | head -n1 
                                            model name  : Intel(R) Core(TM) i7-4600U CPU @ 2.10GHz

                                            Для проверке результаты запуска системного wc c теми-же данными:


                                            $ time /usr/bin/wc /dev/shm/test.txt 
                                              15000000   44774631 1871822210 /dev/shm/test.txt
                                            19.24user 0.27system 0:19.52elapsed 99%CPU (0avgtext+0avgdata 2140maxresident)k
                                            0inputs+0outputs (0major+80minor)pagefaults 0swaps

                                            Файл test.txt был получен ровно как описано в статье, только я сразу разместил его в /dev/shm.
                                            Компилятор clang с -march=native использован чтобы создать максимально равные условия с ghc из статьи. У меня уже была 8-я версия clang, и тратить время на установку более новой я не стал.


                                            Мой ноут с i7-4600U CPU @ 2.10GHz медленнее использованного в статье i7-4770 @ 3.40GHz. Разница как минимум в 1.6 раза, а если судить по времени работы системного wc, то почти в два раза. При этом наивный, но равноценный вариант на C отрабатывает в два раза быстрее. Соответственно нормированная разница, с учетом скорости машин, получается где-то 3-4 раза.


                                            Итого: Наивный код на C быстрее фукционального аналога на Haskell в 3-4 раза.
                                            У меня всё, но прошу перепроверить результаты.


                                            Желающие могут написать статью "Побеждаем Хаскель-флеша 15 строками на С" ;)


                                            Спойлер
                                            #include <fcntl.h>
                                            #include <stddef.h>
                                            #include <stdint.h>
                                            #include <stdio.h>
                                            #include <stdlib.h>
                                            #include <sys/mman.h>
                                            #include <time.h>
                                            #include <unistd.h>
                                            
                                            /* begin */
                                            typedef struct {
                                              size_t chars, words, lines;
                                            } wc_result;
                                            
                                            static wc_result process(const unsigned char *text, const size_t bytes) {
                                              wc_result r = {bytes, 0, 0};
                                              unsigned char prev = 0;
                                              for (size_t i = 0; i < bytes; ++i) {
                                                r.lines += text[i] == '\n';
                                                r.words += text[i] > ' ' && prev <= ' ';
                                                prev = text[i];
                                              }
                                              return r;
                                            }
                                            /* end */
                                            
                                            int main(int argc, const char *argv[]) {
                                              int fd = STDIN_FILENO;
                                              if (argc > 1) {
                                                fd = open(argv[1], O_RDONLY);
                                                if (fd < 0) {
                                                  perror("open");
                                                  return EXIT_FAILURE;
                                                }
                                              }
                                            
                                              off_t length = lseek(fd, 0, SEEK_END);
                                              if (length < 0 || length > INTPTR_MAX)
                                                return EXIT_FAILURE;
                                            
                                              const void *ptr = mmap(NULL, (size_t)length, PROT_READ, MAP_PRIVATE, fd, 0);
                                              if (ptr == MAP_FAILED) {
                                                perror("mmap");
                                                return EXIT_FAILURE;
                                              }
                                            
                                              wc_result r = process((const unsigned char *)ptr, (size_t)length);
                                            
                                              struct timespec ts = {0, 0};
                                              if (clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &ts))
                                                perror("clock_gettime(CLOCK_PROCESS_CPUTIME_ID)");
                                            
                                              printf("lines %zu, words %zu, chars %zu\ntook %.6f seconds\n", r.lines,
                                                     r.words, r.chars, ts.tv_nsec * 1e-9 + ts.tv_sec);
                                              return EXIT_SUCCESS;
                                            }

                                            P.S. 15 строк имеется в виду непосредственно сам подсчет, между /* begin */ и /* end */

                                              0

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

                                                0

                                                Вроде в хаскеле тоже просто проверяется '\n' и ' '. Т.е. в данном случае тз — сделать такой же утил как пример на хаскеле.

                                                  0

                                                  А \t, \r? там проверка c-9 <= 4 была.

                                                    0

                                                    А, да, точно. Еще одино условие для ' ' надо добавить, тогда будет корректно. yleo

                                                      0

                                                      Поправил. Отрабатывает за 1.09 секунды, т.е. чуть медленне чем первый вариант. Но на пропорцию с Хаскель-вариантом это примерно не влияет.


                                                      naive_wc.c
                                                      #include <fcntl.h>
                                                      #include <stddef.h>
                                                      #include <stdint.h>
                                                      #include <stdio.h>
                                                      #include <stdlib.h>
                                                      #include <sys/mman.h>
                                                      #include <time.h>
                                                      #include <unistd.h>
                                                      
                                                      typedef struct {
                                                        size_t chars, words, lines;
                                                      } wc_result;
                                                      
                                                      static wc_result process(const unsigned char *text, const size_t bytes) {
                                                        wc_result r = {bytes, 0, 0};
                                                        _Bool prev = 0;
                                                        for (size_t i = 0; i < bytes; ++i) {
                                                          r.lines += text[i] == '\n';
                                                          _Bool now = text[i] != ' ' && text[i] - 9 > 4;
                                                          r.words += now && prev;
                                                          prev = now;
                                                        }
                                                        return r;
                                                      }
                                                      
                                                      int main(int argc, const char *argv[]) {
                                                        int fd = STDIN_FILENO;
                                                        if (argc > 1) {
                                                          fd = open(argv[1], O_RDONLY);
                                                          if (fd < 0) {
                                                            perror("open");
                                                            return EXIT_FAILURE;
                                                          }
                                                        }
                                                      
                                                        off_t length = lseek(fd, 0, SEEK_END);
                                                        if (length < 0 || length > INTPTR_MAX)
                                                          return EXIT_FAILURE;
                                                      
                                                        const void *ptr = mmap(NULL, (size_t)length, PROT_READ, MAP_PRIVATE, fd, 0);
                                                        if (ptr == MAP_FAILED) {
                                                          perror("mmap");
                                                          return EXIT_FAILURE;
                                                        }
                                                      
                                                        wc_result r = process((const unsigned char *)ptr, (size_t)length);
                                                      
                                                        struct timespec ts = {0, 0};
                                                        if (clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &ts))
                                                          perror("clock_gettime(CLOCK_PROCESS_CPUTIME_ID)");
                                                      
                                                        printf("lines %zu, words %zu, chars %zu\ntook %.6f seconds\n", r.lines,
                                                               r.words, r.chars, ts.tv_nsec * 1e-9 + ts.tv_sec);
                                                        return EXIT_SUCCESS;
                                                      }
                                                        0

                                                        На всякий, в коде есть опечатка.
                                                        Вместо r.words += now && prev должно быть r.words += now && !prev т.е. пропущен '!'.

                                                          0

                                                          Собрал без -march=native:


                                                          17:27:24 d34df00d@build2 ~/hwc % gcc -O3 main.c -o main && /usr/bin/time ./main /var/tmp/portage/test.txt            
                                                          lines 15000000, words 1767272949, chars 1871822210
                                                          took 2.223453 seconds
                                                          2.20user 0.05system 0:02.25elapsed 100%CPU (0avgtext+0avgdata 1829528maxresident)k
                                                          0inputs+0outputs (0major+28637minor)pagefaults 0swaps
                                                          17:27:29 d34df00d@build2 ~/hwc % clang -O3 main.c -o main && /usr/bin/time ./main /var/tmp/portage/test.txt            
                                                          lines 15000000, words 1767272949, chars 1871822210
                                                          took 2.032040 seconds
                                                          2.01user 0.05system 0:02.06elapsed 100%CPU (0avgtext+0avgdata 1829592maxresident)k
                                                          0inputs+0outputs (0major+28636minor)pagefaults 0swaps

                                                          clang 9.0.1, gcc 9.2.


                                                          Две секунды против 1.45. Ну так себе пропорция.

                                                            0

                                                            " наносит ответный удар ;)


                                                            Внутри примерно то (или чуть больше), что (теоретически, в моем представлении) делает ghc в ходе оптимизаций перед бэкэндом, но только на C (без налога на абстракцию) и поэтому быстрее. Суть идеи описана в другом ответе.

                                                              0

                                                              О, ну другое дело!


                                                              0:41:00 d34df00d@build2 ~/hwc % gcc -O3 main2.c -o main2 && ./main2 /var/tmp/portage/test.txt
                                                              lines 15000000, words 44774631, chars 1871822210
                                                              took 0.498306 seconds
                                                              0:41:03 d34df00d@build2 ~/hwc % clang -O3 main2.c -o main2 && ./main2 /var/tmp/portage/test.txt
                                                              lines 15000000, words 44774631, chars 1871822210
                                                              took 0.576808 seconds
                                                              0:41:08 d34df00d@build2 ~/hwc % gcc -O3 -march=native main2.c -o main2 && ./main2 /var/tmp/portage/test.txt
                                                              lines 15000000, words 44774631, chars 1871822210
                                                              took 0.499837 seconds
                                                              0:41:14 d34df00d@build2 ~/hwc % clang -O3 -march=native main2.c -o main2 && ./main2 /var/tmp/portage/test.txt
                                                              lines 15000000, words 44774631, chars 1871822210
                                                              took 0.574677 seconds

                                                              Внутри примерно то (или чуть больше), что (теоретически, в моем представлении) делает ghc в ходе оптимизаций перед бэкэндом

                                                              Нет, увы, ghc не умеет делать таких оптимизаций.


                                                              только на C (без налога на абстракцию) и поэтому быстрее

                                                              Хехе.

                                                                0

                                                                А какие оптимизации он тогда делает? Кто то знает? вроде код простой надо бы асм глянуть.

                                                                  0

                                                                  Это слишком высокоуровневая оптимизация.


                                                                  Я асм глядел, но там что-то не совсем для меня очевидное, так что я и забил.

                                                    0
                                                    Ну, не бред, а скорее жульничество.

                                                    Но вопрос — а что теперь добавилось к выброшенному? Вроде-бы считаются ASCII также как на хаскеле?
                                                  +1

                                                  Это некорректный аналог, вы считаете пробельным символом всё до символа с кодом 32, а это не так.


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


                                                  Если сделать так, чтобы хаскель-код делал то же самое — на моей машине получается 1 секунда с копейками.


                                                  Кстати, если у вас с simd или прочей магией типа broadword programming получится считать слова — дайте знать, очень интересно.


                                                  Ещё непонятно, почему -march=native1 создаёт более равные условия, ну да ладно. Хаскель-то-march=native` не делает.

                                                    0

                                                    Выше был вариант с поправленными не-пробелами (без принципиальных изменений в скорости).
                                                    Здесь вариант с поддержкой чтения из pipe и нескольких файлов (включая "-" как синоним stdin).
                                                    Чтение из pipe добавляет 1% к времени работы.


                                                    naive_wc.c (с пайпами и блекджеком)
                                                    #include <errno.h>
                                                    #include <fcntl.h>
                                                    #include <stddef.h>
                                                    #include <stdint.h>
                                                    #include <stdio.h>
                                                    #include <stdlib.h>
                                                    #include <string.h>
                                                    #include <sys/mman.h>
                                                    #include <time.h>
                                                    #include <unistd.h>
                                                    
                                                    struct {
                                                      size_t chars, words, lines;
                                                    } static result;
                                                    
                                                    static _Bool process_chunk(const unsigned char *text, const size_t bytes,
                                                                               _Bool prev) {
                                                      result.chars += bytes;
                                                      for (size_t i = 0; i < bytes; ++i) {
                                                        result.lines += text[i] == '\n';
                                                        _Bool now = text[i] != ' ' && text[i] - 9 > 4;
                                                        result.words += now && !prev;
                                                        prev = now;
                                                      }
                                                    
                                                      return prev;
                                                    }
                                                    
                                                    static int process_fd(int fd) {
                                                      off_t length = lseek(fd, 0, SEEK_END);
                                                      if (length >= 0 && length <= INTPTR_MAX) {
                                                        void *ptr = mmap(NULL, (size_t)length, PROT_READ, MAP_PRIVATE, fd, 0);
                                                        if (ptr == MAP_FAILED) {
                                                          perror("mmap");
                                                          return EXIT_FAILURE;
                                                        }
                                                        process_chunk((const unsigned char *)ptr, (size_t)length, 0);
                                                        munmap(ptr, length);
                                                        return EXIT_SUCCESS;
                                                      }
                                                    
                                                      if (length < 0 && errno != ESPIPE) {
                                                        perror("leeek");
                                                        return EXIT_FAILURE;
                                                      }
                                                    
                                                      _Bool state = 0;
                                                      ssize_t chunk;
                                                      for (;;) {
                                                        unsigned char buf[65536];
                                                        chunk = read(fd, buf, sizeof(buf));
                                                        if (chunk < 1)
                                                          break;
                                                        state = process_chunk(buf, chunk, state);
                                                      }
                                                    
                                                      if (chunk < 0) {
                                                        perror("read");
                                                        return EXIT_FAILURE;
                                                      }
                                                      return EXIT_SUCCESS;
                                                    }
                                                    
                                                    int main(int argc, const char *argv[]) {
                                                      int rc = 42;
                                                      if (argc > 1) {
                                                        for (int i = 1; i < argc; ++i) {
                                                          int fd =
                                                              (strcmp(argv[i], "-") == 0) ? STDIN_FILENO : open(argv[1], O_RDONLY);
                                                          if (fd < 0) {
                                                            perror("open");
                                                            return EXIT_FAILURE;
                                                          }
                                                          rc = process_fd(fd);
                                                          close(fd);
                                                          if (rc != EXIT_SUCCESS)
                                                            break;
                                                        }
                                                      } else
                                                        rc = process_fd(STDIN_FILENO);
                                                    
                                                      struct timespec ts = {0, 0};
                                                      if (clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &ts))
                                                        perror("clock_gettime(CLOCK_PROCESS_CPUTIME_ID)");
                                                    
                                                      if (rc == EXIT_SUCCESS)
                                                        printf("lines %zu, words %zu, chars %zu\ntook %.6f seconds\n", result.lines,
                                                               result.words, result.chars, ts.tv_nsec * 1e-9 + ts.tv_sec);
                                                      return rc;
                                                    }
                                                      +1

                                                      Оно ж показывает суммарное число по всем файлам, а не по файлу на каждый.


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

                                                  0

                                                  внедрение mmap в код — бессмысленно.
                                                  основной паттерн использования wc — это быть в хвосте пайпа


                                                  PS: было бы крайне интересно написать wc на рагеле и посмотреть что из этого получится в плане скорости.


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

                                                  скорее всего никого просто не интересует эта оптимизация.


                                                  wc обычно находится в хвосте пайпа из различных комманд.


                                                  grep pattern -r path|grep -v foo|grep bar|sed -E 's/bar/baz/'|awk '{print $1}'|grep ^ha|wc -l

                                                  и улучшать производительность его — бессмысленно

                                                    +1

                                                    Вот так и знал, что кто-то напишет про пайпы, ненужность mmap и тому подобное, хотя мне не так уж редко приходится дёргать wc на файлах на диске.


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


                                                    Во-вторых, смысл сего эксперимента не в улучшении производительности wc (иначе надо было бы бежать в дистрибутивы и предлагать пакетировать мою кастомную версию вместо coreutils), а в том, чтобы показать, как на хаскеле писать эффективный код, и какое влияние на подобные задачи имеют совершенно механические и на самом деле довольно известные оптимизации.


                                                    Скрытый текст

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

                                                    0

                                                    попробовал посмотреть что выдаёт time wc -l на этот файл.


                                                    у меня результат ОЧЕНЬ зависит от того сколько буфера использовала OS: время колеблется от 0.3 до 3 секунд

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

                                                      То есть этого вы не заметили?

                                                      0
                                                      Что такое wc?

                                                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                    Самое читаемое