Haskell в реальном мире

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

    Описание данных


    Я работаю в телекомах: фиксированная телефонная связь, интернет, IP-телефония. В задачи входит обработка трафика с АТС, с серверов IP-телефонии, поддержка текущего биллинга, написание софта и администрирование сетей, домена (да, «программист на все руки»). Недавно в моей организации было установлено новое оборудование, работающее совсем по другим принципам, и трафик, соответственно, тоже изменился. Теперь он поставляется в двух вариантах: со старых станций и с новых. Новый трафик дублируется в бинарном и текстовом форматах. Бинарники нам вообще не подходят (хотя кое-кто по незнанию говорил: «А чего там? Берешь их, и они сами в биллинг заскакивают!»), текстовый же занимает на порядок больше места, но именно с ним можно что-то сделать. Трафик со старого оборудования все еще идет, и его мы с напарником забрасываем с помощью отработанных схем, использующих сервисы местной СУБД. Можно было бы настроить эти же сервисы для трафика с новых станций, но обнаружилось несколько особенностей. Трафик на новых станциях пишется в отдельные файлы каждые 15 минут; всего таких файлов за месяц получается около 3000 (в идеале — 2976 за 31 день и 2880 за 30 дней). Каждый файл отдельно импортировать не будешь, ибо маразм. Слить в один их можно и даже нужно, благо они все текстовые, и записи о звонках расположены построчно. Ручное слияние выглядит так: выделяешь файлы только за прошлый месяц и добавляешь их в простейший скрипт слияния в командной строке. Формат имени файла фиксирован, следовательно, слияние можно автоматизировать, только придется парсить год и месяц. Линуксоиды бы использовали какой-нибудь Bash, Perl или Python, — дешево и сердито, но на Windows-машину их ради одной операции не поставишь, то же самое касается и PowerShell. А cmd — это извращение, о чем мы с вами хорошо знаем. ;) Наконец, в самом трафике тоже обнаружились сюрпризы, из-за которых даже после слияния и импорта с помощью средств СУБД требовалось много ручной SQL-работы. В общем, факторы как-то так удачно сложились в задачу для Haskell, который я в то время (апрель-май 2011) начал изучать.

    Итак, ~ 3000 15-тиминутных файлов за месяц. На оборудовании можно изменить интервал и поставить не 15 минут, а любое другое значение: 5, 10, 30, 45… Количество файлов и их размеры, соответственно, изменятся. Пример имени файла (за 09.05.2011 09:30:00):

    999992011050909300081.txt
    99999                      - идентификатор, вшитый в оборудование (по понятным причинам, я его заменил на девятки)
         2011                  - год
             05                - месяц
               09              - день
                 09            - часы
                   30          - минуты
                     00        - секунды
                       81      - какое-то случайное число, возможно, десятые доли секунд.


    Абонентов становится больше, и каждый файл уверенно растет в размере. Сейчас у нас в среднем 240 строчек на файл, но было сезонное летнее проседание, люди разъехались по отпускам и звонили меньше. За сентябрь ждем увеличения активности в полтора-два раза.

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

    |R210|2011-06-24 21:43:53|2011-06-24 01:43:52|1|


    Как нетрудно убедиться, здесь всего лишь 4 поля: идентификатор типа записи, дата начала, дата конца (формат ISO 8601/SQL) и, зачем-то, единичка. Поля разделяются вертикальной чертой, которая должна стоять и в начале записи, и в конце, так что реально полей на 1 больше, то есть, 5. Удобно считать, что поле с индексом 0 пустое, находится перед первой вертикальной чертой. Тогда отсчет значимых полей будет идти с 1.

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

    |R200|99999|111111|CR,CS,AM|1|1|3022|222222|333333|||2011-06-23 11:33:58|C|2011-06-23 11:34:22|S|0|16|1||||||1|1||||||3|162|17|1|12|24|||||||||||16|0||||||192.168.1.172||192.168.1.12||||||8|8|20|20|64|64|20|0|0|OS|7777|8888|555555|666666|0|8|9||||OS|19|||30|10|42|43||||||||||||1||||||1|1|0|3||222222|||||||2|1||333333|||||||||||||||||||||||||||||||


    Нас интересуют поля с индексами [7, 8, 9, 12, 14, 36, 112, 122], и в конечном результате хотелось бы отфильтровать всё ненужное, чтобы лишнего в СУБД не импортировать. Выбрав из сырых данных только нужное, получим строку:

    Запись:   3022|222222|333333|2011-06-23 11:33:58|2011-06-23 11:34:22|24|222222|333333
    Индексы:  7   |8     |9     |12                 |14                 |36|112   |122
    
    Индексы |  Объяснение
    ---------------------------
    7       |  код города Читы
    8, 112  |  исходящий номер
    9, 122  |  входящий номер
    12      |  дата и время начала разговора
    14      |  дата и время конца разговора
    36      |  длительность разговора в секундах


    Все остальные поля особо не нужны. Некоторые, как вы видите, вообще пустые, а смысл прочих — неизвестен. Разве что IP-адреса (изменены) принадлежат двум платам в инфраструктуре телефонной сети, между которыми пойдет RTP-трафик. Импортировав эти поля, можно было бы изучить нагрузку на платы. Возможно, в будущем пригодится.

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

    |7   |8     |9     |12                 |14                 |36  |
    |3022|222222|333333|2011-05-23 13:07:54|2011-05-23 13:37:54|1800|
    |3022|222222|333333|2011-05-23 13:07:54|2011-05-23 13:59:40|3106|
    
    |3022|444444|555555|2011-05-23 14:53:52|2011-05-23 15:23:52|1800|
    |3022|444444|555555|2011-05-23 14:53:52|2011-05-23 15:53:52|3600|
    |3022|444444|555555|2011-05-23 14:53:52|2011-05-23 16:00:50|4018|
    
    |3022|666666|777777|2011-05-23 19:15:55|2011-05-23 19:45:54|1800|
    |3022|666666|777777|2011-05-23 19:15:55|2011-05-23 20:15:54|3600|
    |3022|666666|777777|2011-05-23 19:15:55|2011-05-23 20:45:54|5400|
    |3022|666666|777777|2011-05-23 19:15:55|2011-05-23 20:47:17|5483|


    Вам-то сейчас видно, в чем соль, а тогда мне эти записи среди тысяч им подобных, среди кучи лишних полей, букв и цифр, найти было нелегко. В общем, это было или везение, или интуиция, или волшебство. :) А разгадка проста: оборудование каждые полчаса (1800 секунд) отмечает «веху разговора» на случай, если что-то произойдет. Даже если последние 29 минут разговора были почему-то утеряны, весь предыдущий трехчасовой дискурс был многажды зафиксирован — для пущей надежности. В последней записи будут актуальные данные. Возможно, на оборудовании длительность вех можно как-то изменить, а пока их ряд выглядит так: [1800, 3600, 5400, 7200, 9000, over 9000..] Здесь еще примечательно то, что запись-веха отличается в нескольких «неважных» полях от записи-результата. Возможно, стоит учесть это в будущем, чтобы более качественно отфильтровывать ненужное, а пока я принял решение все записи с длительностью из этого ряда просто выбрасывать. Теоретически, здесь какой-то малый процент нормальных звонков будет утерян, но для этого нужно, чтобы человек разговаривал полчаса в точности до секунды. Вероятность этого очень-очень маленькая, а объемы у нас не такие значительные, чтобы закон больших чисел как-то повлиял на выборку. Мы назвали это явление творчески: «Проблема 1800 секунд».

    Кратко о программах


    Всего я создал четыре программы, которые сливали нужные файлы и отфильтровывали полезную информацию. Первоначально это были parser и merger — две программы, написанные по отдельности и соединенные в третью, тоже названную merger. Все они работали крайне медленно и потребляли много памяти, хотя с задачами справлялись. Данные одного месяца (3000 файлов по 240 строк = 720000 строк) они могли обрабатывать, минимум, 10 минут с отжиранием 500 мб памяти (а то и больше, ведь работал своп). Очень, очень страшный результат. И хотя задачу надо было выполнять 1 раз в месяц, мой напарник презрительно морщил нос на Haskell. Правда, Haskell тут ну совершенно ни при чем; это я допустил в программах ряд типичных ошибок начинающего функциональщика, из-за чего кривые алгоритмы работали из рук вон плохо. Но работали! Даже больше: программы (а самая большая из них занимает всего лишь 150 полезных строк) можно было настроить из командной строки. Вот какие функции были доступны:

    1. Работа в режиме без параметров. Поля берутся по умолчанию, берутся файлы прошлого месяца.
    2. Работа в режиме с параметрами:
    — Fields [<список индексов полей>] — какие поля взять (parser Fields [1, 24, 55]);
    — (yyyy, mm) — какой месяц обрабатывать (merger (2011, 5));
    -W — не закрывать консольное окно после отработки (от слова «wait»).
    3. Получались три файла:
    — yyyy.mm.txt — в него сливались все файлы с сырым трафиком за этот месяц;
    — processed.txt — файл только с нужными полями за этот месяц;
    — yyyy.mm.txt.log — файл-лог, где перечисляются задействованные сырые файлы и пишется сводная информация (количество строк, файлов, диапазон дат).
    4. Программы выводят на экран статистику и примеры обработанного трафика.

    Пару-тройку раз мы пользовались, чем было, но потом я, конечно, переписал программу с нуля. Уж очень в старом коде было много кривого кода, ненужных велосипедов, глупых алгоритмов и странных решений. В итоге четвертая программа, NgnParser, при той же функциональности и на том же наборе данных работает не 10 минут, а 10 секунд, потребляя всего лишь 10 мб памяти. По скорости разница составляет почти два порядка и, как минимум, один — по памяти! Что можно было такого намутить, чтобы так замедлить программу? Полагаю, есть люди, наступившие на те же грабли, что и я, которые поверили скорее в тормознутость языка, чем в свои кривые руки, — недаром в Интернете так много воплей по поводу и без повода… Haskell — замечательный язык. Мне было легко писать эти программы. На каждую я тратил не более двух рабочих дней. И всякий раз получал море удовольствия. Не представляю, сколько было бы мучений, если бы то же самое я делал на C.

    Первая программа


    Первую программу я начал с простого. Покамест я сливал нужные файлы в один (merged.txt) средствами командной строки, а задача parser'а была в парсинге трафика и отфильтровывании нужных записей с идентификатором R200. Для обработки большого количества текста целесообразнее использовать специальный тип строки ByteString. Но работать с ним не так удобно, как с обычным типом String. Если ByteString — это оптимизированная реализация строки как таковой, то String — это список символов, то есть, [Char]. String, благодаря своей природе, очень удобен, но на больших данных производительность любых списков резко падает. В первых версиях программы именно String и несколько глупых решений стали причиной сильных тормозов и большого пожирания памяти. Однако, меня тогда волновала скорость разработки, а не производительность. Прототип программы я написал очень быстро. Вот как он выглядит (ревизия 2):

    replaceChars :: Char -> Char -> Char -> Char
    replaceChars whatC withC c = if c == whatC then withC else c
     
    interestFields :: [String] -> [Int] -> [String]
    interestFields s takeWhat = undefined    -- Заглушка
     
    isR200 :: [String] -> Bool
    isR200 s = (head s) == "R200"
     
    processLine :: String -> String
    processLine s = if isR200 sInWords then unwords (interestFields sInWords [1,2,3] ) else []  -- [1,2,3] - тестовые поля
                    where sInWords = words ( map (replaceChars '|' ' ') s )
     
    processString :: String -> [String]
    processString s = map processLine (lines $ s)
     
    main :: IO ()
    main = do
        str <- readFile "merged.txt"
        putStrLn (intercalate "\r\n" (processString $ str))


    Сразу можно заметить странную функцию replaceChars с типом Char -> Char -> Char -> Char. Идея была такая: берем строку-запись, заменяем вертикальную черту '|' на пробел и используем функцию words для разбиения строки на слова:

    sInWords = words ( map (replaceChars '|' ' ') s )


    В результате выполнения sInWords получится следующее преобразование:

    "|R200|99999|111111|CR,CS,AM|1|1|3022|222222|333333|||2011-06-23 11:33:58|"  -->
    " R200 99999 111111 CR,CS,AM 1 1 3022 222222 333333   2011-06-23 11:33:58 "  -->
    ["R200", "99999", "111111", "CR,CS,AM", "1", "1", "3022", "222222", "333333", "2011-06-23", "11:33:58"]


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

    Замена ' ' -> '*';
    Замена '|' -> ' ';
    Разбиение на слова функцией words;
    Обработка списка полей, получение полей с нужным индексом;
    Слияние полей функцией unwords;
    Замена ' ' -> '|'
    Замена '*' -> ' '

    Кроме того, после этих жутких преобразований количество полученных полей не совпадало с количеством исходных, — ведь пустые поля в итоге вообще исчезали (см. пример преобразования выше). Хорошо, что во всех записях пустые/заполненные поля были на одних и тех же местах, а не то б я получил неприятные артефакты. Код, как вы видите, не только избыточный, но и некрасивый. Я даже не берусь оценить его асимптотическую сложность; думаю, она далеко превысила O(n^2). Более того, ближе к ревизии 12 я понял, что надо что-то делать с полями, которые теряются из-за двойных вертикальных черт. И добавил еще одно преобразование:

    -- Чтобы пустые поля, обозначенные как "||", обрабатывались корректно, между ними вставляется пробел.
    refieldDoubles :: String -> String
    refieldDoubles [] = []
    refieldDoubles ('|':[]) = "|"
    refieldDoubles ('|':'|':ss) = "| |" ++ (refieldDoubles ('|':ss))
    refieldDoubles (s:[]) = [s]
    refieldDoubles (s:ss) = s : (refieldDoubles ss)


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

    split "|" "|R200|99999|111111|CR,CS,AM|1|1|3022|222222|333333|||2011-06-23 11:33:58|" ->
    ["","R200","99999","111111","CR,CS,AM","1","1","3022","222222","333333","","","2011-06-23 11:33:58",""]

    Что сказать… facepalm Слов нет, одни эмоции.

    Какие возможны улучшения


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

    replaceSymbols s = map (replaceChar '|' ' ') (map (replaceChar ' ' '*') s)
    -- -->
    replaceSymbols = map (replaceChar '|' ' ' . replaceChar ' ' '*')
     
     
    isR200 s = (head s) == "R200"
    -- -->
    isR200 ("R200":_) = True
    isR200 _ = False
     
     
    replaceChars whatC withC c = if c == whatC then withC else c
    -- -->
    replaceChars whatC withC c | c == whatC = withC
                               | otherwise = c
     
     
    processLine s = if isR200 sInWords then unwords (interestFields sInWords [1,2,3] ) else []
    where sInWords = words ( map (replaceChars '|' ' ') s )
    -- -->
    processLine s | isR200 sInWords = unwords (interestFields sInWords [1,2,3] )
                  | otherwise       = []
    where sInWords = words . map (replaceChars '|' ' ') $ s
     
     
    processString s = map processLine (lines $ s)
    -- -->
    processString = map processLine . lines


    Функцию intercalate "\r\n" вообще нужно было заменить на unlines. Было бы и короче, и понятнее, да и в тестах unlines показал большую производительность — не менее 30%:

    ItemsCnt  testUnlines(ns)   testIntercalate(ns)    Percent
    10        23.84             34.05                  29.9
    100       22.70             34.62                  34.4
    1000      23.28             35.48                  34.3
    10000     22.17             35.48                  37.5
    50000     22.13             33.26                  33.4
    100000    21.06             35.47                  40.6
    200000    22.70             34.05                  33.3


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

    -- Старый код:
    -- Аргумент 1 - список сырых поелй
    -- Аргумент 2 - список нужных индексов
    takeInterest :: [String] -> [Int] -> [String]
    takeInterest _ [] = []
    takeInterest ss (n:ns) = [ss !! n] ++ takeInterest ss ns
     
    -- Новый код:
    -- Аргумент 1 - аккумулятор
    -- Аргумент 2 - список нужных индексов
    -- Аргумент 3 - список сырых полей
    collectFields :: Int -> [Int] -> [String] -> [String]
    collectFields _ _ [] = []
    collectFields idx fis (s:ss) | idx `elem` fis = s : collectFields (idx+1) fis ss
    collectFields idx fis (s:ss) | otherwise = collectFields (idx+1) fis ss


    В первом случае мы итерируем список индексов и вытаскиваем элемент с помощью небезопасной функции !!. Во втором случае используем аккумулятор одновременно с итерацией по списку полей, и если аккумулятор нашелся в списке индексов, берем текущее поле с индексом аккумулятора в коллекцию. И там, и там — хвостовая рекурсия. Хотя, по тестам, новый код оказался на 40% медленнее. Возможно, в данном случае стоит вернуть старый код, — еще больше ускорить новую программу.

    ItemsCnt    takeInterest(ns)  collectFields(ns)  Percent
    10          17.33             36.84              52.9
    100         20.58             36.84              44.1
    1000        21.67             37.92              42.8
    10000       21.13             36.84              42.6
    50000       21.67             37.92              42.8


    Идем дальше


    Следующая программа — merger — должна была соединять все текстовые файлы за прошлый месяц в один. (Не хотелось каждый раз делать это вручную, а лень, как известно, движитель прогресса.) Возник вопрос: откуда узнать, какой у нас будет прошлый месяц? Да, в общем-то, это просто: берем текущую дату и отнимаем один месяц. Программа должна была использоваться исключительно в первых числах месяца, так что тут проблем не предвиделось. Текущая дата и вообще операции с датой-временем находятся в модуле Time. Операции со структурой файловой системы лежат в модуле System.Directory. И те, и другие функции, в основном, работают в монаде IO, а в то время я еще толком не умел причесывать монадный код, в итоге он выглядит жутко (merger, ревизия 14):

    main :: IO ()
    main = do
        args <- getArgs
        curDir <- getCurrentDirectory
        dirContents <- getDirectoryContents curDir
        curTime <- T.getClockTime
        monthAgoTime <- return $ T.addToClockTime (T.TimeDiff 0 (-1) 0 0 0 0 0) curTime
        calendarMonthAgoTime <- T.toCalendarTime monthAgoTime
        let maybeDateRange = case args of
                            (a:b:_) -> readDateRange (unwords [a, b])
                            _ -> Just $ defaultDateRange calendarMonthAgoTime
        case maybeDateRange of
            Just dr -> do
                        let fsToMerge = filesToMerge dirContents dr
                        let fsToMergeCountStr = show $ length fsToMerge
                        let mergeLog = (newFileName dr ++ ".log")
                        let dateRangeMsg = "DateRange: " ++ show dr
                        fsContents <- merge fsToMerge
                        writeFile (newFileName dr) (unlines fsContents)
                        writeFile mergeLog (unlines fsToMerge ++ printf "\n%s\nTotal files: %s" dateRangeMsg fsToMergeCountStr)
                        putStrLn (unlines fsContents)
                        putStrLn dateRangeMsg
                        --putStrLn ("Files to merge: " ++ unlines fsToMerge)
                        putStrLn (printf "Count of files: %s. See %s for file list." fsToMergeCountStr mergeLog)
            Nothing -> putStrLn ("Invalid date range.")


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

    merge :: [String] -> IO [String]
    merge fsToMerge = mapM readFile fsToMerge


    Она принимает список файлов, которые надо смержить, читает их и возвращает список их содержимого. В коде есть такие две строчки:

    do
        ...
        fsContents <- merge fsToMerge
        writeFile (newFileName dr) (unlines fsContents)
        ...


    Ключевой момент — unlines fsContents. То есть, все сырое содержимое всех файлов соединялось в один присест и запихивалось в файл-результат. В последствии, когда parser и merger были объединены, именно этот огромный объем данных передавался в обработку parser-части, где, вы помните, есть целая куча замен, проходов и прочего оверхеда. Вот как выглядит эта часть кода в старой программе, собранной из parser и merger:

    do
        ...
        fsContents <- readFilesToMerge fsToMerge
        let mergedContents = unlines fsContents
        writeFile (newFileName dr) mergedContents
        let processedContentStr = unlines $ processData nedeedFields mergedContents
        ...


    И это не просто facepalm плохо, это грубейшее нарушение dataflow-концепции. Должно быть так:

    Схема 1
           _____            _____            _____ 
          |     |          |     |          |     |
    A1 -> |F(A1)| -> B1 -> |G(B1)| -> C1 -> |H(C1)| -> RESULT 1 -> SAVE
          |_____|          |_____|          |_____|
    
           _____            _____            _____
          |     |          |     |          |     |
    A2 -> |F(A2)| -> B2 -> |G(B2)| -> C2 -> |H(C2)| -> RESULT 2 -> SAVE
          |_____|          |_____|          |_____|
    
           _____            _____            _____ 
          |     |          |     |          |     |
    A3 -> |F(A3)| -> B3 -> |G(B3)| -> C3 -> |H(C3)| -> RESULT 3 -> SAVE
          |_____|          |_____|          |_____|
    
    
    ...->   ...  -> ... ->   ...  ->  ... ->  ...   -> RESULT n -> SAVE


    А получилось так:

    Схема 2
        ____________________       ____________________       ____________________
       |                    |     |                    |     |                    |
       |                    |     |                    |     |                    |
       |                    |     |                    |     |                    |
    A->|        F(A)        |->B->|        G(B)        |->С->|        H(С)        |->RESULT->SAVE
       |                    |     |                    |     |                    |
       |                    |     |                    |     |                    |
       |____________________|     |____________________|     |____________________|


    Разницу между последовательной обработкой частей и обработкой всего сразу я прочувствовал в полной мере. Теперь я знаю: не стоит брать весь объем работ сразу, лучше создать механизм, который выдает данные порциями, — так будет и по памяти эффективно, и по скорости лучше. И, кроме всего прочего, программу, сделанную по второй схеме, нельзя распараллелить. Ужас, одним словом…

    Позже я пытался соптимизировать старую программу, — заменял почти везде String на ByteString. Выигрыш, конечно, был небольшой, но — веером тумана не разгонишь.

    Надо ли говорить, что новую программу, NgnTraffic, я делал, имея уже нормальный запас знаний? В ней соблюдено многое. Программа разбита на модули: Main, Constants, DataProcess, FileListProces, Options, Tools, Types. Используется, конечно, схема 1. Вместо String изначально взят тип ByteString (Strict-вариант). Код более причесан, даже бесточечный стиль в наличии. И, главное, поменялся принцип действия. Сначала собирается список файлов, которые нужно обработать, — эта часть похожа на аналогичную из старой программы. Затем, однако, файлы не читаются все сразу в одну большую переменную, а каждый читается по отдельности. Его содержимое тут же обрабатывается, строки парсятся, записи фильтруются, нужные поля вытаскиваются. Результат дописывается в результирующий файл. В итоге имеем цикл «Чтение с диска (F(An)) — Обработка строк (G(Bn)) — Запись результата на диск (H(Cn))» — и так много раз по числу файлов. Плюс, конечно, нет никаких замен одного символа на другой, а есть простая функция split из модуля Data.ByteString.Char8, которая за один проход разбивает строку-запись на поля и сама по себе выигрывает чудовищную долю производительности. Вот как выглядят функции, удовлетворяющие схеме 1:

    process' :: ResFilePath -> FieldIndexes -> FilePath -> IO ()
    process' resFile fis targetFile = do
                fileContents <- C.readFile targetFile
                let processResult = processData fis predicates fileContents
                C.appendFile resFile processResult
     
    process :: ResFilePath -> [FilePath] -> FieldIndexes -> IO String
    process _ [] _ = return "No files to process."
    process resFile fs fieldIndexes = do
        C.writeFile resFile C.empty
        mapM_ (process' resFile fieldIndexes) fs
        return "All ok."


    Здесь process принимает имя файла-результата, список файлов на обработку и индексы нужных полей. Индексы могут прийти из командной строки, поэтому они выведены как аргумент этой функции. process берет по очереди имя каждого файла и применяет к нему функцию process' (в строке mapM_ (process' resFile fieldIndexes) fs). Она уже занимается главной работой с файлами. Функция processData берет на себя обработку содержимого файла. Интересно то, что помимо фильтрования R200-записей в новой программе создан механизм предикатов: можно любое любую запись проверить по доступному предикату, а сами предикаты нетрудно дополнить нужным. Пока сделано два: поле с индексом x принадлежит списку полей и не принадлежит ему. Так выглядит тип предикатов:

    data Predicate =  NotInList [C.ByteString]
                    | InList [C.ByteString]
    type PredicateMap = [(FieldIndex, Predicate)]


    А это заданные предикаты-константы:

    predicates :: PredicateMap
    predicates = [(1,  InList [C.pack "R200"]),
                  (36, NotInList (map C.pack ["1800", "3600", "5400", "7200", "9000", "10800", "12600", "14400", "16200", "18000", "19800", "21600", "23400"]) )]


    Нетрудно догадаться, что предикатам будут удовлетворять только те записи, у которых поле 1 равно «R200», и поле 36 не содержится в списке «Проблемы 1800 секунд». Отсеивание происходит в функциях checkPredicate и examineFields:

    checkPredicate :: Predicate -> C.ByteString -> Bool
    checkPredicate (NotInList l) str = (not . elem str) l
    checkPredicate (InList l) str = elem str l
     
    examineFields :: Int -> PredicateMap -> Fields -> Bool
    examineFields _ _ [] = True
    examineFields idx preds (s:ss) = case L.lookup idx preds of
                                        Just pred -> (checkPredicate pred s) && (examineFields (idx+1) preds ss)
                                        Nothing -> examineFields (idx+1) preds ss


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

    В целом, я доволен проделанной работой. Такое бывает редко, — но код NgnTraffic мне даже нравится. А особенно нравится тот прогресс, который стал виден на примере одной и той же программы, написанной в разное время и с разными знаниями. А «еще особеннее» нравится то, что это реальная программа на Haskell, использующаяся в реальном производстве.

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

    Исходники parser по ревизиям: [2], [6], [12]
    Исходники merger (в том числе и объединенная программа merger): [13], [14], [16], [23]
    Исходники NgnTraffic

    P.S. Перевод следующей части Yet Another Monad Tutorial тоже скоро будет.
    P.P.S. Поправил ссылки на программы, спасибо товарищу steck.
    P.P.P.S. Исправил пару ошибок, спасибо товарищам goder и jack128.
    Support the author
    Share post

    Similar posts

    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 59

      +2
      Ключевой момент — unlines fsContents.

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

      В хаскеле кроме чистых функций ленивость реализована в операциях ввода-вывода. Внутри merge readFile фактически начнёт читать в тот момент, когда данные потребуются. И будет читать их чанками фиксированного размера. Грубо говоря каждый чанк будет проходить обработку, записываться в writeFile и подчищаться сборщиком мусора. Если после этого на них него других ссылок, а у вас есть.
        0
        Безусловно да. Но уже в ревизии 23 эта строчка преобразовалась в следующую:

        putStrLn (unlines . take 100 $ processedStrings)

        Это чтобы лишнее не выводить. Не скажу, правда, где именно возникают те дополнительные ссылки, которые мешают лениво читать и обрабатывать данные.
          +1
          Это всё равно ссылка на всю строку, которая непозволит сборщику очистить все элементы строки после 100
            0
            А вот ради интереса завтра уберу строку и протестирую программу.
        +3
        Очень рекомендую эту главу RWH. Помогает бороться с проблемой поедания O(n) памяти. Которой обусловлены почти все проблемы «производительности».

        А статья классная, хоть и сумбурная. Бесточечная нотация поначалу совсем не обязательна. И не только по началу.

        Других способов получше разобраться с хаскелем как я понимаю нет. После руководств совсем не понятно как всё это используется на практике. Приходится просто писать.
          0
          Большое спасибо!

          Вообще да, эту главу я еще не читал, но уже почти собирался. Книга весьма хорошая, название этой статьи как бы намекает. :)
          +5
          Линуксоиды бы использовали какой-нибудь Bash, Perl или Python, — дешево и сердито, но на Windows-машину их ради одной операции не поставишь, то же самое касается и PowerShell.

          Звучит будто Haskell входит в стандартную поставку MS Windows.
            +1
            Нет, но можно собрать исполняемый файл и использовать его на машине, где Haskell нет. Правда не знаю, можно ли скомпилировать программы на языках Perl и Python. Подозреваю, что можно.
              +2
              Для Perl'а можно, например, использовать PAR::Packer. Сгенерирует .exe-шник, в который будут засунуты все зависимые модули, библиотеки и perl'овый интерпретатор.
                +2
                Для Питона есть py2exe.
                +1
                PowerShell даже на Xp ставит банальный Windows Update. И exe с помощью PowerGui собать можно.Но статической типизации там нет, да.
              • UFO just landed and posted this here
                  +1
                  На самом деле проблема глубже. Что будет, если человек начинает длительный разговор в одном месяце, а заканчивает в другом? Ему два раза начислится сумма. А заранее знать не можем, трафика за следующий месяц может и не быть. Единственный выход — тарифицировать только запись с признаками, что она конечная, последняя.
                  +2
                  >>Линуксоиды бы использовали какой-нибудь Bash, Perl или Python
                  Эка вы поддели армию кодеров на этих языках )
                    0
                    Кстати что значит «хаскель в реальном мире»?
                    В этой задаче perl или python подошёл бы ничуть не хуже.

                    Технических проблем, связанных с написанием любого ПО, в хаскеле давно нет.
                    А никто не использует его просто потому, что он никому не нужен.
                      +2
                      Думается, именно то и значит. Очевидно, автор не ставил себе цели доказать что-то кому-то — это удел адептов той или иной технологии. Мне показалось, автор попытался просто привести пример использования действительно «из жизни», — и это вполне получилось.
                        +3
                        Насчет никому не нужен, не вполне понятно.

                        Хаскелл жив, развивается, догоняет Эрланг по некоторым возможностям (ForkIO, epoll/kqueue), но при этом является статически типизированным, со средствами метапрограммирования, компилируемым в нативный код, обладает оптимизирующим компилятором с llvm-ным бэкендом, обрастает библиотеками и пакетами, имеет несколько веб-фреймворков и много что еще.

                        Никому не нужен? А что нужно тогда?
                          +1
                          Никому не нужен в смысле не используется в бизнесе.

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

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

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

                            Кстати, в бизнесе он используется. Но мало, да.
                              +2
                              Если он программирует на с++, то в состоянии использовать питон. Или с#. Или жаву.

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

                              Просто разобраться хотя бы в нескольких концепциях хаскеля занятие не быстрое. А начать писать код с их помощью можно не известно через какое время. Хотелось бы на практике узнать длительность «втягивания» в процесс разработки на хаскеле с нуля.
                                +1
                                Ну на практике, какое-то количество людей на рынке знакомы с функциональным программированием и хотели бы его использовать, просто нет шансов его где-то применить, потому что нет вакансий.

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

                                Переехать с окамла на хаскелл можно дня за три. Окамл очень простой и осваивается недели за две, как и Эрланг, например. Хаскель, безусловно, сложнее, но писать на нём можно и не владея всеми концепциями; сложные вещи можно осваивать постепенно по мере надобности.

                                  +1
                                  А у вас это где если не секрет? И что за хаскельная вакансия? Закрыли опытным хаскелистом или переучивали?
                                    +1
                                    Небольшая компания. Разрабатываем собственный продукт и ПО на заказ. Для операторов мобильной связи, например.

                                    Вакансия — писать приложения на хаскелле. Клиент-сервер, работа с железом, веб и проч.

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

                                    Сейчас у нас пока эрланга больше, чем хаскелла, но я планирую новые проекты в основном начинать на хаскелле, ввиду его преимуществ. Там, где больше смысла использовать эрланг (SMPP, SNMP и прочие библиотеки) — будет эрланг.
                                      +1
                                      Я уже оказывается спрашивал.

                                      Вот и подтверждение тому, что хаскель используют очень ограниченный круг людей.
                                        +2
                                        Кто спорит? Но то, что его не используют другие, не повод же самому не использовать, если вещь годная?
                                  +1
                                  Я не знаю, может, я какой-то особенный, но мне хватило пары недель, чтобы понять, как Хаскелль работает и что такое функциональное программирование. При том на первой неделе я уже писал простые арифметические программы вроде факториалов и чисел Фибоначчи. К концу месяца изучения вполне свободно использовал основные монады (IO, Maybe, []). И не заметил особых трудностей в этом языке. Я даже утверждаю, что С++ гораздо сложнее, запутаннее и непрозрачнее. Нормальные программы на нем начинаешь писать позже. Конечно, мы не говорим о качестве моих знаний, приобретенных за месяц, — и в статье убедительно показывается, где они были недостаточными.

                                  Может быть, если это получится, я напишу и о процессе своего «втягивания» с нуля, — но тут история получится не слишком захватывающей. Все обыденно: писал себе и писал каждый день после работы, и как дите радовался, если что-то вдруг ни с того ни с сего заработало. :)
                                    +1
                                    «…ни с того ни с сего заработало» — это сильно сказано :)
                                      0
                                      Тут, я думаю, работало подсознание. В самом деле, я писал простенькие арифметические функции по разным примерам, еще не зная, с какой стороны подойти к языку. Просто писал что-то, внутри чего логика связей была такой же, как в примерах, с поправками на свою задачу. И оно почему-то начинало работать…
                        • UFO just landed and posted this here
                            +1
                            Но ведь вам для вашей задачи никто и не предлагал использовать хаскель? Автору захотелось попробовать «чего-то эдакого» — он попробовал и у него получилось. Своими достижениями автор поделился с общественностью. Я не заметил чтобы автор делал какие-то категоричные утверждения касательно необходимости использования той или иной технологии для каких-либо видов задач.
                            • UFO just landed and posted this here
                                +1
                                Я веду к тому что автор ведь не утверждал, что данная задача подходит для хаскеля или наоборот. Соответственно и пытаться это оспорить просто бессмысленно. Захотелось автору именно такую задачу решить именно на хаскеле — и все дела. А народ начинает спорить о том, какой ЯП больше подходит для данной задачи — да статья-то вообще не об этом!
                                  +1
                                  http://shootout.alioth.debian.org/u64q/benchmark.php?test=all&lang=ghc&lang2=python3

                                  бенчмарки не считают что питон лучше подходит в плане производительности
                                    +1
                                    По вашей ссылке показывается, что на идентичных задачах питоновский код вдвое короче. Его можно выбрать для некритичных к производительности задач. Возможно, что краткость исходников обусловлена отсутствием статической типизиции.
                                      +3
                                      В этом случае длинна хаскельных исходников обусловлена чрезмерной оптимизацией.
                                    +1
                                    Для ультимативной скорости при равной кривизне рук хаскель подходит лучше — ибо оптимизирующий компилятор.
                                    Для ультимативной надежности при тех же равных — опять лучше хаскель ибо сильная статическая типизация.
                                    Но если функциональщина еще не вошла в мозг — то рулит питон, повершелл и т.п.
                                  +3
                                  Подобные файлы скорее всего легко парсятся fsm, а значит, заметного отставания, например, от Си в этом вопросе не будет. Файловый ввод-вывод на байтстрингах тоже не уступает; вот например рассчет sha1 от файла:

                                  fileHash :: FilePath -> IO FileHash
                                  fileHash f = do
                                  content <- L.readFile f
                                  let hash = H.hashlazy content
                                  return $ concatMap (printf "%02x") (B.unpack hash)


                                  этот код работает ровно со скоростью стандартной sha1sum

                                  Хаскелл быстрее и питона, и перла. И у него очень простой и удобный FFI, который позволяет выносить критичные места в Си, если это нужно. Но это нужно крайне редко.

                                  Вот например рассчет crc16 на Haskell и С. Задача для хаскелла нехарактерная, однако справляется не сильно хуже, чем тот же Си. Так что не надо нездорового ажиотажа, Хаскелл — ок. Другое дело, что при наивных реализациях он начинает внезапно сливать. Тот же приведенный выше код рассчета SHA1 от файла при тупой реализации в лоб жрал память и не завершался. Практика нужна, и всё.

                                  • UFO just landed and posted this here
                                      +2
                                      Но вы при этом сразу делаете вывод, что хаскелл не подходит.

                                      Хаскелл — язык общего назначения, подходит для очень большого спектра задач. И уж точно файлы парсить и статистику считать он будет, мягко говоря, не хуже, чем некоторые интерпретируемые языки с динамическрой типизацией.

                                      Я не вникал детали того, что конкретно делал автор, но если он не использовал для парсинга своих файлов attoparser или happy/alex или bnfc — значит, скорее всего делал что-то не то, какой смысл парсить это вручную вообще, да еще и медленно.

                                      • UFO just landed and posted this here
                                          +1
                                          Вы сравнили разный код для разных задач, написанный разными людьми с разным уровнем владения инструментом.
                                          • UFO just landed and posted this here
                                            0
                                            Я более чем уверен, что даже моя вторая, эффективная, программа может быть улучшена по многим показателям. Я пока еще не гуру Хаскелля.
                                      +1
                                      Тоже самое можно сказать и о Perl, легко ставится под винду, задача как раз для него, и со строками справляется лучше всех =)
                                      не Питоном единым сыты
                                      +1
                                      Прочитал о воркарраунде с заменой пробела звездочкой и окончательно убедился, что люди готовы на любое извращение, лишь бы ничего не знать об «этих жутких регэкспах».

                                      * Правда сам грешен сегодня выкусывал из html'a кусок типа $.get(url, function(s){ $("#id").html( $s.substring(s.indexOf('>', s.indexOf('<BODY'))+1, s.indexOf(''))); });
                                        0
                                        Можно было бы и регэкспы. Было бы интересно сравнить производительность разных решений.
                                          +1
                                          Есть мнение что об «этих жутких регекспах» действительно можно ничего не знать.

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

                                          Комбинаторы парсеров в питоне, в хаскеле.

                                          ipAddr :: GenParser Char st Word32
                                          ipAddr = do
                                              as <- many1 digit
                                              let a = read as
                                              when (a > 255) $ fail "ip address octet must be >= 0 && < 256"
                                              char '.'
                                              bs <- many1 digit
                                              let b = read bs
                                              when (b > 255) $ fail "ip address octet must be >= 0 && < 256"
                                              char '.'
                                              cs <- many1 digit
                                              let c = read cs
                                              when (c > 255) $ fail "ip address octet must be >= 0 && < 256"
                                              char '.'
                                              ds <- many1 digit
                                              let d = read ds
                                              when (d > 255) $ fail "ip address octet must be >= 0 && < 256"
                                              eof
                                              return $ shiftL a 24 + shiftL b 16 + shiftL c 8 + d
                                          
                                            0
                                            И так тоже можно было бы…
                                              +1
                                              интересно. действительно интересно.

                                              но человека который так решил приведенную задачу я бы на работу не взял, как и человека написавшего регэксп. в этой задаче обычного split выше крыши
                                                0
                                                Я вас не совсем понимаю. split в полной мере используется в новой версии программы. А в начале своего пути я, конечно, дал маху с заменами символов, но это было по неопытности. Вряд ли можно корить начинающего в том, что он начинающий.
                                                  +2
                                                  Это задача парсинга пользовательского ввода.

                                                  Сплит это конечно хорошо. Но там ещё нужен один ифник для проверки того, что октетов 4. И ещё проверки того, что не встретились посторонние символы. А может тестировщик найдёт и другие проблемы.

                                                  Здесь мы получаем автоматическую генерацию сообщений об ошибках. Введена буква? Библиотека внутри сгенерит ошибку «expected digit». 3 октета вместо 4, будет сгенерина ошибка «unexpected eof, expected digit or '.'», если октетов больше 4, будет сгенерина ошибка «unexpected '.', expected eof». И это всё уже внутри этого кода.

                                                  Кроме того, этот подход универсален. Эта функция парсит ip адрес, другие функции в этом модуле точно так же парсят более сложные вещи. Ip-адрес конечно можно распарсить сплитом и регекспом. Но, например, выражение со скобками нельзя.

                                                  Используя комбинаторы парсеров везде, мы получаем выйгрыш в универсальности.
                                                    0
                                                    Это смешение теплого и мягкого — сплиты применяются для разбора структурированных данных, регэкспы для быстрой проверки/выкуса конкретного фрагмента.

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

                                                    scalar($post =~ /\bрегэксп/mgo);

                                              +2
                                              я имел ввиду пример с парсингом ip

                                              а по поводу вашей программы… могу сказать только одно — вы молодец.

                                              любая решенная задача (не важно каким методом или какими средствам) это плюс в карму в реале)
                                                +1
                                                Чур какашками не кидаться, но у меня парсер access-logs, разбитых с помощью cronolog на файлы по 1 минуте работает достаточно шустро: просто парсинг без базы данных и др. логики — 4 минуты на ~15 млн. записей (лог за месяц).
                                                  0
                                                  Ну что вы так сразу — «не кидаться»… Здесь вроде бы культурные люди собрались. А иным Haskell и не интересен. :)

                                                  Видимо, это хороший результат — 15 млн. записей за 4 минуты… Но мне кажется, можно было еще быстрее. То есть, у меня 10 сек. = 700 000 записей, 1 мин. = 4 200 000 записей. На 4 минуты это уже 16 млн… То есть, примерно как у вас. Я хочу еще больше оптимизировать свою программу, благо, пути для этого наметились. Если выйдет что-нибудь интересное, опять будет топик. :)
                                                    +1
                                                    Если ценой одного рабочего дня производительность поднимется на 10% для операции периодической и некритичной — то ну его нафиг такую оптимизацию :) Есть куча критичных задач, да и сервера свои и за процессорное время и т.д. мы не платим.
                                                      0
                                                      Ну а у меня это просто повод изучить оптимизацию в Haskell.
                                                  +1
                                                  Интересно, как некоторые языки прочно привязаны к одной области применения. Например хаскель, эрланг настолько прочно к биллингу в сотовых сетях, что вот и эта статья про биллинг, и в комментариях есть «Небольшая компания. Разрабатываем собственный продукт и ПО на заказ. Для операторов мобильной связи, например.»

                                                  В каких еще областях у хаскеля есть success stories? Просто интересно.
                                                    0
                                                    На самом деле применения есть, но, конечно, их мало в сравнении с другими языками. На странице «Haskell in industry» приводится несколько десятков успешных программ на Haskell. Из них:

                                                    * ИИ для оборонной промышленности
                                                    * Обработка ДНК в терапевтической компании
                                                    * Симуляторы для тестирования беспроводного оборудования
                                                    * В Bank of America Merril Lynch Haskell используется как бэкенд для обработки данных
                                                    * И многое другое

                                                  Only users with full accounts can post comments. Log in, please.