Geek Answers Handbook

Using a list generator for efficient memory usage in Haskell

I would like to get an idea of ​​how to write haskell code with memory efficiently. One thing that I came across is that there is no dead simple way to create python style list generators / iterators (which I could find).

A small example:

Finding the sum of integers from 1 to 100,000,000 without using the closed formulas.

Python that can be executed quickly with minimal memory usage sum(xrange(100000000). In Haskell, there will be an analog sum [1..100000000]. However, this requires a lot of memory. I thought using foldlor foldrwould be fine, but even that uses a lot of memory and is slower than python. Any suggestions?

+4
source share
1 answer

TL DR - I believe that the culprit in this case is the default of the GHC before Integer.

By all accounts, I don’t know enough about python, but I assume that python will switch to "bigint" only if necessary - so all calculations are done using Intaka 64-bit integer on my machine.

First check with

$> ghci
GHCi, version 7.10.3: http://www.haskell.org/ghc/  :? for help
Prelude> maxBound :: Int
9223372036854775807

shows that the result of the sum ( 5000000050000000) is less than this number, so we are not afraid of overflow Int.

I guessed that your sample programs look something like this.

sum.py

print(sum(xrange(100000000)))

sum.hs

main :: IO ()
main = print $ sum [1..100000000]

To make things explicit, I added a type annotation (100000000 :: Integer), compiling it with

$ > stack build --ghc-options="-O2 -with-rtsopts=-sstderr"

and executed your example,

$ > stack exec -- time sum
5000000050000000
   3,200,051,872 bytes allocated in the heap
         208,896 bytes copied during GC
          44,312 bytes maximum residency (2 sample(s))
          21,224 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

                                     Tot time (elapsed)  Avg pause  Max pause
  Gen  0      6102 colls,     0 par    0.013s   0.012s     0.0000s    0.0000s
  Gen  1         2 colls,     0 par    0.000s   0.000s     0.0001s    0.0001s

  INIT    time    0.000s  (  0.000s elapsed)
  MUT     time    1.725s  (  1.724s elapsed)
  GC      time    0.013s  (  0.012s elapsed)
  EXIT    time    0.000s  (  0.000s elapsed)
  Total   time    1.739s  (  1.736s elapsed)

  %GC     time       0.7%  (0.7% elapsed)

  Alloc rate    1,855,603,449 bytes per MUT second

  Productivity  99.3% of total user, 99.4% of total elapsed

1.72user 0.00system 0:01.73elapsed 99%CPU (0avgtext+0avgdata 4112maxresident)k

and actually ~ 3 GB of memory is playing.

(100000000 :: Int) -

$ > stack build
$ > stack exec -- time sum
5000000050000000
          51,872 bytes allocated in the heap
           3,408 bytes copied during GC
          44,312 bytes maximum residency (1 sample(s))
          17,128 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

                                     Tot time (elapsed)  Avg pause  Max pause
  Gen  0         0 colls,     0 par    0.000s   0.000s     0.0000s    0.0000s
  Gen  1         1 colls,     0 par    0.000s   0.000s     0.0001s    0.0001s

  INIT    time    0.000s  (  0.000s elapsed)
  MUT     time    0.034s  (  0.034s elapsed)
  GC      time    0.000s  (  0.000s elapsed)
  EXIT    time    0.000s  (  0.000s elapsed)
  Total   time    0.036s  (  0.035s elapsed)

  %GC     time       0.2%  (0.2% elapsed)

  Alloc rate    1,514,680 bytes per MUT second

  Productivity  99.4% of total user, 102.3% of total elapsed

0.03user 0.00system 0:00.03elapsed 91%CPU (0avgtext+0avgdata 3496maxresident)k
0inputs+0outputs (0major+176minor)pagefaults 0swaps

haskell , conduit vector ( ).

sumC.hs

import Data.Conduit
import Data.Conduit.List as CL

main :: IO ()
main = do res <- CL.enumFromTo 1 100000000 $$ CL.fold (+) (0 :: Int)
          print res

sumV.hs

import           Data.Vector.Unboxed as V
{-import           Data.Vector as V-}

main :: IO ()
main = print $ V.sum $ V.enumFromTo (1::Int) 100000000

,

main = print $ V.sum $ V.enumFromN (1::Int) 100000000

, - .

enumFromN :: (Unbox a, Num a) => a -> Int -> Vector a

O (n) , x, x + 1 .. , enumFromTo.

Update

@Carsten - integer - well integer-simple, , Integer integer-gmp integer-gmp2 libgmp.

data Integer = Positive !Positive | Negative !Positive | Naught

-------------------------------------------------------------------
-- The hard work is done on positive numbers

-- Least significant bit is first

-- Positive have the property that they contain at least one Bit,
-- and their last Bit is One.
type Positive = Digits
type Positives = List Positive

data Digits = Some !Digit !Digits
            | None
type Digit = Word#

data List a = Nil | Cons a (List a)

Integer Int , , unboxed Int# - , ( ).

Integer ( )

  • 1 x Word sum-type ( Positive
  • n x (Word + Word) Some Digit
  • 1 x Word None

(2 + (log_10 (n)) Integer + .

+6

More articles:


All Articles