STUArray s i e - space leak solo quando i == Int?

Question

Sono confuso dal comportamento dei seguenti snipped:

import Data.Int 
import Data.Array.ST 
import Control.Monad.ST 

{-# INLINE fib #-} 
fib _ 0 = return 0 
fib _ 1 = return 1 
fib c n = do 
    f1 <- memo c (fib c) (n-1) 
    f2 <- memo c (fib c) (n-2) 
    return (f1+f2) 

newtype C a = C a 

{-# INLINE memo #-} 
memo (C a) f k = do 
    e <- readArray a k 
    if e == (-1) 
    then do 
     v <- f k 
     writeArray a k v 
     return v 
    else return e 

evalFib :: Int -> Int 
evalFib n = runST $ do 
    a <- newArray (0,n) (-1) :: ST s (STUArray s Int Int) 
    fib (C a) n 

main = print $ evalFib 120000 

quando si compila con -O2 esso Pila-overflow (che mostrano 20M di memoria in uso). La parte confusa è che effettivamente funziona come previsto (senza overflow dello stack e memoria 9M in uso) se è fatto qualsiasi delle seguenti modifiche:

• Int64 è usato al posto di Int: (dando evalFib :: Int64 -> Int e STUArray s Int64 Int) . In effetti qualsiasi Int* (Int32, Int16, ecc.) Eseguirà il trucco, nonché Word o Word*;
• newtype C a rimosso dall'immagine;
• data C a = C !a è usato al posto di newtype

Sto cercando di ottenere la mia testa intorno a questo comportamento: si tratta di un bug nel modulo GHC/array (che mostra un comportamento identico a 7.4.2 e 7.6.2) o è dovuto funziona in questo modo?

PS La cosa divertente è che quando provo a compilarlo con ghc array.hs -O2 -fext-core per vedere le differenze nel core prodotto entrambe le versioni di GHC falliscono con "ghc: panic! (L''impossibile' è successo)". Nessuna fortuna nemmeno qui ..

Answer 1

Guardando il nucleo dal 7.6.1, con -O2 e -dsuppress-uniques, la funzione che fa il lavoro, Main.main_$spoly_$wa strutturalmente (quasi) identica sia che uso int o Int64 come tipo di indice. Dato che il nucleo è lunga e complessa, ecco la diff uscita:

$ diff Int_core.dump-simpl Int64_core.dump-simpl 
11,12c11,12 
<   (Data.Array.Base.STUArray s GHC.Types.Int GHC.Types.Int) 
<   (Main.C (Data.Array.Base.STUArray s GHC.Types.Int GHC.Types.Int)) 
--- 
>   (Data.Array.Base.STUArray s GHC.Int.Int64 GHC.Types.Int) 
>   (Main.C (Data.Array.Base.STUArray s GHC.Int.Int64 GHC.Types.Int)) 
26,27c26,27 
<    (Data.Array.Base.STUArray s GHC.Types.Int GHC.Types.Int) 
<    (Main.C (Data.Array.Base.STUArray s GHC.Types.Int GHC.Types.Int))) 
--- 
>    (Data.Array.Base.STUArray s GHC.Int.Int64 GHC.Types.Int) 
>    (Main.C (Data.Array.Base.STUArray s GHC.Int.Int64 GHC.Types.Int))) 

Diversi tipi di indice, questi sono ovviamente differenti.

33,40d32 
<   l :: GHC.Types.Int 
<   [LclId] 
<   l = GHC.Types.I# sc } in 
<   let { 
<   u :: GHC.Types.Int 
<   [LclId] 
<   u = GHC.Types.I# sc1 } in 
<   let { 

Per indice tipo Int, GHC produce errori alquanto più informativi per indici fuori dal campo, per cui necessita il limite inferiore e superiore degli indici validi. (L'implementazione predefinita di index non viene sostituito nel instance Ix Int64.)

45,46c37 
<   GHC.Types.False -> 
<    case poly_$w$j5 (GHC.Types.I# a) l u of wild2 { }; 
--- 
>   GHC.Types.False -> case GHC.Arr.hopelessIndexError of wild1 { }; 

errore diverso, indexError vs. hopelessIndexError. Le seguenti differenze riguardano anche solo gli errori di indice.

49,50c40 
<    GHC.Types.False -> 
<     case poly_$w$j5 (GHC.Types.I# a) l u of wild2 { }; 
--- 
>    GHC.Types.False -> case GHC.Arr.hopelessIndexError of wild2 { }; 
58c48 
<      case poly_$w$j4 y (GHC.Types.I# sc2) of wild3 { }; 
--- 
>      case poly_$w$j3 y (GHC.Types.I# sc2) of wild4 { }; 
62c52 
<       case poly_$w$j4 y (GHC.Types.I# sc2) of wild5 { }; 
--- 
>       case poly_$w$j3 y (GHC.Types.I# sc2) of wild5 { }; 
77,78c67 
<         GHC.Types.False -> 
<         case poly_$w$j3 (GHC.Types.I# a1) l u of wild6 { }; 
--- 
>         GHC.Types.False -> case GHC.Arr.hopelessIndexError of wild6 { }; 
81,82c70 
<          GHC.Types.False -> 
<          case poly_$w$j3 (GHC.Types.I# a1) l u of wild7 { }; 
--- 
>          GHC.Types.False -> case GHC.Arr.hopelessIndexError of wild7 { }; 

Ora, una volta di più il diverso tipo di indice:

110c98 
<                  GHC.Types.Int 
--- 
>                  GHC.Int.Int64 
152c140 
<             s GHC.Types.Int GHC.Types.Int>)>) 
--- 
>             s GHC.Int.Int64 GHC.Types.Int>)>) 

E, infine, 0 e 1 hanno ottenuto diversi nomi di primo livello.

177,178c165,166 
<  0 -> (# sc5, lvl5 #); 
<  1 -> (# sc5, lvl6 #) 
--- 
>  0 -> (# sc5, lvl #); 
>  1 -> (# sc5, lvl1 #) 

Quindi l'intero codice che esegue il lavoro effettivo è identico. Eppure quello causa uno stack overflow (anche se solo, -K9M è sufficiente [-K8731K è sufficiente qui, -K8730K non]) e l'altro no.

La differenza è effettivamente causata dagli errori dell'indice. Il codice con Int indici alloca due scatolati Int s in ogni chiamata ricorsiva che il codice Int64 non alloca, perché

Main.main_$spoly_$wa [Occ=LoopBreaker] 
    :: forall s. 
    GHC.Prim.Int# 
    -> GHC.Prim.Int# 
    -> GHC.Prim.Int# 
    -> GHC.Prim.MutableByteArray# s 
    -> (GHC.Prim.~#) 
      * 
      (Data.Array.Base.STUArray s GHC.Types.Int GHC.Types.Int) 
      (Main.C (Data.Array.Base.STUArray s GHC.Types.Int GHC.Types.Int)) 
    -> GHC.Prim.Int# 
    -> GHC.Prim.State# s 
    -> (# GHC.Prim.State# s, GHC.Types.Int #) 

porta vicino due riferimenti alla matrice.

Questo utilizza più stack, e questi boxing Int s devono essere raccolti con garbage collection, il che causa cifre GC molto più grandi. Inoltre, il thunk per l'errore di indice è un po 'più grande del thunk hopelessIndexError.

Ora, se aiutare il compilatore da

• rimuovere l'involucro newtype
• rendendo la funzione rigorosa nella matrice (da modelli Bang o data C a = C !a)

o qualche altro modo, produce un codice migliore che gestisce senza un overflow di stack per l'argomento specificato, dal momento che c'è solo un riferimento all'array nel worker, e quindi l'allocazione del boxed Int s per i limiti non è necessario.

Si noti che questo algoritmo causa uno stack overflow per argomenti leggermente più grandi anche con l'aiuto del compilatore.

Answer 2

tuo programma iniziale, come dici tu, stack overflow:

$ ghc -O2 A.hs --make -rtsopts 
$ ./A +RTS -s 
Stack space overflow: current size 8388608 bytes. 
Use `+RTS -Ksize -RTS' to increase it. 
     21,213,928 bytes allocated in the heap 
     3,121,864 bytes copied during GC 
     5,400,592 bytes maximum residency (4 sample(s)) 
      20,464 bytes maximum slop 
       20 MB total memory in use (0 MB lost due to fragmentation) 

Mentre se cambiamo ad Int64 funziona benissimo:

$ time ./A 
-2092835058118682368 
./A 0.03s user 0.01s system 92% cpu 0.050 total 

Allora, dov'è la perdita?

Basta ispezionare visivamente il codice, c'è un problema evidente:

• fib è pigro nel suo argomento di matrice

Si può anche dedurre questo dal comportamento che avete visto:

newtype C a is removed from the picture; 

data C a = C !a is used instead of newtype 

Tutti i server per esporre l'array all'analizzatore di rigidità.

Se si effettua fib rigorosa nella matrice:

{-# LANGUAGE BangPatterns #-} 

{-# INLINE fib #-} 
fib !_ 0 = return 0 
fib !_ 1 = return 1 
fib !c n = do 
    f1 <- memo c (fib c) (n-1) 
    f2 <- memo c (fib c) (n-2) 
    return (f1+f2) 

allora funziona solo:

$ time ./A 
-2092835058118682368 
./A 0.03s user 0.01s system 89% cpu 0.052 total 

Allora perché lo fa fuoriuscire con un solo tipo, ma non un altro? Sei appena diventato fortunato con Int64, penso. Ma considererei questo un "bug", probabilmente nelle regole di riscrittura per i vari tipi di numeri.

Guardando l'output del semplificatore, otteniamo una serie piuttosto diversa di regole di riscrittura che si attivano nel caso Int64 rispetto al caso Int.Poiché le funzioni sottostanti sono spesso indicizzate da Int, finisci per esercitare diverse ottimizzazioni usando il tipo Int comune. In questo caso, sufficiente per confondere l'analizzatore di rigidità.

Come sempre, si applicano le regole generali: dare al compilatore più suggerimenti e ottenere un codice migliore.