How to process two long lines with constant memory?

Question

Input file consists of two lines, each of which holds many numbers

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

I want to process each line's data, like this:

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

When I run this program, heap profiling shows like this:

If I don't use secondLine (xs) then this program runs with constant memory. Each entry of list firstLine is processed then discarded by GC.

1. Why the consumed memory is so large? I see the amount of allocated memory is ~100MB, but actual input data size is 5MB.

2. Does head xs force reading entire first line into memory, even secondLine is not used at all? And is this the main cause of memory increase of heap profiling graph?

3. How can I process two lines with constant memory, like latter execution graph?

4. If the answer to 3) depends on processing order, how can I process second line first, and then first line?

Answer 1

Q1) Why the consumed memory is so large? I see the amount of allocated memory is ~100MB, but actual input data size is 5MB.

String in Haskell is a type alias for [Char], so along the actual bytes, the compiler also has to keep a constructor, a pointer to the boxed character and a pointer to the next constructor for every character in the memory, results >10 times of memory usage than a C-style string. Even worse the text is stored multiple times in memory.

Q3) How can I process two lines with constant memory, like latter execution graph?
Q4) If the answer to Q3) depends on processing order, how can I process second line first, and then first line?

No you can't process the second line first since the lines function have to evaluate every byte in the first line to hit the '\n' newline character.

Q2) Does head xs force reading entire first line into memory, even secondLine is not used at all? And is this the main cause of memory increase of heap profiling graph?

It's not the head that prevents the first line from being GCed. The space leak still occurs if you adjust the type signature of doSomething and pass xs directly to it. The point is the (not optimizing) compiler won't know that secondLine isn't used before doSomething finally hits the first pattern, so the program keeps a reference to xs . BTW if compiled with -O2 your program runs with constant memory.

What caused the space leak of your program is mainly this line:

let (x:xs) = lines inputdata

When either x or xs is discarded, this let clause will be in-lined in the dumped Core. Only when both of them are referenced later the Core behaves strangely: it constructs a tuple, destruct it by pattern matching, then construct the two part into a tuple again, therefore by keeping a reference to secondLine the program in fact keeps a reference to a tuple (x, xs) so the first line will never be GCed.

Core with secondLine commented 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

Core with space leak:

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

Replace the let clause by a case .. of clause will fix the space leak:

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

The dumped Core. The "construct then destruct" pattern didn't happen this time:

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