Incremental array updates

Daniel Kraft

26 Feb 2009 26 Feb '09

8:53 a.m.

Hi, I seem to be a little stuck with incremental array updates... I've got an array of "few" (some thousand) integers, but have to do a calculation where I incrementally build up the array. For sake of simplicity, for now I don't use a State-Monad but simply pass the array as state down the recursive calls. Unfortunatelly, I seem to experience problems with lazyness; when I run my program, memory usage goes up to horrific values! The simple program below reproduces this; when run on my machine, it uses up about 300 MB of real and 300 MB of virtual memory, and the system starts swapping like mad! I compiled with ghc --make -O3, ghc version 6.8.3 if that matters. BTW, I tried to make the array update strict using the `seq` as below, but with no effect... What am I doing wrong here? Many thanks, Daniel import Data.Array; arraySize = 1000 limit = 100000 type MyArray = Array Int Int emptyArray :: MyArray emptyArray = array (0, arraySize - 1) [ (i, 0) | i <- [0 .. arraySize - 1] ] procOne :: Int -> MyArray -> MyArray procOne a cnt | a > limit = cnt | otherwise = let ind = a `mod` arraySize oldcnt = cnt ! ind newarr = cnt // [(ind, oldcnt + 1)] in procOne (a + 1) (newarr `seq` newarr) main :: IO () main = do arr <- return $ procOne 0 emptyArray print $ arr ! 42

Show replies by date

Eugene Kirpichov

26 Feb 26 Feb

8:56 a.m.

You need to use STUArray. The Data.Array completely-immutable-and-boxed arrays are ok only for tasks where you build an array once and don't modify it, and where you need array elements to be lazy. The // operation creates a copy of the whole array with one element modified. It should probably be called "turtleSlowCopyWholeArrayAndModifySingleElement". 2009/2/26 Daniel Kraft :

...

Hi,

I seem to be a little stuck with incremental array updates... I've got an array of "few" (some thousand) integers, but have to do a calculation where I incrementally build up the array. For sake of simplicity, for now I don't use a State-Monad but simply pass the array as state down the recursive calls.

Unfortunatelly, I seem to experience problems with lazyness; when I run my program, memory usage goes up to horrific values! The simple program below reproduces this; when run on my machine, it uses up about 300 MB of real and 300 MB of virtual memory, and the system starts swapping like mad! I compiled with ghc --make -O3, ghc version 6.8.3 if that matters.

BTW, I tried to make the array update strict using the `seq` as below, but with no effect... What am I doing wrong here?

Many thanks, Daniel

import Data.Array;

arraySize = 1000 limit = 100000

type MyArray = Array Int Int

emptyArray :: MyArray emptyArray = array (0, arraySize - 1) [ (i, 0) | i <- [0 .. arraySize - 1] ]

procOne :: Int -> MyArray -> MyArray procOne a cnt | a > limit = cnt | otherwise = let ind = a `mod` arraySize oldcnt = cnt ! ind newarr = cnt // [(ind, oldcnt + 1)] in procOne (a + 1) (newarr `seq` newarr)

main :: IO () main = do arr <- return $ procOne 0 emptyArray print $ arr ! 42

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Eugene Kirpichov Web IR developer, market.yandex.ru

Daniel Kraft

9:12 a.m.

Eugene Kirpichov wrote:

...

You need to use STUArray. The Data.Array completely-immutable-and-boxed arrays are ok only for tasks where you build an array once and don't modify it, and where you need array elements to be lazy. The // operation creates a copy of the whole array with one element modified. It should probably be called "turtleSlowCopyWholeArrayAndModifySingleElement".

Thanks for the hint! However, I still don't see why this increments memory usage so much... Shouldn't even in this case the garbage collector remove the old, no longer needed versions of the array? My main point of concern is not that the program may run slowly, but that it uses that much memory. But of course for the real program this hint is surely very useful! I'll give it a try... Thanks, Daniel

...

2009/2/26 Daniel Kraft :

...
Hi,

I seem to be a little stuck with incremental array updates... I've got an array of "few" (some thousand) integers, but have to do a calculation where I incrementally build up the array. For sake of simplicity, for now I don't use a State-Monad but simply pass the array as state down the recursive calls.

Unfortunatelly, I seem to experience problems with lazyness; when I run my program, memory usage goes up to horrific values! The simple program below reproduces this; when run on my machine, it uses up about 300 MB of real and 300 MB of virtual memory, and the system starts swapping like mad! I compiled with ghc --make -O3, ghc version 6.8.3 if that matters.

BTW, I tried to make the array update strict using the `seq` as below, but with no effect... What am I doing wrong here?

Many thanks, Daniel

import Data.Array;

arraySize = 1000 limit = 100000

type MyArray = Array Int Int

emptyArray :: MyArray emptyArray = array (0, arraySize - 1) [ (i, 0) | i <- [0 .. arraySize - 1] ]

procOne :: Int -> MyArray -> MyArray procOne a cnt | a > limit = cnt | otherwise = let ind = a `mod` arraySize oldcnt = cnt ! ind newarr = cnt // [(ind, oldcnt + 1)] in procOne (a + 1) (newarr `seq` newarr)

main :: IO () main = do arr <- return $ procOne 0 emptyArray print $ arr ! 42

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Luke Palmer

9:07 a.m.

On Thu, Feb 26, 2009 at 6:53 AM, Daniel Kraft wrote:

...

procOne (a + 1) (newarr `seq` newarr)

The semantics of seq are: a `seq` b = _|_ if a = _|_, b otherwise. This implies that x `seq` x = x, and this seq is superfluous. Maybe you meant newarr `seq` procOne (a+1) newarr ? Luke

Sjur Gjøstein Karevoll

9:17 a.m.

On Thursday 26 February 2009 15.07.34 Luke Palmer wrote:

...

On Thu, Feb 26, 2009 at 6:53 AM, Daniel Kraft wrote:

...
procOne (a + 1) (newarr `seq` newarr)

The semantics of seq are: a `seq` b = _|_ if a = _|_, b otherwise. This implies that x `seq` x = x, and this seq is superfluous.

Maybe you meant newarr `seq` procOne (a+1) newarr ?

Luke

I just tested that, and both that and the original used about 500mb of memory. I changed it to "(newarr ! ind) `seq` procOne (a+1) newarr" and it only used about 15mb. -- Sjur Gjøstein Karevoll sjurberengal@gmail.com

Daniel Fischer

9:17 a.m.

Am Donnerstag, 26. Februar 2009 14:53 schrieb Daniel Kraft:

...

Hi,

I seem to be a little stuck with incremental array updates... I've got an array of "few" (some thousand) integers, but have to do a calculation where I incrementally build up the array. For sake of simplicity, for now I don't use a State-Monad but simply pass the array as state down the recursive calls.

Unfortunatelly, I seem to experience problems with lazyness; when I run my program, memory usage goes up to horrific values! The simple program below reproduces this; when run on my machine, it uses up about 300 MB of real and 300 MB of virtual memory, and the system starts swapping like mad! I compiled with ghc --make -O3, ghc version 6.8.3 if that matters.

As Eugene already said, use STUArray (STArray if you need some laziness). It's much much faster.

...

BTW, I tried to make the array update strict using the `seq` as below, but with no effect... What am I doing wrong here?

Many thanks, Daniel

import Data.Array;

arraySize = 1000 limit = 100000

type MyArray = Array Int Int

emptyArray :: MyArray emptyArray = array (0, arraySize - 1) [ (i, 0) | i <- [0 .. arraySize - 1] ]

procOne :: Int -> MyArray -> MyArray procOne a cnt

| a > limit = cnt | otherwise =

let ind = a `mod` arraySize oldcnt = cnt ! ind newarr = cnt // [(ind, oldcnt + 1)] in procOne (a + 1) (newarr `seq` newarr)

Note that x `seq` x is exactly equivalent to just writing x, it will be evaluated if and only if x is required to be evaluated by something else. Try let ind = a `mod` arraySize oldcnt = cnt ! ind newarr = cnt // [(ind,oldcnt+1)] newcnt = newarr ! ind in newcnt `seq` procOne (a+1) newarr to force newarr to be evaluated, so the old array is eligible for garbage collection.

...

main :: IO () main = do arr <- return $ procOne 0 emptyArray print $ arr ! 42

Cheers, Daniel

Daniel Kraft

9:27 a.m.

Daniel Fischer wrote:

...

Am Donnerstag, 26. Februar 2009 14:53 schrieb Daniel Kraft:

...
Hi,

I seem to be a little stuck with incremental array updates... I've got an array of "few" (some thousand) integers, but have to do a calculation where I incrementally build up the array. For sake of simplicity, for now I don't use a State-Monad but simply pass the array as state down the recursive calls.

Unfortunatelly, I seem to experience problems with lazyness; when I run my program, memory usage goes up to horrific values! The simple program below reproduces this; when run on my machine, it uses up about 300 MB of real and 300 MB of virtual memory, and the system starts swapping like mad! I compiled with ghc --make -O3, ghc version 6.8.3 if that matters.

As Eugene already said, use STUArray (STArray if you need some laziness). It's much much faster.

I'm just reading about it, but didn't find anything except the Haddock documentation... This may need some time to work out :)

...

...
BTW, I tried to make the array update strict using the `seq` as below, but with no effect... What am I doing wrong here?

Many thanks, Daniel

import Data.Array;

arraySize = 1000 limit = 100000

type MyArray = Array Int Int

emptyArray :: MyArray emptyArray = array (0, arraySize - 1) [ (i, 0) | i <- [0 .. arraySize - 1] ]

procOne :: Int -> MyArray -> MyArray procOne a cnt

| a > limit = cnt | otherwise =

let ind = a `mod` arraySize oldcnt = cnt ! ind newarr = cnt // [(ind, oldcnt + 1)] in procOne (a + 1) (newarr `seq` newarr)

Note that

x `seq` x

is exactly equivalent to just writing x, it will be evaluated if and only if x is required to be evaluated by something else.

Try let ind = a `mod` arraySize oldcnt = cnt ! ind newarr = cnt // [(ind,oldcnt+1)] newcnt = newarr ! ind in newcnt `seq` procOne (a+1) newarr

to force newarr to be evaluated, so the old array is eligible for garbage collection.

This was my first attempt at using `seq` for forcing strict evaluation, and I seemingly did it wrong ;) Thanks for all the quick answers! Yours, Daniel

Eugene Kirpichov

9:32 a.m.

STUArray is really a bit tricky to get used with: especially, if you do something wrong, the type errors will be rather dreadful. However, if you do everything right, it's OK and you sometimes even don't need to write the types at all. There are a couple of examples here http://www.google.com/codesearch?q=runSTUArray I also use them a bit in http://hackage.haskell.org/cgi-bin/hackage-scripts/package/jarfind And here's one more small source where I used it: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=1791#a1791 That's problem 87 from projecteuler.net. 2009/2/26 Daniel Kraft :

...

Daniel Fischer wrote:

...
Am Donnerstag, 26. Februar 2009 14:53 schrieb Daniel Kraft:

...
Hi,

I seem to be a little stuck with incremental array updates... I've got an array of "few" (some thousand) integers, but have to do a calculation where I incrementally build up the array. For sake of simplicity, for now I don't use a State-Monad but simply pass the array as state down the recursive calls.

Unfortunatelly, I seem to experience problems with lazyness; when I run my program, memory usage goes up to horrific values! The simple program below reproduces this; when run on my machine, it uses up about 300 MB of real and 300 MB of virtual memory, and the system starts swapping like mad! I compiled with ghc --make -O3, ghc version 6.8.3 if that matters.

As Eugene already said, use STUArray (STArray if you need some laziness). It's much much faster.

I'm just reading about it, but didn't find anything except the Haddock documentation... This may need some time to work out :)

...
...
BTW, I tried to make the array update strict using the `seq` as below, but with no effect... What am I doing wrong here?

Many thanks, Daniel

import Data.Array;

arraySize = 1000 limit = 100000

type MyArray = Array Int Int

emptyArray :: MyArray emptyArray = array (0, arraySize - 1) [ (i, 0) | i <- [0 .. arraySize - 1] ]

procOne :: Int -> MyArray -> MyArray procOne a cnt

| a > limit = cnt | otherwise =

let ind = a `mod` arraySize oldcnt = cnt ! ind newarr = cnt // [(ind, oldcnt + 1)] in procOne (a + 1) (newarr `seq` newarr)

Note that x `seq` x is exactly equivalent to just writing x, it will be evaluated if and only if x is required to be evaluated by something else.

Try let ind = a `mod` arraySize oldcnt = cnt ! ind newarr = cnt // [(ind,oldcnt+1)] newcnt = newarr ! ind in newcnt `seq` procOne (a+1) newarr

to force newarr to be evaluated, so the old array is eligible for garbage collection.

This was my first attempt at using `seq` for forcing strict evaluation, and I seemingly did it wrong ;)

Thanks for all the quick answers!

Yours, Daniel

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Eugene Kirpichov Web IR developer, market.yandex.ru

Bulat Ziganshin

2:02 p.m.

New subject: Re[2]: Re: Incremental array updates

Hello Eugene, Thursday, February 26, 2009, 5:32:14 PM, you wrote: look at http://haskell.org/haskellwiki/Library/ArrayRef it contains reimplementation of arrays library according to Oleg&Simon idea: - Unboxed arrays now can be used in polymorphic functions, they are defined for every element type that belongs to the classes Unboxed and HasDefaultValue (again, look at http://www.haskell.org/pipermail/haskell-cafe/2004-July/006400.html). You can add new instances to these classes

...

STUArray is really a bit tricky to get used with: especially, if you do something wrong, the type errors will be rather dreadful. However, if you do everything right, it's OK and you sometimes even don't need to write the types at all. There are a couple of examples here http://www.google.com/codesearch?q=runSTUArray I also use them a bit in http://hackage.haskell.org/cgi-bin/hackage-scripts/package/jarfind And here's one more small source where I used it: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=1791#a1791 That's problem 87 from projecteuler.net.

...

2009/2/26 Daniel Kraft :

...
Daniel Fischer wrote:

...
Am Donnerstag, 26. Februar 2009 14:53 schrieb Daniel Kraft:

...
Hi,

I seem to be a little stuck with incremental array updates... I've got an array of "few" (some thousand) integers, but have to do a calculation where I incrementally build up the array. For sake of simplicity, for now I don't use a State-Monad but simply pass the array as state down the recursive calls.

Unfortunatelly, I seem to experience problems with lazyness; when I run my program, memory usage goes up to horrific values! The simple program below reproduces this; when run on my machine, it uses up about 300 MB of real and 300 MB of virtual memory, and the system starts swapping like mad! I compiled with ghc --make -O3, ghc version 6.8.3 if that matters.

As Eugene already said, use STUArray (STArray if you need some laziness). It's much much faster.

I'm just reading about it, but didn't find anything except the Haddock documentation... This may need some time to work out :)

...
...
BTW, I tried to make the array update strict using the `seq` as below, but with no effect... What am I doing wrong here?

Many thanks, Daniel

import Data.Array;

arraySize = 1000 limit = 100000

type MyArray = Array Int Int

emptyArray :: MyArray emptyArray = array (0, arraySize - 1) [ (i, 0) | i <- [0 .. arraySize - 1] ]

procOne :: Int -> MyArray -> MyArray procOne a cnt

| a > limit = cnt | otherwise =

let ind = a `mod` arraySize oldcnt = cnt ! ind newarr = cnt // [(ind, oldcnt + 1)] in procOne (a + 1) (newarr `seq` newarr)

Note that x `seq` x is exactly equivalent to just writing x, it will be evaluated if and only if x is required to be evaluated by something else.

Try let ind = a `mod` arraySize oldcnt = cnt ! ind newarr = cnt // [(ind,oldcnt+1)] newcnt = newarr ! ind in newcnt `seq` procOne (a+1) newarr

to force newarr to be evaluated, so the old array is eligible for garbage collection.

This was my first attempt at using `seq` for forcing strict evaluation, and I seemingly did it wrong ;)

Thanks for all the quick answers!

Yours, Daniel

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

Eugene Kirpichov

2:28 p.m.

New subject: Re[2]: Re: Incremental array updates

Hello, Thanks, I'll have a look at these. Treating unboxed stuff polymorphically is anyways very interesting and would be good to use in collections API that has been recently discussed (and which I occasionally try to continue inventing with scarce success :-/ ). 2009/2/26 Bulat Ziganshin :

...

Hello Eugene,

Thursday, February 26, 2009, 5:32:14 PM, you wrote:

look at http://haskell.org/haskellwiki/Library/ArrayRef it contains reimplementation of arrays library according to Oleg&Simon idea:

- Unboxed arrays now can be used in polymorphic functions, they are defined for every element type that belongs to the classes Unboxed and HasDefaultValue (again, look at http://www.haskell.org/pipermail/haskell-cafe/2004-July/006400.html). You can add new instances to these classes

...
STUArray is really a bit tricky to get used with: especially, if you do something wrong, the type errors will be rather dreadful. However, if you do everything right, it's OK and you sometimes even don't need to write the types at all. There are a couple of examples here http://www.google.com/codesearch?q=runSTUArray I also use them a bit in http://hackage.haskell.org/cgi-bin/hackage-scripts/package/jarfind And here's one more small source where I used it: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=1791#a1791 That's problem 87 from projecteuler.net.

...
2009/2/26 Daniel Kraft :

...
Daniel Fischer wrote:

...
Am Donnerstag, 26. Februar 2009 14:53 schrieb Daniel Kraft:

...
Hi,

I seem to be a little stuck with incremental array updates... I've got an array of "few" (some thousand) integers, but have to do a calculation where I incrementally build up the array. For sake of simplicity, for now I don't use a State-Monad but simply pass the array as state down the recursive calls.

Unfortunatelly, I seem to experience problems with lazyness; when I run my program, memory usage goes up to horrific values! The simple program below reproduces this; when run on my machine, it uses up about 300 MB of real and 300 MB of virtual memory, and the system starts swapping like mad! I compiled with ghc --make -O3, ghc version 6.8.3 if that matters.

As Eugene already said, use STUArray (STArray if you need some laziness). It's much much faster.

I'm just reading about it, but didn't find anything except the Haddock documentation... This may need some time to work out :)

...
...
BTW, I tried to make the array update strict using the `seq` as below, but with no effect... What am I doing wrong here?

Many thanks, Daniel

import Data.Array;

arraySize = 1000 limit = 100000

type MyArray = Array Int Int

emptyArray :: MyArray emptyArray = array (0, arraySize - 1) [ (i, 0) | i <- [0 .. arraySize - 1] ]

procOne :: Int -> MyArray -> MyArray procOne a cnt

| a > limit = cnt | otherwise =

let ind = a `mod` arraySize oldcnt = cnt ! ind newarr = cnt // [(ind, oldcnt + 1)] in procOne (a + 1) (newarr `seq` newarr)

Note that x `seq` x is exactly equivalent to just writing x, it will be evaluated if and only if x is required to be evaluated by something else.

Try let ind = a `mod` arraySize oldcnt = cnt ! ind newarr = cnt // [(ind,oldcnt+1)] newcnt = newarr ! ind in newcnt `seq` procOne (a+1) newarr

to force newarr to be evaluated, so the old array is eligible for garbage collection.

This was my first attempt at using `seq` for forcing strict evaluation, and I seemingly did it wrong ;)

Thanks for all the quick answers!

Yours, Daniel

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

-- Eugene Kirpichov Web IR developer, market.yandex.ru

Bulat Ziganshin

27 Feb 27 Feb

8:13 a.m.

New subject: Re[4]: Re: Incremental array updates

Hello Eugene, Thursday, February 26, 2009, 10:28:13 PM, you wrote:

...

Thanks, I'll have a look at these. Treating unboxed stuff polymorphically is anyways very interesting and would be good to use in collections API that has been recently discussed (and which I occasionally try to continue inventing with scarce success :-/ ).

does this mean that type classes from Edison and Container (Collection?) libraries are not good enough or you don't checked them? -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

Eugene Kirpichov

8:42 a.m.

New subject: Re[4]: Re: Incremental array updates

I'm exactly basing on them, but they don't have at least these things: - Monad-mutable collections like MArray - Instances of something like Assoc for arrays (arrays are collections in some sense, after all) - Treatment for unboxed types (I don't know yet, whether it is needed; but why do STUArrays have special treatment then?) It's not that I am in desperate need for these, but making the already-good collection API even better sounds like fun :) Actually, it started with me writing a monad-mutable hashtable and thinking about what its interface should be, so probably I should just upload the hashtable to hackage as is and look what comes next :) 2009/2/27 Bulat Ziganshin :

...

Hello Eugene,

Thursday, February 26, 2009, 10:28:13 PM, you wrote:

...
Thanks, I'll have a look at these. Treating unboxed stuff polymorphically is anyways very interesting and would be good to use in collections API that has been recently discussed (and which I occasionally try to continue inventing with scarce success :-/ ).

does this mean that type classes from Edison and Container (Collection?) libraries are not good enough or you don't checked them?

-- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

-- Eugene Kirpichov Web IR developer, market.yandex.ru

Bulat Ziganshin

8:47 a.m.

New subject: Re[6]: Re: Incremental array updates

Hello Eugene, Friday, February 27, 2009, 4:42:03 PM, you wrote:

...

I'm exactly basing on them, but they don't have at least these things:

"them" means Edison or Collections typeclasses?

...

- Treatment for unboxed types (I don't know yet, whether it is needed; but why do STUArrays have special treatment then?)

imho, this doesn't need its own typeclass

...

Actually, it started with me writing a monad-mutable hashtable and thinking about what its interface should be, so probably I should just upload the hashtable to hackage as is and look what comes next :)

what are the differences against Data.Hashtable? -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

Eugene Kirpichov

9 a.m.

New subject: Re[6]: Re: Incremental array updates

2009/2/27 Bulat Ziganshin :

...

Hello Eugene,

Friday, February 27, 2009, 4:42:03 PM, you wrote:

...
I'm exactly basing on them, but they don't have at least these things:

"them" means Edison or Collections typeclasses? The EdisonAPI.

...

...
- Treatment for unboxed types (I don't know yet, whether it is needed; but why do STUArrays have special treatment then?)

imho, this doesn't need its own typeclass

I hope so :)

...

...
Actually, it started with me writing a monad-mutable hashtable and thinking about what its interface should be, so probably I should just upload the hashtable to hackage as is and look what comes next :)

what are the differences against Data.Hashtable?

Support for ST monad and stuff like insertWith, mergeWith.

...

-- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

-- Eugene Kirpichov Web IR developer, market.yandex.ru

Ross Paterson

26 Feb 26 Feb

11:11 a.m.

On Thu, Feb 26, 2009 at 02:53:42PM +0100, Daniel Kraft wrote:

...

I seem to be a little stuck with incremental array updates... I've got an array of "few" (some thousand) integers, but have to do a calculation where I incrementally build up the array. For sake of simplicity, for now I don't use a State-Monad but simply pass the array as state down the recursive calls.

Unfortunatelly, I seem to experience problems with lazyness; when I run my program, memory usage goes up to horrific values! The simple program below reproduces this; when run on my machine, it uses up about 300 MB of real and 300 MB of virtual memory, and the system starts swapping like mad! I compiled with ghc --make -O3, ghc version 6.8.3 if that matters.

As noted above, updating an array one element at a time is the problem. But before writing an imperative program with STUArray, you might try building a whole new Array, specifying a new value for each element, using array or accumArray. These are often enough. In your simple example: procOne :: Int -> MyArray -> MyArray procOne a cnt | a >= limit = cnt | otherwise = procOne (a + arraySize) $! array (0, arraySize - 1) [ (i, cnt!i + 1) | i <- [0 .. arraySize - 1] ] If elements of the new array depend on previously computed elements of the same array, you can define the array recursively.

Daniel Kraft

11:31 a.m.

Ross Paterson wrote:

...

On Thu, Feb 26, 2009 at 02:53:42PM +0100, Daniel Kraft wrote:

...
I seem to be a little stuck with incremental array updates... I've got an array of "few" (some thousand) integers, but have to do a calculation where I incrementally build up the array. For sake of simplicity, for now I don't use a State-Monad but simply pass the array as state down the recursive calls.

Unfortunatelly, I seem to experience problems with lazyness; when I run my program, memory usage goes up to horrific values! The simple program below reproduces this; when run on my machine, it uses up about 300 MB of real and 300 MB of virtual memory, and the system starts swapping like mad! I compiled with ghc --make -O3, ghc version 6.8.3 if that matters.

As noted above, updating an array one element at a time is the problem. But before writing an imperative program with STUArray, you might try building a whole new Array, specifying a new value for each element, using array or accumArray. These are often enough. In your simple example:

Well, my main problem was the lazy evaluation... And using STUArray did also speed it up notably, of course :) I finally managed to get it working with it ;)

...

procOne :: Int -> MyArray -> MyArray procOne a cnt | a >= limit = cnt | otherwise = procOne (a + arraySize) $! array (0, arraySize - 1) [ (i, cnt!i + 1) | i <- [0 .. arraySize - 1] ]

If elements of the new array depend on previously computed elements of the same array, you can define the array recursively.

For this example program... yes of course :) I'm trying to do so when possible, but for my real problem I couldn't figure out a nice way to do it like that, unfortunatelly. Which does not mean it is impossible of course, but maybe just I need more experience in functional programming... :D Daniel

Ross Paterson

11:39 a.m.

On Thu, Feb 26, 2009 at 05:31:34PM +0100, Daniel Kraft wrote:

...

Well, my main problem was the lazy evaluation...

No, your main problem was that you were creating 100,000 arrays, each only a little different from the one before.

...

For this example program... yes of course :) I'm trying to do so when possible, but for my real problem I couldn't figure out a nice way to do it like that, unfortunately. Which does not mean it is impossible of course, but maybe just I need more experience in functional programming... :D

Writing imperative programs in Haskell may not be the best way to gain that experience. What is the pattern of updates in your actual program?

Daniel Kraft

1:27 p.m.

Ross Paterson wrote:

...

On Thu, Feb 26, 2009 at 05:31:34PM +0100, Daniel Kraft wrote:

...
Well, my main problem was the lazy evaluation...

No, your main problem was that you were creating 100,000 arrays, each only a little different from the one before.

Here I have to disagree (in my particular situation). Even with Data.Array but the strict evaluation the program took about 5m, where it before wouldn't even get far because of all that memory swapping... With STUArray it took 1m--much better, but the worst of all was the horrific memory usage.

...

...
For this example program... yes of course :) I'm trying to do so when possible, but for my real problem I couldn't figure out a nice way to do it like that, unfortunately. Which does not mean it is impossible of course, but maybe just I need more experience in functional programming... :D

Writing imperative programs in Haskell may not be the best way to gain that experience. What is the pattern of updates in your actual program?

It was about this: I needed to generate "all possibilities" for some combinations and each of those had a numeric property, say from 1 to 10000; I then had to count how many of the possibilities were of a given "category". So I created this array, generated all combinations, and incremented the matching slot each time. I do not see how I could have done this another way, but I think it should be a fairly common pattern, so if there are ideas, I'd welcome them! Daniel

Bulat Ziganshin

1:36 p.m.

Hello Daniel, Thursday, February 26, 2009, 9:27:10 PM, you wrote:

...

It was about this: I needed to generate "all possibilities" for some combinations and each of those had a numeric property, say from 1 to 10000; I then had to count how many of the possibilities were of a given "category". So I created this array, generated all combinations, and incremented the matching slot each time.

it's histogram essentially? accumArray is doing so. internally, it's the same loop using STArray, but accumArray provide you pure API for such computations -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

Ross Paterson

1:54 p.m.

On Thu, Feb 26, 2009 at 09:36:17PM +0300, Bulat Ziganshin wrote:

...

Thursday, February 26, 2009, 9:27:10 PM, you wrote:

...
It was about this: I needed to generate "all possibilities" for some combinations and each of those had a numeric property, say from 1 to 10000; I then had to count how many of the possibilities were of a given "category". So I created this array, generated all combinations, and incremented the matching slot each time.

it's histogram essentially? accumArray is doing so. internally, it's the same loop using STArray, but accumArray provide you pure API for such computations

And accumArray can also be used with UArray if laziness is a problem.

Bulat Ziganshin

1:59 p.m.

New subject: Re[2]: Re: Incremental array updates

Hello Ross, Thursday, February 26, 2009, 9:54:23 PM, you wrote:

...

...
the same loop using STArray, but accumArray provide you pure API for such computations

...

And accumArray can also be used with UArray if laziness is a problem.

to be exact, for Array, STArray used internally for UArray - STUArray -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

Ross Paterson

1:45 p.m.

On Thu, Feb 26, 2009 at 07:27:10PM +0100, Daniel Kraft wrote:

...

It was about this: I needed to generate "all possibilities" for some combinations and each of those had a numeric property, say from 1 to 10000; I then had to count how many of the possibilities were of a given "category". So I created this array, generated all combinations, and incremented the matching slot each time.

I do not see how I could have done this another way, but I think it should be a fairly common pattern, so if there are ideas, I'd welcome them!

Yes, bucketing problems like this are a common case that the standard functions cannot handle. Perhaps the libraries need a canned solution.

Ross Paterson

1:48 p.m.

On Thu, Feb 26, 2009 at 06:45:27PM +0000, Ross Paterson wrote:

...

Yes, bucketing problems like this are a common case that the standard functions cannot handle. Perhaps the libraries need a canned solution.

Stratch that -- as Bulat points out, accumArray is such a canned solution.

5927

Age (days ago)

5928

Last active (days ago)

List overview

Download

22 comments

7 participants

participants (7)

Bulat Ziganshin
Daniel Fischer
Daniel Kraft
Eugene Kirpichov
Luke Palmer
Ross Paterson
Sjur Gjøstein Karevoll