Анализ производительности сгиба с использованием ключей map и ByteString - PullRequest
2 голосов
/ 23 июня 2011

У меня есть небольшой скрипт для чтения, анализа и получения какой-то интересной (не совсем) статистики из файла журнала apache. Пока что я выбрал два простых варианта: общее количество байтов, отправленных во всех запросах в файле журнала, и 10 самых распространенных IP-адресов.

Первый «режим» - это просто простая сумма всех проанализированных байтов. Второй - это сгиб по карте (Data.Map), использующий insertWith (+) 1' для подсчета вхождений.

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

42 359 709 344 байта, выделенных в куча 72,405,840 байт скопировано во время GC Максимальная резидентность 113 712 байт (1553 выборок) 145 872 байт, максимальный спад 2 МБ общей используемой памяти (0 МБ потеряно из-за фрагментации)

Поколение 0: 76311 коллекций,
0 параллель, 0,89 с, 0,99 с прошло
Поколение 1: 1553 коллекций, 0 параллельно, 0,21 с, 0,22 с

Время INIT 0.00s (0.00s истекшее время MUT 21,76с ( Прошло 24,82 с) Время GC 1,10 с (прошло 1,20 с) Время выхода
0,00 с (прошедшие 0,00 с) Общее время 22,87 с (прошедшие 26,02 с)

% GC время 4,8% (4,6% прошло)

Скорость выделения 1,946,258,962 байта в секунду MUT

Производительность 95,2% от общего числа пользователей, 83,6% от общего времени прошло

Однако второй нет!

49 398 834 152 байта, выделенных в куча 580 579 208 байт, скопированных во время GC Максимальная резидентность 718 385 088 байт (15 образцов) 134 532 128 байт, максимальный спад Общая используемая память 1393 МБ (172 МБ потеряно из-за фрагментации)

Поколение 0: 91275 коллекций,
0 параллель, 252,65 с, 254,46 с прошло
Поколение 1: 15 коллекций, 0 параллельно, 0,12 с, 0,12 с прошло

INIT time 0.00s (0.00s истекшее время MUT 41.11с ( 48,87 с прошло) время GC 252,77 с (прошло 254,58 с) время выхода
0,00 с (истек 0,01 с) Общее время 293,88 с (303,45 с прошло)

% время GC 86,0% (истекло 83,9%)

Скорость выделения 1,201,635,385 байт в секунду MUT

Производительность 14,0% от общего числа пользователей, 13,5% от общего количества прошедших

А вот и код.

{-# LANGUAGE OverloadedStrings #-}

module Main where

import qualified Data.Attoparsec.Lazy as AL
import Data.Attoparsec.Char8 hiding (space, take)
import qualified Data.ByteString.Char8 as S
import qualified Data.ByteString.Lazy.Char8 as L
import Control.Monad (liftM)
import System.Environment (getArgs)
import Prelude hiding (takeWhile)
import qualified Data.Map as M
import Data.List (foldl', sortBy)
import Text.Printf (printf)
import Data.Maybe (fromMaybe)

type Command = String

data LogLine = LogLine {
    getIP     :: S.ByteString,
    getIdent  :: S.ByteString,
    getUser   :: S.ByteString,
    getDate   :: S.ByteString,
    getReq    :: S.ByteString,
    getStatus :: S.ByteString,
    getBytes  :: S.ByteString,
    getPath   :: S.ByteString,
    getUA     :: S.ByteString
} deriving (Ord, Show, Eq)

quote, lbrack, rbrack, space :: Parser Char
quote  = satisfy (== '\"')
lbrack = satisfy (== '[')
rbrack = satisfy (== ']')
space  = satisfy (== ' ')

quotedVal :: Parser S.ByteString
quotedVal = do
    quote
    res <- takeTill (== '\"')
    quote
    return res

bracketedVal :: Parser S.ByteString
bracketedVal = do
    lbrack
    res <- takeTill (== ']')
    rbrack
    return res

val :: Parser S.ByteString
val = takeTill (== ' ')

line :: Parser LogLine
l    ine = do
    ip <- val
    space
    identity <- val
    space
    user <- val
    space
    date <- bracketedVal
    space
    req <- quotedVal
    space
    status <- val
    space
    bytes <- val
    (path,ua) <- option ("","") combined
    return $ LogLine ip identity user date req status bytes path ua

combined :: Parser (S.ByteString,S.ByteString)
combined = do
    space
    path <- quotedVal
    space
    ua <- quotedVal
    return (path,ua)

countBytes :: [L.ByteString] -> Int
countBytes = foldl' count 0
    where
        count acc l = case AL.maybeResult $ AL.parse line l of
            Just x  -> (acc +) . maybe 0 fst . S.readInt . getBytes $ x
            Nothing -> acc

countIPs :: [L.ByteString] -> M.Map S.ByteString Int
countIPs = foldl' count M.empty
    where
        count acc l = case AL.maybeResult $ AL.parse line l of
            Just x -> M.insertWith' (+) (getIP x) 1 acc
            Nothing -> acc

---------------------------------------------------------------------------------

main :: IO ()
main = do
  [cmd,path] <- getArgs
  dispatch cmd path

pretty :: Show a => Int -> (a, Int) -> String
pretty i (bs, n) = printf "%d: %s, %d" i (show bs) n

dispatch :: Command -> FilePath -> IO ()
dispatch cmd path = action path
    where
        action = fromMaybe err (lookup cmd actions)
        err    = printf "Error: %s is not a valid command." cmd

actions :: [(Command, FilePath -> IO ())]
actions = [("bytes", countTotalBytes)
          ,("ips",  topListIP)]

countTotalBytes :: FilePath -> IO ()
countTotalBytes path = print . countBytes . L.lines =<< L.readFile path

topListIP :: FilePath -> IO ()
topListIP path = do
    f <- liftM L.lines $ L.readFile path
    let mostPopular (_,a) (_,b) = compare b a
        m = countIPs f
    mapM_ putStrLn . zipWith pretty [1..] . take 10 . sortBy mostPopular . M.toList $ m

Edit:

Добавление + RTS -A16M снижает ГХ до 20%. Использование памяти, конечно, без изменений.

Ответы [ 2 ]

3 голосов
/ 23 июня 2011

Я предлагаю внести следующие изменения в код:

@@ -1,4 +1,4 @@
-{-# LANGUAGE OverloadedStrings #-}
+{-# LANGUAGE BangPatterns, OverloadedStrings #-}

 module Main where

@@ -9,7 +9,7 @@
 import Control.Monad (liftM)
 import System.Environment (getArgs)
 import Prelude hiding (takeWhile)
-import qualified Data.Map as M
+import qualified Data.HashMap.Strict as M
 import Data.List (foldl', sortBy)
 import Text.Printf (printf)
 import Data.Maybe (fromMaybe)
@@ -17,15 +17,15 @@
 type Command = String

 data LogLine = LogLine {
-    getIP     :: S.ByteString,
-    getIdent  :: S.ByteString,
-    getUser   :: S.ByteString,
-    getDate   :: S.ByteString,
-    getReq    :: S.ByteString,
-    getStatus :: S.ByteString,
-    getBytes  :: S.ByteString,
-    getPath   :: S.ByteString,
-    getUA     :: S.ByteString
+    getIP     :: !S.ByteString,
+    getIdent  :: !S.ByteString,
+    getUser   :: !S.ByteString,
+    getDate   :: !S.ByteString,
+    getReq    :: !S.ByteString,
+    getStatus :: !S.ByteString,
+    getBytes  :: !S.ByteString,
+    getPath   :: !S.ByteString,
+    getUA     :: !S.ByteString
 } deriving (Ord, Show, Eq)

 quote, lbrack, rbrack, space :: Parser Char
@@ -39,14 +39,14 @@
     quote
     res <- takeTill (== '\"')
     quote
-    return res
+    return $! res

 bracketedVal :: Parser S.ByteString
 bracketedVal = do
     lbrack
     res <- takeTill (== ']')
     rbrack
-    return res
+    return $! res

 val :: Parser S.ByteString
 val = takeTill (== ' ')
@@ -67,14 +67,14 @@
     space
     bytes <- val
     (path,ua) <- option ("","") combined
-    return $ LogLine ip identity user date req status bytes path ua
+    return $! LogLine ip identity user date req status bytes path ua

 combined :: Parser (S.ByteString,S.ByteString)
 combined = do
     space
-    path <- quotedVal
+    !path <- quotedVal
     space
-    ua <- quotedVal
+    !ua <- quotedVal
     return (path,ua)

 countBytes :: [L.ByteString] -> Int
@@ -84,11 +84,11 @@
             Just x  -> (acc +) . maybe 0 fst . S.readInt . getBytes $ x
             Nothing -> acc

-countIPs :: [L.ByteString] -> M.Map S.ByteString Int
+countIPs :: [L.ByteString] -> M.HashMap S.ByteString Int
 countIPs = foldl' count M.empty
     where
         count acc l = case AL.maybeResult $ AL.parse line l of
-            Just x -> M.insertWith' (+) (getIP x) 1 acc
+            Just x -> M.insertWith (+) (getIP x) 1 acc
             Nothing -> acc

 ---------------------------------------------------------------------------------

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

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

Наконец, я переключился на лучшую структуру данных HashMap из пакета unordered-container .Обратите внимание, что все функции в Data.HashMap.Strict имеют строгое значение, что означает, что мы можем использовать простой вариант insertWith.

Обратите внимание, что взятие подстроки ByteString заставляет исходную строку быть сохраненной впамяти, из-за совместного использования основного хранилища (это то же самое, что и для Java String).Если вы хотите убедиться, что дополнительная память не сохраняется, используйте функцию copy из пакета bytestring.Вы можете попробовать позвонить copy по результату (getIP x) и посмотреть, будет ли это иметь значение.Компромисс здесь заключается в использовании дополнительных вычислений для копирования строки в обмен на более низкое использование пространства.

Обратите внимание, что использование -A<high number> имеет тенденцию повышать производительность краткосрочных программ (т.е. тестов производительности), но не обязательно на реальныхпрограммы.То же самое касается -H.По крайней мере, более высокое значение -H (например, 1G) не влияет на производительность вашей программы.

0 голосов
/ 23 июня 2011

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

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

Я бы с подозрением воспринимал вызовы Data.Map.insertWith, поскольку каждый из них отрисовывает кусок существующего излишка Карты в соответствии с требованиями и требует копирования и перебалансировки, но с моей стороны это просто догадки. Если виноваты вызовы insertWith, то, поскольку вам не нужны промежуточные записи Map, может быть быстрее, чтобы построить всю карту за один проход (без каких-либо приращений для подсчета IP-адресов), а затем выполнить второй проход, чтобы сделать счет. Таким образом, вы не будете тратить время на перебалансировку Карты. Вы также можете воспользоваться тем фактом, что ваш тип данных ключа вписывается в Int (ну, если он, по крайней мере, если это IPv4-адрес), и использовать вместо него Data.IntMap, который имеет намного меньшую нагрузку на память.

...