Wie verarbeitet man zwei lange Zeilen mit konstantem Speicher?

Question

Eingabedatei besteht aus zwei Linien, von denen jeder viele Zahlen

1 2 3 4... 
5 6 7 8... 

ich die Daten jeder Zeile hält bearbeiten wollen, wie folgt aus:

doSomething :: [Int] -> [Int] -> Int 
doSomething [] y = 0 -- stop execution. I'm concerted in memory behavior only. 
doSomething (x:xs) y = doSomething xs y 
main = do 
    inputdata <- getContents 
    let (x:xs) = lines inputdata 
     firstLine = map (read ::String->Int) $ words $ x 
     secondLine = map (read ::String->Int) $ words $ head xs 
    print $ doSomething firstLine secondLine 

Als ich dieses Programm ausführen, zeigt Haufen Profilierung wie dies:

Wenn ich secondLine (xs) nicht verwende, dann läuft dieses Programm mit konstantem Speicher. Jeder Eintrag der Liste firstLine wird verarbeitet und dann von GC verworfen.

1. Warum die verbrauchte Speicher ist so groß? Ich sehe die Menge des zugewiesenen Speichers ist ~ 100 MB, aber die tatsächliche Eingangsdatengröße ist 5 MB.

2. Erzwingt head xs Lesen der gesamten ersten Zeile in den Speicher, sogar secondLine wird überhaupt nicht verwendet? Und ist dies die Hauptursache Speichererhöhung von Heap Profiling Graphen?

3. Wie kann ich zwei Zeilen mit konstantem Speicher verarbeiten, wie das letzte Ausführungsdiagramm?

4. Wenn die Antwort auf 3) hängt von der Reihenfolge der Verarbeitung ab, wie kann ich die zweite Zeile zuerst und dann die erste Zeile verarbeiten?

Answer 1

Q1) Warum die verbrauchte Speicher so groß ist? Ich sehe die Menge des zugewiesenen Speichers ist ~ 100 MB, aber die tatsächliche Eingangsdatengröße beträgt 5 MB.

String in Haskell ist eine Art Alias ​​für [Char], also entlang des tatsächlichen Bytes, auch der Compiler einen Konstruktor zu halten hat, einen Zeiger auf den geschachtelte Charakter und einen Zeiger auf den nächsten Konstruktor für jedes Zeichen in dem Speicher , Ergebnisse> 10 Mal Speicherbelegung als eine Zeichenfolge im C-Stil. Noch schlimmer, der Text wird mehrfach im Speicher gespeichert.

Q3) Wie kann ich zwei Zeilen mit konstantem Speicher verarbeiten, wie das letzte Ausführungsdiagramm?
Q4) Wenn die Antwort auf Q3) von der Reihenfolge der Verarbeitung abhängt, wie kann ich zuerst die zweite Zeile und dann die erste Zeile verarbeiten?

Nein, Sie können nicht die zweite Zeile zuerst verarbeiten, da die lines Funktion jedes Byte in der ersten Zeile zu bewerten haben die ‚\ n‘ Newline-Zeichen zu schlagen.

Q2) Erzwingt Kopf xs das Lesen der gesamten ersten Zeile in den Speicher, selbst SecondLine wird überhaupt nicht verwendet? Und ist dies der Hauptgrund für die Speichererhöhung des Heap-Profiling-Graphen?

Es ist nicht die head, die verhindert, dass die erste Zeile GCed wird. Das Speicherleck tritt weiterhin auf, wenn Sie die Typensignatur doSomething anpassen und xs direkt an es übergeben.Der Punkt ist der (nicht optimierende) Compiler wird nicht wissen, dass secondLine nicht verwendet wird, bevor doSomething schließlich das erste Muster trifft, so dass das Programm einen Verweis auf xs behält. BTW, wenn mit -O2 kompiliert, läuft Ihr Programm mit konstantem Speicher.

Was den Raum Leck des Programms verursacht wird, in erster Linie diese Linie:

let (x:xs) = lines inputdata 

Wenn entweder x oder xs verworfen wird, diese Klausel in der Core Dump in ausgekleideten lassen wird. Nur wenn beide später referenziert werden, verhält sich der Core merkwürdig: Er konstruiert ein Tupel, zerstört es durch Mustervergleich, baut dann die beiden Teile wieder zu einem Tupel zusammen, daher behält das Programm unter Bezugnahme auf secondLine tatsächlich einen Verweis auf a Tuple (x, xs) so wird die erste Zeile nie GCed sein.

Kern mit secondLine kommentiert out:

Rec { 
doSomething_rjH 
doSomething_rjH = 
    \ ds_d1lv y_alG -> 
    case ds_d1lv of _ { 
     [] -> I# 0; 
     : x_alH xs_alI -> doSomething_rjH xs_alI y_alG 
    } 
end Rec } 

main 
main = 
    >>= 
    $fMonadIO 
    getContents 
    (\ inputdata_app -> 
     print 
     $fShowInt 
     (doSomething_rjH 
      (map 
       (read $fReadInt) 
       (words 
        (case lines inputdata_app of _ { 
        [] -> case irrefutPatError "a.hs:6:9-32|(x : xs)"# of wild1_00 { }; 
        : x_auf xs_aug -> x_auf 
        }))) 
      ([]))) 

main 
main = runMainIO main 

Kern mit Platz Leck:

Rec { 
doSomething_rjH 
doSomething_rjH = 
    \ ds_d1ol y_alG -> 
    case ds_d1ol of _ { 
     [] -> I# 0; 
     : x_alH xs_alI -> doSomething_rjH xs_alI y_alG 
    } 
end Rec } 

main 
main = 
    >>= 
    $fMonadIO 
    getContents 
    (\ inputdata_app -> 
     -- *** Construct *** 
     let { 
     ds_d1op 
     ds_d1op = 
      case lines inputdata_app of _ { 
      [] -> irrefutPatError "a.hs:6:9-30|x : xs"#; 
      : x_awM xs_awN -> (x_awM, xs_awN) 
      } } in 
     -- *** Destruct *** 
     let { 
     xs_awN 
     xs_awN = case ds_d1op of _ { (x_awM, xs1_XwZ) -> xs1_XwZ } } in 
     let { 
     x_awM 
     x_awM = case ds_d1op of _ { (x1_XwZ, xs1_XwU) -> x1_XwZ } } in 
     -- *** Construct *** 
     let { 
     ds1_d1oq 
     ds1_d1oq = (x_awM, xs_awN) } in 
     print 
     $fShowInt 
     -- *** Destruct *** 
     (doSomething_rjH 
      (map 
       (read $fReadInt) 
       (words (case ds1_d1oq of _ { (x1_Xx1, xs1_Xx3) -> x1_Xx1 }))) 
      (map 
       (read $fReadInt) 
       (words 
        (head (case ds1_d1oq of _ { (x1_Xx1, xs1_Xx3) -> xs1_Xx3 })))))) 

main 
main = runMainIO main 

Ersetzen Sie die let Klausel durch eine case .. of Klausel wird den Raum Leck beheben:

doSomething :: [Int] -> [Int] -> Int 
doSomething [] _ = 0 -- stop execution. I'm concerted in memory behavior only. 
doSomething (_:xs) y = doSomething xs y 

main :: IO() 
main = do 
    inputdata <- getContents 
    case lines inputdata of 
    x:xs -> do 
     let 
     firstLine = map (read ::String->Int) $ words x 
     secondLine = map (read ::String->Int) $ words $ head xs 
     print $ doSomething firstLine secondLine 

Der entkernte Core. Die „Konstrukt dann Destruct“ Muster diesmal nicht passieren:

Rec { 
doSomething_rjG 
doSomething_rjG = 
    \ ds_d1o6 ds1_d1o7 -> 
    case ds_d1o6 of _ { 
     [] -> I# 0; 
     : ds2_d1o8 xs_alG -> doSomething_rjG xs_alG ds1_d1o7 
    } 
end Rec } 

main 
main = 
    >>= 
    $fMonadIO 
    getContents 
    (\ inputdata_apn -> 
     case lines inputdata_apn of _ { 
     [] -> patError "a.hs:(8,3)-(13,46)|case"#; 
     : x_asI xs_asJ -> 
      print 
      $fShowInt 
      (doSomething_rjG 
       (map (read $fReadInt) (words x_asI)) 
       (map (read $fReadInt) (words (head xs_asJ)))) 
     }) 

main 
main = runMainIO main