Why does the strictness flag make memory usage increase?

Question

The following two programs differ only by the strictness flag on variable st

$ cat testStrictL.hs

module Main (main) where

import qualified Data.Vector as V
import qualified Data.Vector.Generic as GV
import qualified Data.Vector.Mutable as MV

len = 5000000

testL = do
  mv <- MV.new len
  let go i = do
          if i >= len then return () else
             do  let st = show (i+10000000)  -- no strictness flag
                 MV.write mv i st
                 go (i+1)
  go 0
  v <- GV.unsafeFreeze mv :: IO (V.Vector String)
  return v

main =
  do
     v <- testL
     print (V.length v)
     mapM_ print $ V.toList $ V.slice 4000000 5 v

$ cat testStrictS.hs

module Main (main) where

import qualified Data.Vector as V
import qualified Data.Vector.Generic as GV
import qualified Data.Vector.Mutable as MV

len = 5000000

testS = do
  mv <- MV.new len
  let go i = do
          if i >= len then return () else
             do  let !st = show (i+10000000)  -- this has the strictness flag
                 MV.write mv i st
                 go (i+1)
  go 0
  v <- GV.unsafeFreeze mv :: IO (V.Vector String)
  return v

main =
  do
     v <- testS
     print (V.length v)
     mapM_ print $ V.toList $ V.slice 4000000 5 v

Compiling and running these two programs on Ubuntu 10.10 with ghc 7.03 I get the following results

$ ghc --make testStrictL.hs -O3 -rtsopts  
[2 of 2] Compiling Main             ( testStrictL.hs, testStrictL.o )  
Linking testStrictL ...  
$ ghc --make testStrictS.hs -O3 -rtsopts  
[2 of 2] Compiling Main             ( testStrictS.hs, testStrictS.o )  
Linking testStrictS ...  
$ ./testStrictS +RTS -sstderr  
./testStrictS +RTS -sstderr  
5000000  
"14000000"  
"14000001"  
"14000002"  
"14000003"  
"14000004"  
     824,145,164 bytes allocated in the heap  
   1,531,590,312 bytes copied during GC  
     349,989,148 bytes maximum residency (6 sample(s))  
       1,464,492 bytes maximum slop  
             656 MB total memory in use (0 MB lost due to fragmentation)  

  Generation 0:  1526 collections,     0 parallel,  5.96s,  6.04s elapsed  
  Generation 1:     6 collections,     0 parallel,  2.79s,  4.36s elapsed  

  INIT  time    0.00s  (  0.00s elapsed)  
  MUT   time    1.77s  (  2.64s elapsed)  
  GC    time    8.76s  ( 10.40s elapsed)  
  EXIT  time    0.00s  (  0.13s elapsed)  
  Total time   10.52s  ( 13.04s elapsed)  

  %GC time      83.2%  (79.8% elapsed)  

  Alloc rate    466,113,027 bytes per MUT second  

  Productivity  16.8% of total user, 13.6% of total elapsed  

$ ./testStrictL +RTS -sstderr  
./testStrictL +RTS -sstderr  
5000000  
"14000000"  
"14000001"  
"14000002"  
"14000003"  
"14000004"  
      81,091,372 bytes allocated in the heap  
     143,799,376 bytes copied during GC  
      44,653,636 bytes maximum residency (3 sample(s))  
       1,005,516 bytes maximum slop  
              79 MB total memory in use (0 MB lost due to fragmentation)  

  Generation 0:   112 collections,     0 parallel,  0.54s,  0.59s elapsed  
  Generation 1:     3 collections,     0 parallel,  0.41s,  0.45s elapsed  

  INIT  time    0.00s  (  0.03s elapsed)  
  MUT   time    0.12s  (  0.18s elapsed)  
  GC    time    0.95s  (  1.04s elapsed)  
  EXIT  time    0.00s  (  0.06s elapsed)  
  Total time    1.06s  (  1.24s elapsed)  

  %GC time      89.1%  (83.3% elapsed)  

  Alloc rate    699,015,343 bytes per MUT second  

  Productivity  10.9% of total user, 9.3% of total elapsed

Could someone please explain why the strictness flag seems to cause the program to use so much memory? This simple example came about from my attempts to understand why my programs use so much memory when reading large files of 5 million lines and creating vectors of records.

Strictness constrains the order of execution - that's its whole point. This limits the optimisers options. Not an answer because my Haskell-fu isn't strong enough to say exactly what is going on, but my guess would be that strictness is preventing an optimisation that allows memory to be more efficiently re-used within the go tail-recursive loop. — Steve314
If you're using a recent version of GHC, you might try specifying that the LLVM back-end should be used rather than the original GHC back-end. This probably doesn't affect the highest-level optimisation decisions, but it will select a completely different optimiser for the low-level generated code. — Steve314

hvr hvr · Accepted Answer · 2011-08-01T08:24:19

The problem here is mainly that you're using the String (which is an alias for [Char]) type which due to its representation as a non-strict list of single Chars requires 5 words per characters on the memory heap (See also this blog article for some memory footprint comparisons)

In the lazy case, you basically store an unevaluated thunk pointing to the (shared) evaluation function show . (+10000000) and a varying integer, whereas in the strict case the complete strings composed of 8 characters seem to be materialized (usually the bang-pattern would only force the outermost list-constructor :, i.e. the first character of a lazy String, to be evaluated), which requires way more heap space the longer the strings become.

Storing 5000000 String-typed strings of length 8 thus requires 5000000*8*5 = 200000000 words, which on 32-bit correspond to about ~763 MiB. If the Char digits are shared, you only need 3/5 of that, i.e. ~458 MiB, which seems to match your observed memory overhead.

If you replace your String by something more compact such as a Data.ByteString.ByteString you'll notice that the memory overhead will be about one magnitude lower compared to when using a plain String.

Why does the strictness flag make memory usage increase?

1 Answers