Haskell에서 수수께끼의 메모리 동작

Question

하스켈리스트와 어레이의 성능을 비교하려고 시도하고 이상한 행동을합니다. 배열을 만든 다음 인쇄 할 때 'x'MB의 메모리가 필요하지만 'elems'함수를 사용하여 배열을 목록으로 변환 한 다음 'x'보다 작은 메모리를 사용하면 인쇄가됩니다. 'elems'함수가 배열에서 새 목록을 작성하지 않아도됩니까? 목록을 만들지 않는 함수보다 더 많은 공간을 가져야하지 않습니까? -O2 및 -fspec-constr 최적화 플래그를 사용하고 있습니다. 나는 또한 함수를 프로파일 링하기 위해 -p 플래그를 사용하고있다. 사전에

이 중간 목록 코드입니다

fun n = runST $ do 
     final_soln <- newArray_ ((1,1), (n, (10^n))) :: ST s ((STUArray s) (Int,Int) Int) 
     U.unsafeFreeze final_soln 

main = do 
    [n] <- getArgs 
    {-# SCC "file-writing" #-} (writeFile "cprod-starray-creation.txt" $ show $ fun (read n)) 

이 중간 목록에없는 코드입니다

,

fun :: Int -> UArray (Int,Int) Int 
fun n = runST $ do 
     final_soln <- newArray_ ((1,1), (n, (10^n))) :: ST s ((STUArray s) (Int,Int) Int) 
     U.unsafeFreeze final_soln 

main = do 
    [n] <- getArgs 
    {-# SCC "file-writing" #-} (writeFile "cprod-starray-creation.txt" $ show $ elems $ fun (read n)) 

감사 lazyness의 부족은에있다

Answer 1

첫 번째 변종이며, 귀하의 잘못이 아닙니다.

이 결과 동안,

첫 번째 코드의 프로파일 출력된다 : 파라메터 (6) 런의 프로파일 출력 (+RTS -hd)을 비교하는 제 힌트를 제공 두 번째 코드. 배열 자체 (ARR_WORDS)는 둘 다 동일한 공간을 사용합니다. 또한 첫 번째 코드는 Int 생성자 (Int#이라는 이름을 가진)의 큰 목록 (: 생성자가 인식 할 수 있음)을 생성한다는 것을 알 수 있습니다.

이제 최종 문자열 (인쇄물로 Char, 생성자가 C#)이 될 수 없습니다. 배열에 0을 포함하고 있기 때문에 가비지 컬렉터에 할당 된 (또는 실제로는 [-16,16]) 범위의 작은 Int (작은 범위)의 캐시가 있으므로 배열의 요소 목록이 될 수 없습니다. 새로운 생성자를 복사하는 대신).

: 생성자의 경우 약 24MB, I# 생성자의 경우 16MB가 필요합니다. 전자가 3 단어와 후자 2 단어를 필요로하고 내 컴퓨터에서 한 단어가 8 바이트 길이라는 것을 알면 목록은 100000 = 10^6 요소입니다. 따라서 매우 좋은 후보는 두 번째 인덱스 매개 변수의 범위입니다.

그래서이 배열은 어디에 있습니까? 우리가 show에 전화를 추적하자

showsIArray :: (IArray a e, Ix i, Show i, Show e) => Int -> a i e -> ShowS 
showsIArray p a = 
    showParen (p > 9) $ 
    showString "array " . 
    shows (bounds a) . 
    showChar ' ' . 
    shows (assocs a) 

(Data.Array.Base에서 코드). 우리가 인덱스의 목록을 찾고 있기 때문에

assocs :: (IArray a e, Ix i) => a i e -> [(i, e)] 
assocs arr = case bounds arr of 
    (l,u) -> [(i, arr ! i) | i <- range (l,u)] 

의 range 호출이 충분히 의심스러운 : 분명히, 범인은 그래서 여기에 대한 소스는 assocs 호출에 있어야합니다.

instance (Ix a, Ix b) => Ix (a, b) where 
    range ((l1,l2),(u1,u2)) = [ (i1,i2) | i1 <- range (l1,u1), i2 <- range (l2,u2) ] 

그리고 지금 우리가 범인을 발견 : 그 동안 우리가 (불행하게도 엉망 대구의 일종) GHC.Arr의 원인으로보고있다 여기에, range (l2,u2) 목록 [1..1000000] 및 로 평가됩니다 모든 단계에 대한 공유 색인의 첫 번째 구성 요소에서.

지금 나는 당신이 두 번째 코드에 assocs 대신 elems을 넣어 위해 노력하고, 거기에 공간 누수 기대에 호기심이있을 것 같아요. 그러나 당신은 그것을 보지 못할 것입니다. 그 이유는 show이 인라인되지는 않지만 assocs 자체가 인라인 된 다음 range을 포함한 다른 많은 기능이 효과적으로 공유되지 않기 때문입니다. 당신은 GHC에 -ddump-rule-firings를 전달하여 그 (다소) 볼 수 있습니다

$ ghc --make -O2 -fspec-constr -ddump-rule-firings -fforce-recomp code2.hs -prof -fprof-auto 
[1 of 1] Compiling Main    (code2.hs, code2.o) 
Rule fired: SPEC GHC.Arr.$fIx(,) 
Rule fired: unpack 
Rule fired: Class op fail 
Rule fired: unpack 
Rule fired: Class op show 
Rule fired: Class op newArray_ 
Rule fired: unsafeFreeze/STUArray 
Rule fired: Class op >>= 
Rule fired: Class op >>= 
Rule fired: Class op showList 
Rule fired: Class op rangeSize 
Rule fired: Class op rangeSize 
Rule fired: Class op bounds 
Rule fired: Class op bounds 
Rule fired: Class op numElements 
Rule fired: Class op index 
Rule fired: Class op unsafeAt 
Rule fired: Class op range 
Rule fired: fold/build 
Rule fired: SPEC GHC.Real.^ 
Rule fired: unpack-list 
Rule fired: foldr/app 
Rule fired: unpack-append 
Rule fired: foldr/app 
Rule fired: unpack-append 
Rule fired: ># 
Rule fired: ># 
Rule fired: x# <=# x# 
Rule fired: x# -# x# 
Rule fired: 0# *# x# 
Rule fired: 0# +# x# 
Linking code2 ...