Tại sao chức năng nhập khẩu trực tiếp trong GHC khác nhau rất nhiều với chức năng tôi viết với mã nguồn sao chép từ GHC Libraries

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 

problem1: filter này được sao chép từ thư viện GHC 's, nhưng tại sao nó tiêu thụ một số lượng ngày càng tăng của bộ nhớ trong tương phản với nhập trực tiếp filter, tiêu thụ số lượng bộ nhớ không đổi.

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

problem2: filter này được sao chép từ thư viện GHC 's, nhưng tại sao nó tiêu thụ một số lượng ngày càng tăng của bộ nhớ như trực tiếp sử dụng elem, mà cũng tiêu thụ một số lượng ngày càng tăng của bộ nhớ trái ngược với nhập trực tiếp filter.

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

GHC phiên bản: 7.4.2 Hệ điều hành: Ubuntu 12.10 Biên soạn với -O2 để tối ưu hóa

Như trên filter và elem 'định nghĩa của hàm ý cả p = filter (==1000000000000) [0..] và s = 1000000000000 `elem` [0..]' s [0..] nên được thu gom rác thải dần. Nhưng cả hai p và s tiêu thụ một số lượng ngày càng tăng của bộ nhớ. Và r được xác định bằng nhập trực tiếp filter tiêu thụ một số lượng bộ nhớ không đổi.

Câu hỏi của tôi là lý do tại sao các hàm được nhập trực tiếp trong GHC khác nhau rất nhiều với các hàm tôi viết bằng mã nguồn được sao chép từ Thư viện GHC. Tôi tự hỏi liệu có gì sai với GHC?

Tôi có thêm một câu hỏi: Đoạn mã trên được tóm tắt từ một dự án mà tôi đã viết, và dự án cũng phải đối mặt với vấn đề "tiêu thụ số lượng bộ nhớ ngày càng tăng, mà phải được thu thập trong lý thuyết". Vì vậy, tôi muốn biết rằng có một cách để tìm biến nào chiếm nhiều bộ nhớ trong GHC.

Cảm ơn bạn đã đọc.

Answer 1

Nguyên nhân tiêu thụ bộ nhớ trong ghci không phải là mã số filter hoặc elem. (Mặc dù quy tắc ghi lại cho filter trong GHC.List thường xuyên hơn một chút.)

Hãy xem (một phần) lõi ghc-7.4.2 được tạo ra với -O2 (-ddump-simpl). Đầu tiên cho r, sử dụng 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 là 0 :: Integer, và Has.p2 là 1 :: Integer. Các quy tắc viết lại (ví filter và enumDeltaInteger) biến nó thành (với những cái tên ngắn hơn)

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 

mà có lẽ có thể là một chút hiệu quả hơn nếu fun được sắp xếp theo hàng nhưng vấn đề là danh sách để được filter ed doesn' t tồn tại như vậy, nó đã được hợp nhất.

Đối p mặt khác, mà không cần viết lại quy tắc (s), chúng tôi nhận

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 

một CAF top-level cho danh sách [0 .. ] (Has.p1), và Has.filter áp dụng cho (== 1000000000000) và danh sách.

Vì vậy, công cụ này sẽ tạo danh sách thực tế được lọc - do đó nó kém hiệu quả hơn.

Nhưng thông thường (chạy một tệp nhị phân đã biên dịch), không có vấn đề gì về mức tiêu thụ bộ nhớ, vì danh sách là rác được thu thập khi nó được tiêu thụ. Tuy nhiên, vì lý do vượt quá tôi, ghci giữ danh sách [0 .. ] xung quanh khi đánh giá p hoặc s (nhưng có bản sao riêng của [0 .. ], vì vậy nó không được chia sẻ không mong muốn ở đây), có thể được thu thập từ hồ sơ heap -hT (đánh giá . s, vì vậy chỉ có một nguồn có thể cho các tế bào danh sách ghci gọi với +RTS -M300M -hT -RTS, vì vậy ngay sau khi sử dụng bộ nhớ đạt 300M, ghci chấm dứt):

vì vậy, nguyên nhân của việc tiêu thụ bộ nhớ trong ghci là mã hóa cứng của danh sách được lọc. Nếu bạn sử dụng Has.filter với danh sách được cung cấp tại dấu nhắc, mức sử dụng bộ nhớ không thay đổi như mong đợi.

Tôi không chắc liệu ghci giữ lại danh sách [0 .. ] là lỗi hay hành vi dự định.