Проблемы с потреблением памяти

[Александр Замараев]

Такая задачка:

Есть пачка апачевских логов - 20 штучек.
Один - почти гиг, остальные поменьше.
Встала задачка посчитать разную статистику.
Простейший пример: найти 100 IP-шек, на которые в сумме потрачено больше всего времени.

Формат лога довольно простой: нужные нам поля в начале и разделены пробелом.

Функция для разбора строки:

line2item :: BS.ByteString -> Maybe (BS.ByteString, Int)

line2item line = ret_tupl $ time_str

  where

    [ip, _, time_str] = take 3 . BS.split ' ' $ line

    ret_tupl "-" = Nothing

    ret_tupl ts = case readMaybe . BS.unpack $ ts of

      Nothing -> Nothing

      Just t -> Just (ip, t)

И стало быть main

import qualified Data.ByteString.Lazy.Char8 as BSL

import qualified Data.ByteString.Char8 as BS

import qualified Data.HashMap.Strict as DM

main :: IO()

main = do

  args <- getArgs

  let paths = if null args then [dir] else args

  files <- forM paths (\path -> do -- Получаем список списков нужных логов

    fnames <- getDirectoryContents path

    return . map (path </>) $ fnames)

  let logs = filter (isSuffixOf "-access_log") . concat $ files

  log_contents <- forM logs (\fn -> do -- Получаем список списков записей из всех файлов

    cont <- BSL.readFile fn

    return . map line2item . map BSL.toStrict . BSL.lines $ cont)

  let items = foldl' f DM.empty . concat $ log_contents -- Считаем статистику

      f ips Nothing = ips

      f ips (Just (ip, time)) = DM.insertWith (+) ip time ips

  let -- Выбираем 10 самых толстых

      strs = take 10 . reverse . sortBy (compare `on` snd) . DM.toList $ items

  putStrLn . unlines . map (\(i, t) -> printf "%s: %d" (BS.unpack i) t) $ strs

Вроде вполне быстро работает. Но вот памяти съедает больше гига.

Похоже, что логи таки засасываются в память полностью, или где-то накапливаются отложенные вычисления.

Чего хотелось бы избежать.

Похоже что я чего-то не понимаю/вижу.

Может ли кто-нибудь прояснить ситуацию.

П. С. Аналогичная прожка на Python-е не вылазит за 10мб и работает несколько быстрее.

[Никита Тимофеев]

А можешь ради интереса переписать программу с ByteString на Text и сравнить результаты? Просто очень любопытно не связано ли это с тем что ByteString'и живут  в сишной куче. Кстати, в начале чего располагаются нужные поля? Показал бы ты файл, что ли…

14 июня 2014 г., 13:17 пользователь Александр Замараев <tonal.p...@gmail.com> написал:

--
Вы получили это сообщение, поскольку подписаны на группу "Русский Haskell".
Чтобы отменить подписку на эту группу и больше не получать от нее сообщения, отправьте письмо на электронный адрес haskell-russi...@googlegroups.com.
Чтобы отправлять сообщения в эту группу, отправьте письмо на электронный адрес haskell...@googlegroups.com.
Чтобы посмотреть обсуждение на веб-странице, перейдите по ссылке https://groups.google.com/d/msgid/haskell-russian/e9245621-5c79-4e3e-a07d-c7f3cf89f5ff%40googlegroups.com.
Чтобы настроить другие параметры, перейдите по ссылке https://groups.google.com/d/optout.

--
Тимофеев Н.Д.

[Alexander Tchitchigin]

Не специалист, но возникает подозрение, что " map BSL.toStrict" провоцирует считывание всего в память.

Может, стОит на кондуитах переписать для контроля памяти и вообще?

Чтобы посмотреть обсуждение на веб-странице, перейдите по ссылке https://groups.google.com/d/msgid/haskell-russian/CAOMWv%3DLtv%2BzyteuXwX6pYXUwuGPSfRJzgNR%3DZNjb6veVWj9GTw%40mail.gmail.com.

Чтобы настроить другие параметры, перейдите по ссылке https://groups.google.com/d/optout.

--
С уважением,
Александр.

[Александр Замараев]

суббота, 14 июня 2014 г., 18:01:07 UTC+7 пользователь Gabriel написал:

Не специалист, но возникает подозрение, что " map BSL.toStrict" провоцирует считывание всего в память.

map применяет BSL.toStrict к каждой конкретной строке и не требует засасывания всех в память.

 К тому же этот код у меня работает ка и ожидается в другом проекте. 

Может, стОит на кондуитах переписать для контроля памяти и вообще?

Попробую и на Text-е и на кондуитах, только хотелось бы разобраться в чём тут подвох...

[Maxim Taldykin]

> ret_tupl ts = case readMaybe . BS.unpack $ ts of

Это не причина потребления лишней памяти, но очень неэффективный код.
Для чтения числа из строки лучше использовать decimal из
Data.Text.Read.

Я позволил себе переписать всё на Text.Lazy.Используемая память
пропорциональна размеру хэша с агрегированными данными.
Вполне возможно, что вашем исходном коде память тоже никуда не течёт.
Если в логах преимущественно уникальные адреса, то все их придётся
хранить в хэше и он как раз будет сравним с размерами самого лога.

Обычно такие статистики собираются с помощью поточных алгоритмов,
можете погуглить что-нибудь вроде heavy hitters in data streams.

{-# LANGUAGE OverloadedStrings, ViewPatterns #-}

import Control.Applicative
import Data.Text.Lazy (Text)
import qualified Data.Text.Lazy as L
import qualified Data.Text.Lazy.IO as L
import qualified Data.Text.Lazy.Read as L
import Data.Map(Map)
import qualified Data.Map as Map
import Data.List
import Data.Maybe (catMaybes)
import Data.Ord (comparing)

import System.Environment (getArgs)
import System.Directory
import System.FilePath ((</>))

line2item :: Text -> Maybe (Text, Int)
line2item line = case L.words line of
ip : _ : timeStr : _
| Right (t,"") <- L.decimal timeStr -> Just (ip, t)
_ -> Nothing

fileItems :: Text -> [(Text,Int)]
fileItems = catMaybes . map line2item . L.lines

stats :: [(Text,Int)] -> [(Text,Int)]
stats
= take 10
. sortBy (flip $ comparing snd)
. Map.toList
. foldl' (\m (ip,t) -> Map.insertWith' (+) ip t m) Map.empty

main :: IO ()
main = do
let path = "." -- FIXME:
let dir = "."

args <- getArgs
let paths = if null args then [dir] else args

files <- map (path </>) . concat
<$> mapM getDirectoryContents paths
let logs = filter (isSuffixOf "-access_log") files
logContents <- mapM (fmap fileItems . L.readFile) logs
mapM_ (putStrLn . show) $ stats $ concat logContents

[Arthur Welf]

Я в Haskell’е новичок, поэтому могу ошибаться, но, мне кажется, проблема лежит не в используемых библиотеках, а в вашем алгоритме. Вы сначала обрабатываете все имеющиеся у вас файлы, сливаете все записи в один огромный список (очевидно, и занимающий вашу память), который потом сортируете и выбираете 100 самых толстых. 

Я бы пошел несколько другим путем: 

1. Дробим файлы на множество небольших файлов (скажем, по 200 записей в каждом). 

2. Сортируем эти 200 записей из каждого файла, и оставляем только 100 самых толстых. 

3. Конкатенируем получившийся список с аналогичным списком, образовавшимся в результате обработки другого файла, и снова получаем список из 200 записей. 

4. Опять их сортируем и снова оставляем только 100 самых толстых из них. 

5. И так далее, пока не останется только 100 самых толстых записей. 

P.S. (лирическое отступление): Когда я учился в медицинском институте, преподаватель с кафедры микробиологии рассказывала, как она работала во время эпидемии холеры в Одессе в 1972 году. Тогда холеру привезли на каком-то судне через порт, и власти не давали разрешения на сход команд стоявших на рейде кораблей на берег, пока медики не убедятся, что на кораблях нет носителей холерного вибриона. Точно так же корабли не выпускали из порта, пока не убедятся, что на их борту не было носителей холеры. Кораблей было очень много, и делать каждому члену экипажа анализ было слишком времязатратно. Поэтому медики придумали следующее: они смешивали анализы всего экипажа каждого корабля в одну банку, и проверяли ее на наличие холерного вибриона (то есть делали один анализ на один корабль). Если анализ был отрицательным - кораблю давали зеленый свет. Если положительным - то команду разделяли на 2 группы, анализы в каждой группе опять-таки смешивали, и снова проверяли их на наличие холерного вибриона. Таким образом, проведя только небольшое количество анализов, медикам удалось выполнить задание партии и правительства. Мне это почему-то вспомнилось в связи с вашим вопросом, сорри за оффтоп ;)). 

-- 

Best regards,

Arthur Welf

суббота, 14 июня 2014 г. в 19:26, Maxim Taldykin написал:

Чтобы добавлять сообщения в эту группу, отправьте письмо по адресу haskell...@googlegroups.com.

Просмотреть это обсуждение в Сети можно по адресу https://groups.google.com/d/msgid/haskell-russian/CABxyK-nj-eSdikHi2ODMwcmDZeC7djO43OcJMNsNkbki1G25sg%40mail.gmail.com.

Настройки подписки и доставки писем: https://groups.google.com/d/optout.

[Maxim Taldykin]

14 июня 2014 г., 21:15 пользователь Arthur Welf <arthu...@gmail.com> написал:

> Я в Haskell’е новичок, поэтому могу ошибаться, но, мне кажется, проблема
> лежит не в используемых библиотеках, а в вашем алгоритме. Вы сначала
> обрабатываете все имеющиеся у вас файлы, сливаете все записи в один огромный
> список (очевидно, и занимающий вашу память), который потом сортируете и
> выбираете 100 самых толстых.

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

>
> Я бы пошел несколько другим путем:
> 1. Дробим файлы на множество небольших файлов (скажем, по 200 записей в
> каждом).
> 2. Сортируем эти 200 записей из каждого файла, и оставляем только 100 самых
> толстых.
> 3. Конкатенируем получившийся список с аналогичным списком, образовавшимся в
> результате обработки другого файла, и снова получаем список из 200 записей.
> 4. Опять их сортируем и снова оставляем только 100 самых толстых из них.
> 5. И так далее, пока не останется только 100 самых толстых записей.

Пусть, например, данные имеют следующий вид:
- 199 записей с уникальными ключами
- потом одна запись с ключом ХХХ
- так повторяется несколько раз.
Т.е. самая часто встречающаяся запись как раз с ключом ХХХ будет,
однако нет никакой гарантии того, что она не будет каждый раз
отбрасываться на шаге 2.

[Александр Замараев]

суббота, 14 июня 2014 г., 23:26:54 UTC+7 пользователь Maxim Taldykin написал:

>     ret_tupl ts = case readMaybe . BS.unpack $ ts of

Это не причина потребления лишней памяти, но очень неэффективный код.

Да. я знаю. Набросал просто для быстроты, с мыслью поправить потом. :)

 

Для чтения числа из строки лучше использовать decimal из
Data.Text.Read.

Для Data.ByteString это будет readInt насколько я понял

Я позволил себе переписать всё на Text.Lazy.Используемая память
пропорциональна размеру хэша с агрегированными данными.

Спасибо за ваш труд - интересно сравнить код решения.

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

Я сравнил скорости и требования к памяти. Получается примерно так:

Всего логов: 20
Общее количество строк: 2189232
Уникальных IP: 31485

Самый большой файл: 853535Kб

fat_ip.py - Простая реализация на Python-е
время ~10сек. память < 10мб.

fat_ip_bs - Haskell реализация на Data.ByteString.Lazy

время ~5-6сек. память < 1гб.

fat_ip_text - Haskell реализация на Data.Text.Lazy

время ~1мин 30сек. память < 400мб.

Другая выборка логов

Всего логов: 20
Общее количество строк: 1375093 
Уникальных IP: 17829

Самый большой файл: 315612Kб

fat_ip.py - Простая реализация на Python-е
время ~5-6сек. память ~ 5мб.

fat_ip_bs - Haskell реализация на Data.ByteString.Lazy

время ~3,5сек. память ~ 400мб.

fat_ip_text - Haskell реализация на Data.Text.Lazy

время ~44-45сек. память ~ 250мб.

Я бы сказал, что для версии  с ByteString размер памяти больше похож на размер самого большого файла.

А в версии Text больше похож на разницу в количестве IP-шек.

Ну и прожорливость таки несколько обескураживает. Как и скорость работы для версии с Text.

Т. е. пока Python по совокупности изрядно лучшее...

В реализации на ByteString убрал ByteString.Strict и заменил line2item на использование readInt:

line2item line = case BS.words line of

  ip : _ : timeStr : _

    | Just (t, "") <- BS.readInt timeStr -> Just (ip, t)

  _ -> Nothing

Реализации на Data.Text сделал 2 - Ваш код и мой с заменой ByteString на Text.
Видимых отличий по памяти и скорости нет.

Да. на кондуитах пока не пробовал.

[Maxim Taldykin]

А расшарьте пожалуйста исходнички на каком-нибудь гитхабе/битбакете,
было бы интересно таки допилить до нормальной производительности.
Магия питона, если не ошибаюсь, заключается в том, что все операции со
строками на сях написаны. В своё время я им парсил логи по 20Gb,
действительно волшебно получалось.

В случае с байтстрингами можно попробовать адресам делать copy[1]
прежде чем вставлять их в хэш, предположительно это уменьшит
используемую память.
Кстати, раз уж у вас несколько файлов с логами, интересно было бы
распараллелить обработку.

[1] https://hackage.haskell.org/package/bytestring-0.10.4.0/docs/Data-ByteString.html#g:23


16 июня 2014 г., 10:18 пользователь Александр Замараев
<tonal.p...@gmail.com> написал:

> суббота, 14 июня 2014 г., 23:26:54 UTC+7 пользователь Maxim Taldykin
> написал:
>>
>> > ret_tupl ts = case readMaybe . BS.unpack $ ts of
>>
>> Это не причина потребления лишней памяти, но очень неэффективный код.
>
> Да. я знаю. Набросал просто для быстроты, с мыслью поправить потом. :)
>
>>
>> Для чтения числа из строки лучше использовать decimal из
>> Data.Text.Read.
>
> Для Data.ByteString это будет readInt насколько я понял

Возможно bytestring-lexing будет ещё быстрее, но это только если
производительность действительно в парсер чисел упирается.

Можно избавиться от ViewPatterns и немножко компактнее получится.
line2item line = do
ip : _ : timeStr : _ <- return $ BS.words line
(ip,) . fst <$> BS.readInt timeStr

> https://groups.google.com/d/msgid/haskell-russian/48dd8dc6-7927-46d4-bba3-c17187b3cf34%40googlegroups.com.

[Александр Замараев]

понедельник, 16 июня 2014 г., 15:33:45 UTC+7 пользователь Maxim Taldykin написал:

А расшарьте пожалуйста исходнички на каком-нибудь гитхабе/битбакете,
было бы интересно таки допилить до нормальной производительности.

https://github.com/tonal/fat_ip 

Сложил туда все тестовые исходники и написал краткую аннотацию.

 

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

Я встречал простые примеры на Сях которые проигрывали по скорости ввода/вывода и работы со строками Python-у.
Так что там не столько «реализация на С», а скорее очень аккуратная реализация. :)

В случае с байтстрингами можно попробовать адресам делать copy[1]
прежде чем вставлять их в хэш, предположительно это уменьшит
используемую память.

Это сыграло прамо таки драмотично! :)

Что опять же поднимает вопрос об аккуратности реализации библиотек работы со строками в Haskell.

 

Кстати, раз уж у вас несколько файлов с логами, интересно было бы
распараллелить обработку.

Теперь, когда понятно как работать быстро и экономно работать в одном потолке можно и параллелить. :)

[Alexander V Vershilov]

> Что опять же поднимает вопрос об аккуратности реализации библиотек работы со строками в Haskell.

Если только вопрос о внимательности чтения документации. В Haskell
строка бинарных данных (ByteString),
устроена следующим образом:

data ByteString = ByteString Offset Length (ForeignPtr Word8)

ну и все поля строгие и распакованные, таким образом операции взятия
среза (init, tail, take, ...) могут
выполняться за O(1) времени и аллокации ~8 байт памяти. Однако, если
существует хотя бы один
указатель на полную строку, то она не удаляется. Если Вам в необходимо
использовать части больших
данных в программе, то 'copy' позволяет скопировать только
интересующий кусок и работать с ним, о
чем и написано в документации.

Кстати хотелось бы ещё раз вставить слово, что в данном случае стоило
работать с Text, а не ByteString
по следующим причинам:

1. идеоматичность - работаете вы с текстом, а не с бинарными данными
2. Text находится в unpinned памяти, что обеспечивает, гораздо более
эффективную работу gc и
спасает от фрагментации памяти.
3. Text поддерживать stream fusion, что позволяет автоматически
свернуть код в большой и эффективный
for loop, позволяющий зачастую избавиться от большинтсва аллокаций.

Однако стоит заметить, что и с Text Вам понадобиться copy.

--
Александр

> https://groups.google.com/d/msgid/haskell-russian/b8c81867-6b97-492a-9d5b-ef1603e54cee%40googlegroups.com.

>
> Чтобы настроить другие параметры, перейдите по ссылке
> https://groups.google.com/d/optout.



--

Alexander

[Maxim Taldykin]

17 июня 2014 г., 11:08 пользователь Alexander V Vershilov
<alexander...@gmail.com> написал:

>> Что опять же поднимает вопрос об аккуратности реализации библиотек работы со строками в Haskell.
>
> Если только вопрос о внимательности чтения документации. В Haskell
> строка бинарных данных (ByteString),
> устроена следующим образом:
>
> data ByteString = ByteString Offset Length (ForeignPtr Word8)
>
> ну и все поля строгие и распакованные, таким образом операции взятия
> среза (init, tail, take, ...) могут
> выполняться за O(1) времени и аллокации ~8 байт памяти. Однако, если
> существует хотя бы один
> указатель на полную строку, то она не удаляется. Если Вам в необходимо
> использовать части больших
> данных в программе, то 'copy' позволяет скопировать только
> интересующий кусок и работать с ним, о
> чем и написано в документации.

Это всё действительно очевидно, только почему-то никто не написал об
этом неделю назад.

>
> Кстати хотелось бы ещё раз вставить слово, что в данном случае стоило
> работать с Text, а не ByteString
> по следующим причинам:
>
> 1. идеоматичность - работаете вы с текстом, а не с бинарными данными
> 2. Text находится в unpinned памяти, что обеспечивает, гораздо более
> эффективную работу gc и
> спасает от фрагментации памяти.
> 3. Text поддерживать stream fusion, что позволяет автоматически
> свернуть код в большой и эффективный
> for loop, позволяющий зачастую избавиться от большинтсва аллокаций.
>

Я тоже так думал, но почему-то моя версия с текстом на порядок
медленнее получилась.

> Однако стоит заметить, что и с Text Вам понадобиться copy.

Зачем? У них же чанки в хаскельной куче.

> Чтобы добавлять сообщения в эту группу, отправьте письмо по адресу haskell...@googlegroups.com.

> Просмотреть это обсуждение в Сети можно по адресу https://groups.google.com/d/msgid/haskell-russian/CAO-1Pb5FkuXik_zd4CkJJ_C6ce6C5xiZV6x9%3DPxSo9LUyg9HVg%40mail.gmail.com.

[Alexander V Vershilov]

2014-06-17 11:26 GMT+04:00 Maxim Taldykin <jor...@gmail.com>:
> 17 июня 2014 г., 11:08 пользователь Alexander V Vershilov
> <alexander...@gmail.com> написал:
>>> Что опять же поднимает вопрос об аккуратности реализации библиотек работы со строками в Haskell.
>>
>> Если только вопрос о внимательности чтения документации. В Haskell
>> строка бинарных данных (ByteString),
>> устроена следующим образом:
>>
>> data ByteString = ByteString Offset Length (ForeignPtr Word8)
>>
>> ну и все поля строгие и распакованные, таким образом операции взятия
>> среза (init, tail, take, ...) могут
>> выполняться за O(1) времени и аллокации ~8 байт памяти. Однако, если
>> существует хотя бы один
>> указатель на полную строку, то она не удаляется. Если Вам в необходимо
>> использовать части больших
>> данных в программе, то 'copy' позволяет скопировать только
>> интересующий кусок и работать с ним, о
>> чем и написано в документации.
>
> Это всё действительно очевидно, только почему-то никто не написал об
> этом неделю назад.

Все были заняты, или не занимались ручным парсингом строк, в результате
которого в программе остаются объекты ссылающиеся на исходную строку.
Я, например, честно забыл о `copy`, но каждый раз когда вижу подобную
ситуацию в своем коде, то вспоминаю.
Это, действительно, нужно помнить, но с другой стороны во всех серьёзных
мануалах об этом пишут.

>>
>> Кстати хотелось бы ещё раз вставить слово, что в данном случае стоило
>> работать с Text, а не ByteString
>> по следующим причинам:
>>
>> 1. идеоматичность - работаете вы с текстом, а не с бинарными данными
>> 2. Text находится в unpinned памяти, что обеспечивает, гораздо более
>> эффективную работу gc и
>> спасает от фрагментации памяти.
>> 3. Text поддерживать stream fusion, что позволяет автоматически
>> свернуть код в большой и эффективный
>> for loop, позволяющий зачастую избавиться от большинтсва аллокаций.
>>
>
> Я тоже так думал, но почему-то моя версия с текстом на порядок
> медленнее получилась.

К сожалению я так и не нашёл времени подробно посмотреть код.
Поэтому спрошу так (-O) было? иначе правила не будут использоваться
и основные плюсы Text спадут на нет.

>> Однако стоит заметить, что и с Text Вам понадобиться copy.
>
> Зачем? У них же чанки в хаскельной куче.

Проблема не в положении данных, а в том, что Text имеет тот же формат, что
и ByteString, и тем самым не позволяет освободить чанк, если на него есть
ссылки. А подстроки это ссылки. Тип памяти влияет, но в данном случае
это не должно быть заметно.

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

> Просмотреть это обсуждение в Сети можно по адресу https://groups.google.com/d/msgid/haskell-russian/CABxyK-%3DYQhc6JeKvLC5juNHLZhY9dTGBQ9ZnDD7sMPikn2p6MQ%40mail.gmail.com.

> Настройки подписки и доставки писем: https://groups.google.com/d/optout.

--
Alexander

[Александр Замараев]

вторник, 17 июня 2014 г., 14:39:52 UTC+7 пользователь Alexander (qnikst) Vershilov написал:

> Это всё действительно очевидно, только почему-то никто не написал об
> этом неделю назад.

Все были заняты, или не занимались ручным парсингом строк, в результате
которого в программе остаются объекты ссылающиеся на исходную строку.
Я, например, честно забыл о `copy`, но каждый раз когда вижу подобную
ситуацию в своем коде, то вспоминаю.
Это, действительно, нужно помнить, но с другой стороны во всех серьёзных
мануалах об этом пишут.

Видимо не читал «серьёзных мануалов» т, к. ранее не встречал.

Но теперь буду знать и помнить - спасибо сообществу! :)

 

>>
>> Кстати хотелось бы ещё раз вставить слово, что в данном случае стоило
>> работать с Text, а не ByteString
>> по следующим причинам:

> Я тоже так думал, но почему-то моя версия с текстом на порядок
> медленнее получилась.
К сожалению я так и не нашёл времени подробно посмотреть код.
Поэтому спрошу так (-O) было? иначе правила не будут использоваться
и основные плюсы Text спадут на нет.

Ежели зайдёте на гитхаб: https://github.com/tonal/fat_ip
То там есть все тексты и параметры компиляции. При -O3 или -O2 отличий не обнаружил.
Но версия с Text.Lazy медленнее чем с ByteString.Lazy более чем на порядок (~20раз)
Причём одна из другой получилась просто сменой типов и функции разбора числа.

 

>> Однако стоит заметить, что и с Text Вам понадобиться copy.
>
> Зачем? У них же чанки в хаскельной куче.

Проблема не в положении данных, а в том, что Text имеет тот же формат, что
и ByteString, и тем самым не позволяет освободить чанк, если на него есть
ссылки. А подстроки это ссылки. Тип памяти влияет, но в данном случае
это не должно быть заметно.

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

По ходу в данных получилось что практически на каждый чанк есть  ссылки - и только copy помогла избавится от лишней памяти...

[Maxim Taldykin]

> При -O3 или -O2 отличий не обнаружил.

их не должно быть, эти флаги пока что ничем не отличаются

[Maxim Taldykin]

>>> Однако стоит заметить, что и с Text Вам понадобиться copy.
>>
>> Зачем? У них же чанки в хаскельной куче.
>
> Проблема не в положении данных, а в том, что Text имеет тот же формат, что
> и ByteString, и тем самым не позволяет освободить чанк, если на него есть
> ссылки. А подстроки это ссылки. Тип памяти влияет, но в данном случае
> это не должно быть заметно.

Есть такой код

addVal hash line = case Text.words line of
key : val : _ -> Map.insert key val hash
_ -> hash

Если line нигде больше не используется, этого достаточно чтобы GC
собрал куски строчки не пересекающиеся с key или с val?
Если да, то зачем тогда что-то копировать (cache aware выравнивания в
расчёт не берём)?

[Alexander V Vershilov]

Здравствуйте.

Не достаточно, т.к. words создает срезы строки, т.е. key и val ссылаются на
ту же строку, что была подана на вход и таким образом препятствуют её
удалению.

--
Alexander

[Maxim Taldykin]

17 июня 2014 г., 12:49 пользователь Alexander V Vershilov
<alexander...@gmail.com> написал:

key и val не содержат никаких ссылок на куски текста (chunks), не
содержащие байтов из key или val.
Проблема в том, что сам chunk может быть размером до 16Kb (почему-то
мне казалось, что до 1Kb), т.е. для маленьких долгоживущих строчек
всегда имеет смысл делать copy.

[Alexander V Vershilov]

Здравствуйте.

2014-06-17 16:10 GMT+04:00 Maxim Taldykin <jor...@gmail.com>:
> 17 июня 2014 г., 12:49 пользователь Alexander V Vershilov
> <alexander...@gmail.com> написал:
>> Здравствуйте.
>>
>> 2014-06-17 12:21 GMT+04:00 Maxim Taldykin <jor...@gmail.com>:
>>>>>> Однако стоит заметить, что и с Text Вам понадобиться copy.
>>>>>
>>>>> Зачем? У них же чанки в хаскельной куче.
>>>>
>>>> Проблема не в положении данных, а в том, что Text имеет тот же формат, что
>>>> и ByteString, и тем самым не позволяет освободить чанк, если на него есть
>>>> ссылки. А подстроки это ссылки. Тип памяти влияет, но в данном случае
>>>> это не должно быть заметно.
>>>
>>> Есть такой код
>>>
>>> addVal hash line = case Text.words line of
>>> key : val : _ -> Map.insert key val hash
>>> _ -> hash
>>>
>>> Если line нигде больше не используется, этого достаточно чтобы GC
>>> собрал куски строчки не пересекающиеся с key или с val?
>>> Если да, то зачем тогда что-то копировать (cache aware выравнивания в
>>> расчёт не берём)?
>>
>> Не достаточно, т.к. words создает срезы строки, т.е. key и val ссылаются на
>> ту же строку, что была подана на вход и таким образом препятствуют её
>> удалению.
>
> key и val не содержат никаких ссылок на куски текста (chunks), не
> содержащие байтов из key или val.

Я не понимаю, что это значит.

Давайте, я попробую переформулировать, у нас есть тип Text:

data Text = Text !Array !Int !Int

Поле !Array у key и val тоже самое, что и у line, это значит, что эти данные не
будут оствобождены до тех пор пока key и val не освободжены. copy создает
новый Array и таким образом позволяет освободить line, т.к. ссылок больше нет.

> Проблема в том, что сам chunk может быть размером до 16Kb (почему-то
> мне казалось, что до 1Kb), т.е. для маленьких долгоживущих строчек
> всегда имеет смысл делать copy.

Если речь про Text.Lazy - да. Так же вполне возможно, что при копировании
хорошо бы сразу делать Text строгим.

> --
> Вы получили это сообщение, поскольку подписаны на группу Русский Haskell.
>
> Чтобы отменить подписку на эту группу и больше не получать от нее сообщения, отправьте письмо на электронный адрес haskell-russi...@googlegroups.com.
> Чтобы добавлять сообщения в эту группу, отправьте письмо по адресу haskell...@googlegroups.com.

> Просмотреть это обсуждение в Сети можно по адресу https://groups.google.com/d/msgid/haskell-russian/CABxyK-%3D%2BoXit1sAhyy4uotG8oyKznHyJukmN5wf_QG-o_Dgt5Q%40mail.gmail.com.

[Maxim Taldykin]

17 июня 2014 г., 16:22 пользователь Alexander V Vershilov

Я немножко потерял нить дискуссии. Давайте попробуем подытожить:
- если вырезать два символа из строки, то, в худшем случае, в памяти
останутся висеть два массива по 16Кб, остальные части строки будут
доступны для сборки;
- исходный мой вопрос "зачем copy, если и так всё уберётся?",
очевидно, не имеет смысла. Я исходил из того, что чанки гораздо меньше
и обрезками можно пренебречь.

[Alexander V Vershilov]

Здравствуйте, Максим.

Если вырезать 2 символа из строки, то в памяти останется висеть тот чанк,
из которого они вырезаны: для Text.Lazy это (16кб), для ByteString.Lazy это
(32 кб) (хотя тут могу соврать), для строгих Text и ByteString это вся строка.

> - исходный мой вопрос "зачем copy, если и так всё уберётся?",
> очевидно, не имеет смысла. Я исходил из того, что чанки гораздо меньше
> и обрезками можно пренебречь.

Ага.

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

Если я правильно понял, то для коротних строк Text может 128б памяти, но
это появилось сравнительно недавно и мне нужно заново смотреть реализацию


--
Alexander

[Alexander V Vershilov]

На самом деле все немного сложнее. И даже использование copy может не помогать,
причина заключается в и использовании pinned memory, т.к. GC не может освободить
весь блок памяти, если там есть pinned объекты [1]. Поэтому при
неудачном стечении
обстоятельств copy может позволять освободить ByteString, но
выделенная память не
будет освободжена.

Этот эффект можно увидеть на профилировочном графике.

Решение: использовать unpinned память для данных, это или ByteStringShort из
последних версий пакета bytestring, или Text. Например версия [2]
работает в 4-5 раза
быстрее версии на питоне и потребляет сравнимое (в 1.3 раза больше) количество
памяти.

По поводу чисто Text версии, для меня оказалось несколько неожиданным
такой провал,
однако стоит помнить, что Data.Text предназначен для прямой работы с
IO в том и только
том случае если идёт работа с кодировками, в остальных случаях для IO интерфейса
используется ByteString и потом строка декодируется в текст. (см.
комментарий Performance
в Data.Text.Lazy.IO). Я так же отправлю более адекватную версию кода
(работает в 4 раза
быстрее текущей, но в 10 раз медленнее bytestring версии).

Хочется заметить, что код использует класс типов Traversable и поэтому его можно
полуавтоматически распараллелить используя странегии (пакет parallel),
если кому интересно,
то я могу скинуть код и результаты.



[1] https://ghc.haskell.org/trac/ghc/wiki/Commentary/Rts/Storage/GC/Pinned
[2] https://github.com/tonal/fat_ip/pull/1/files

> --
> Вы получили это сообщение, поскольку подписаны на группу Русский Haskell.
>
> Чтобы отменить подписку на эту группу и больше не получать от нее сообщения, отправьте письмо на электронный адрес haskell-russi...@googlegroups.com.
> Чтобы добавлять сообщения в эту группу, отправьте письмо по адресу haskell...@googlegroups.com.

> Просмотреть это обсуждение в Сети можно по адресу https://groups.google.com/d/msgid/haskell-russian/CABxyK-mZ3heaeXR5kOmeSDNvwrrBm1gssXOSPWMDQPq4nZXwMQ%40mail.gmail.com.

[Maxim Taldykin]

Спасибо, познавательно.

18 июня 2014 г., 0:59 пользователь Alexander V Vershilov

> Просмотреть это обсуждение в Сети можно по адресу https://groups.google.com/d/msgid/haskell-russian/CAO-1Pb5JZu9FHOK4yYKMB0rn%3DHkz7DoQqLKUFcc0chhX2_mSeA%40mail.gmail.com.

[Александр Замараев]

Огромное спасибо за проделанную работу и разяснения.
Влил оба изменения.

Теперь показатели следующие:

 * fat_ip_bs.hs - <4 сек. ~15мб.

 * fat_ip_text.hs - <30 сек. ~600мб

Хотя сейчас обе они используют и ByteString и Text, так что большого смысла во втором нет, как мне кажется. :)

К тому же больше чем на порядок возросло потребление памяти (~40 раз)

Есть небольшой вопрос по коду:

В обоих случаях используется unionsWith для объединения результатов по каждому логу.

Почему не сконкотинировать результат lines или line2item как было у меня?

Это как-то завязано на скорость/память или тлько на потенциальную парралельность?

И да, хотелось бы увидеть вариант с параллельностью или просто пример как её туда вставить. :)

П. С. [В порядке брюзжания] В часто ругаемом сегодня С++ есть такая тема, что каждая крупная библиотека/фреймворк содержит свой класс строк и подсистему ввода-вывода. И если в проекте используется несколько таких библиотек, то начинаются постоянные конвертации, что не улучшает читаемость и сопровождаемость.
Причём, т. к. в любой С++ программе доступны как минимум libc, STL, IOStream, а на винде ещё и WinApi то этот бардак можно обнаружить даже в самых простых исходниках...

По факту в haskell-platform сейчас как минимум 3 библиотеки работы со строками со своим вводом/выводом. Причём в двух из них по 2 типа строк и в ByteString ожидается прибавление. Итого 6 разных типов строк и 5 разных систем В/В.

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

Вот это я и имел в виду, когда писал об «аккуратной» реализации соответствующих механизмов Python-а.

среда, 18 июня 2014 г., 3:59:14 UTC+7 пользователь Alexander (qnikst) Vershilov написал:

[Alexander V Vershilov]

Здравствуйте, Александр.

2014-06-18 12:43 GMT+04:00 Александр Замараев <tonal.p...@gmail.com>:
> Огромное спасибо за проделанную работу и разяснения.
> Влил оба изменения.
> Теперь показатели следующие:
> * fat_ip_bs.hs - <4 сек. ~15мб.
> * fat_ip_text.hs - <30 сек. ~600мб
> Хотя сейчас обе они используют и ByteString и Text, так что большого смысла
> во втором нет, как мне кажется. :)
> К тому же больше чем на порядок возросло потребление памяти (~40 раз)

Интересно, у меня Text показывал более адекватное потребление памяти. Но
действительно большого смысла в нём нет. Кстати, тут подсказали идею, что
IP адрес это 4байтный Int, поэтому гораздо выгоднее его парсить как
Int и хранить
в IntMap.Strict/Map.Strict, а при выводе распаковывать обратно.

> Есть небольшой вопрос по коду:
> В обоих случаях используется unionsWith для объединения результатов по
> каждому логу.
> Почему не сконкотинировать результат lines или line2item как было у меня?
> Это как-то завязано на скорость/память или тлько на потенциальную
> парралельность?

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

> И да, хотелось бы увидеть вариант с параллельностью или просто пример как её
> туда вставить. :)

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

> П. С. [В порядке брюзжания] В часто ругаемом сегодня С++ есть такая тема,
> что каждая крупная библиотека/фреймворк содержит свой класс строк и
> подсистему ввода-вывода. И если в проекте используется несколько таких
> библиотек, то начинаются постоянные конвертации, что не улучшает читаемость
> и сопровождаемость.
> Причём, т. к. в любой С++ программе доступны как минимум libc, STL,
> IOStream, а на винде ещё и WinApi то этот бардак можно обнаружить даже в
> самых простых исходниках...
>
> По факту в haskell-platform сейчас как минимум 3 библиотеки работы со
> строками со своим вводом/выводом. Причём в двух из них по 2 типа строк и в
> ByteString ожидается прибавление. Итого 6 разных типов строк и 5 разных
> систем В/В.
> Причём как выясняется не удастся ограничится только одним каким-то, ежели
> важны скорость и память. Нужно хорошо понимать особенности каждого типа,
> чтобы добится приемлемых результатов.
> Вот это я и имел в виду, когда писал об «аккуратной» реализации
> соответствующих механизмов Python-а.

Ну в haskell есть 2 типа строк:

String - внутренний и неэффективный

Text - более эффективный и умеющий оптимизации при малых размерах
(+ ленивый вариант)

Есть тип для бинарных данных и FFI:

ByteString

Есть тип, который можно использовать как строки:

Vector с кучей вариантов


Соответвенно правила простые: если используется внутри программы и без FFI,
то использовать по возможности Text, в части случаев это сделать сложно, т.к.
используемые библиотеки умеют только String, но ситуация в последние годы
меняется.

Если нужна работа с FFI, то или промежуточное представление в
ByteString / CString
или сразу с ними и работать.

Если IO - то ByteString. (Исключением может быть работа с терминалом, где важна
локаль).

Причины этого простые: разные задачи требуют разные свойства и каждая из
библиотек нацелена на решение определенной задачи эффективым способом. Итого
есть tradeoff между простой изучения и эффективностью решения (жалко я не могу
найти интересные слайды Brian O'Salivan как раз на тему Text и Fusion
и сравнении с питоном).
К сожалению, к этому накладывается историческое наследие в виде String, который
часто используется не по назначению и действительно портит картину.

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

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

> Чтобы отправлять сообщения в эту группу, отправьте письмо на электронный
> адрес haskell...@googlegroups.com.
> Чтобы посмотреть обсуждение на веб-странице, перейдите по ссылке

> https://groups.google.com/d/msgid/haskell-russian/cdd10252-701c-4c72-9ddb-5d0a7da31673%40googlegroups.com.

[Maksim Kulagin]

Привет,

Эти слайды?

Bryan O’Sullivan - Fast Code Nation

http://bos.github.io/reaktor-dev-day-2012/reaktor-talk-slides.html

/Максим

Просмотреть это обсуждение в Сети можно по адресу https://groups.google.com/d/msgid/haskell-russian/CAO-1Pb7e0_CpaMHLG19ws67dEqbYvBUobNcLBC_YBTS2d_WfVA%40mail.gmail.com.

[Alexander V Vershilov]

Очень похожи, но вроде не то.

> https://groups.google.com/d/msgid/haskell-russian/CAH5okkAePvv7UUpk1pcEQg1efDZWfyHMr-Mbr3gxRrSO4itXSg%40mail.gmail.com.