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

Question

module Has (r,p,s) where

import Prelude ((==),Bool(..),otherwise,(||),Eq)
import qualified Data.List as L

filter :: (a -> Bool) -> [a] -> [a]
filter _pred []    = []
filter pred (x:xs)
  | pred x         = x : filter pred xs
  | otherwise      = filter pred xs

проблема1: это filter копируется из GHCбиблиотека, но почему она потребляет все больше памяти в отличие от импортируемых напрямую filter, который потребляет постоянное количество памяти.

elem :: (Eq a) => a -> [a] -> Bool
elem _ []       = False
elem x (y:ys)   = x==y || elem x ys

проблема2: это filter копируется из GHCбиблиотека, но почему она потребляет все больше памяти, как непосредственно используемая elem, который также потребляет все больше памяти в отличие от напрямую импортируемых filter,

r = L.filter (==1000000000000) [0..]
p = filter (==1000000000000) [0..]
s = 1000000000000 `elem` [0..]

Версия GHC:7.4.2 ОС:Ubuntu 12.10 Скомпилирована с -O2 для оптимизации

Как указано выше filter а также elem определения подразумевают оба p = filter (==1000000000000) [0..] а также s = 1000000000000 `elem` [0..] "s [0..] мусор должен собираться постепенно. Но оба p а также s потребляет все больше памяти. А также r который определяется непосредственно импортированным filter потребляет постоянное количество памяти.

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

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

Спасибо за ваше чтение.

Answer 1

Причиной потребления памяти в ghci является не код filter или же elem, (Хотя правило перезаписи для filter в GHC.List обычно немного лучше.)

Давайте посмотрим на (часть) ядра ghc-7.4.2, созданного с -O2 (-ddump-simpl). Сначала для r, с помощью GHC.List.filter:

Has.r1
  :: GHC.Integer.Type.Integer
     -> [GHC.Integer.Type.Integer] -> [GHC.Integer.Type.Integer]
[GblId,
 Arity=2,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=2, Value=True,
         ConLike=True, Cheap=True, Expandable=True,
         Guidance=IF_ARGS [0 0] 60 30}]
Has.r1 =
  \ (x_awu :: GHC.Integer.Type.Integer)
    (r2_awv :: [GHC.Integer.Type.Integer]) ->
    case GHC.Integer.Type.eqInteger x_awu Has.p5 of _ {
      GHC.Types.False -> r2_awv;
      GHC.Types.True ->
        GHC.Types.: @ GHC.Integer.Type.Integer x_awu r2_awv
    }

Has.r :: [GHC.Integer.Type.Integer]
[GblId,
 Str=DmdType,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=False,
         ConLike=False, Cheap=False, Expandable=False,
         Guidance=IF_ARGS [] 40 0}]
Has.r =
  GHC.Enum.enumDeltaIntegerFB
    @ [GHC.Integer.Type.Integer] Has.r1 Has.p3 Has.p2

Has.p3 является 0 :: Integer, а также Has.p2 является 1 :: Integer, Правила переписывания (для filter а также enumDeltaInteger) превратил его в (с более короткими именами)

r = go fun 0 1
  where
    go foo x d = x `seq` (x `foo` (go foo (x+d) d))

fun n list
    | n == 1000000000000 = n : list
    | otherwise          = list

что, вероятно, может быть немного более эффективным, если fun был встроен, но дело в том, что список будет filterЭд не существует как таковой, он был расплавлен.

За p с другой стороны, без правил перезаписи мы получаем

Has.p1 :: [GHC.Integer.Type.Integer]
[GblId,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=False,
         ConLike=False, Cheap=False, Expandable=False,
         Guidance=IF_ARGS [] 30 0}]
Has.p1 = GHC.Enum.enumDeltaInteger Has.p3 Has.p2

Has.p :: [GHC.Integer.Type.Integer]
[GblId,
 Str=DmdType,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=False,
         ConLike=False, Cheap=False, Expandable=False,
         Guidance=IF_ARGS [] 30 0}]
Has.p = Has.filter @ GHC.Integer.Type.Integer Has.p4 Has.p1

CAF верхнего уровня для списка [0 .. ] (Has.p1), а также Has.filter применительно к (== 1000000000000) и список.

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

Но обычно (при запуске скомпилированного бинарного файла) это не проблема с точки зрения потребления памяти, так как список мусора собирается по мере его использования. Однако по причинам, которые мне не известны, ghci сохраняет список [0 .. ] вокруг при оценке p или же s (но это имеет свою собственную копию [0 .. ]так что это не нежелательный обмен здесь), что можно почерпнуть из -hT профиль кучи (оценивающий sтак что есть только один возможный источник для ячеек списка. GHCI вызывается с +RTS -M300M -hT -RTS, так что вскоре после того, как использование памяти достигло 300M, ghci прекратил работу):

Таким образом, причиной потребления памяти в ghci является жесткое кодирование списка, подлежащего фильтрации. Если вы используете Has.filter со списком, предоставленным в приглашении, использование памяти остается постоянным, как и ожидалось.

Я не уверен, сохранил ли ghci список [0 .. ] это ошибка или предполагаемое поведение.