- Haskell-Cafe - Haskell.org

using Map rather than FiniteMap
by S. Alexander Jacobson 27 Jan '05

27 Jan '05

Just did a search after my last post and learned that FiniteMap is bad. Discoverd that Data.Map is the intended replacement. Downloaded it and modified it to work with 6.2. Blazingly fast! Yay. Please ignore the prior message. -Alex- ______________________________________________________________ S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com

5 7

RE: [Haskell-cafe] using Map rather than FiniteMap
by Simon Marlow 27 Jan '05

27 Jan '05

On 26 January 2005 16:42, S. Alexander Jacobson wrote: > On Wed, 26 Jan 2005, Simon Marlow wrote: >> When using the ordinary 2-generation collector, memory in use will >> tend to be 2-3 times larger than the actual residency, because this >> is a copying collector. > > Ok. Perhaps you want a different name for > this item in the reports? Well, "memory in use" is pretty accurate - it measures the actual amount of memory that the runtime has allocated from the OS. "residency" is a GC term which refers to the amount of live data. I don't think these terms are that confusing, but perhaps my explanation was? >>> On the other hand, I found 10mb, 5mb, and 2.5mb >>> maximum residency, but that is still ~100 bytes >>> per record. > > But 100 bytes per record in a (Map Int Int) seems > awefully high. That 100 bytes includes stack overhead. Remember, when you ran the heap profile which didn't show stack overhead you got a much more reasonable figure. >>> Lastly, I tried "example +RTS -p -K5M -hc" and >>> then looked at the resulting graph (attachment #2) >>> and it shows a total of 1.6Mb heap allocated and >>> if that data is correct, it does correspond >>> roughly to our 20-30 bytes per record estimate. >> >> That profile doesn't include the stack, which sounds reasonable. > > So I guess all the extra memory is actually being > allocated on the stack rather than the heap which > is a sign of a spaceleak. If I solve the > spaceleak I get the 70 bytes per item back. Yup. >> I haven't looked at your code in detail, hopefully someone else can >> shed some light on why you're building up such a large stack in the >> first place. > > The code is just this 6 line program: > > import qualified Map > zipped =zip [1..] [1..100000]::[(Int,Int)] > untup f (x,y) = f x y > produce = foldr (untup Map.insert) Map.empty zipped > fm = length $ Map.keys produce > main = print $ fm > > Can someone tell me what I can do to make this > more efficient? Replace the foldr by a foldl'? import Data.List produce = foldl' (untup (flip Map.insert)) Map.empty zipped (untested) Cheers, Simon

1 0

RE: [Haskell-cafe] using Map rather than FiniteMap
by Simon Marlow 27 Jan '05

27 Jan '05

On 26 January 2005 14:29, S. Alexander Jacobson wrote: > Ah, ok. So I ran the code with 100000 items, > 50000 items, and 25000 items and got total memory > in use of 28Mb, 15Mb, and 8Mb respectively. That > comes to 260-280 bytes per record which is still > an order of magnitude higher than the 20-30 bytes > per record we would expect. When using the ordinary 2-generation collector, memory in use will tend to be 2-3 times larger than the actual residency, because this is a copying collector. > On the other hand, I found 10mb, 5mb, and 2.5mb > maximum residency, but that is still ~100 bytes > per record. Right. > Lastly, I tried "example +RTS -p -K5M -hc" and > then looked at the resulting graph (attachment #2) > and it shows a total of 1.6Mb heap allocated and > if that data is correct, it does correspond > roughly to our 20-30 bytes per record estimate. That profile doesn't include the stack, which sounds reasonable. > Regarding stack, I tried "example +RTS -p -K5M -xt > -hc" and then ran hp2ps and looked at the > resulting graph (attachment #1) SYSTEM appears to > use 4mb of stack at the very beginning (presumably > to create "zipped"), but I don't know why it > would. Then this stack is consumed by the rest of > the program. Stacks never get smaller in GHC, only bigger. If you need 4Mb of stack at one point in your program, you will forever have a 4Mb stack after that (fixing this wouldn't really buy you much; the memory doesn't get traversed or copied by the GC - but one thing you could do is madvise() to tell the OS it doesn't have to page the memory, though). I haven't looked at your code in detail, hopefully someone else can shed some light on why you're building up such a large stack in the first place. Cheers, Simon

2 1

RE: [Haskell-cafe] using Map rather than FiniteMap
by Simon Marlow 26 Jan '05

26 Jan '05

On 25 January 2005 23:27, S. Alexander Jacobson wrote: > Oops. It pays to check your checking code before > making posts like this. > > After actually running the correct test, I am > still getting semi-ridiculous space behavior > (6k/pair)! > > import qualified Map > zipped =zip [1..] [1..100000]::[(Int,Int)] > untup f (x,y) = f x y > produce = foldr (untup Map.insert) Map.empty zipped > fm = length $ Map.keys produce > main = print $ fm > > Has this profile: > > example +RTS -p -K5M -RTS > > total time = 5.10 secs (255 ticks @ 20 ms) > total alloc = 612,534,236 bytes (excludes profiling overheads) > > COST CENTRE MODULE %time %alloc > balance Map 71.8 72.8 > insert Map 12.2 10.8 > size Map 9.0 9.7 > bin Map 2.4 2.2 > rotateR Map 1.6 0.3 > zipped Main 0.8 1.9 > > Notice the 612Mb for storing a mapping from Int > to Int!! Notice that's 612Mb *allocation* to create the finite map and deconstruct it into a list. Not 612Mb of live heap to store the finite map. If you make sure everything is evaluated, and examine the heap profile I'm sure you'll find that the finite map is taking a reasonable amount of space (perhaps 20-30 bytes per node for storing integers, I guess). To get a rough idea of the total live heap without profiling, you can run the program with +RTS -sstderr and look at the memory "in use" figure. Cheers, Simon

2 1

RE: [Haskell-cafe] what is a stack overflow?
by Simon Marlow 26 Jan '05

26 Jan '05

On 25 January 2005 16:04, S. Alexander Jacobson wrote: > Ok. I guessed I was producing a big expression > of the form > > addToFM (addToFM (addToFM (addToFM (addToFM ...) > > I tried to solve it by doing > > (addToFM $! fm) key val > > But still got an error. I then tried the same > with the wrapper code, but still got the error. > > Is there a way to profile stack usage using GHCi > (without compiling) to find the problem? +RTS -xt -RTS will include the stack in a heap profile. See http://www.haskell.org/ghc/docs/latest/html/users_guide/prof-heap.html It will show you the size of the stack over time, but not the contents of the stack. Cheers, Simon

2 1

RE: [Haskell-cafe] Re: Can't do basic time operations with System.Time
by Simon Marlow 26 Jan '05

26 Jan '05

On 25 January 2005 17:17, John Goerzen wrote: > On Tue, Jan 25, 2005 at 03:15:38PM -0000, Simon Marlow wrote: >> normalizeTimeDiff (and TimeDiff in general) is wrong. I wouldn't >> recommend using it. There's the TimeExts library in the lang >> package, which might be useful to you. > > I'm curious about that package. It's in my ghc source tree but not > documented at > http://www.haskell.org/ghc/docs/latest/html/libraries/index.html. > > Is it assumed to be portable and available outside ghc? It's an old non-hierarchical library, unfortunately with no documentation. It'll probably disappear in GHC 6.6, but you can always take the source and use it in your apps. Hopefully by 6.6 there will be a decent date/time library that provides this functionality. Cheers, Simon

1 0

RE: [Haskell-cafe] Re: Visual Programming Languages
by Bayley, Alistair 26 Jan '05

26 Jan '05

> From: Stijn De Saeger [mailto:stijndesaeger@gmail.com] > > Don't know if this is exactly what you were thinking of, but you may > want to have a look at > www.subtextual.org > > if you do, make sure you watch the demo. This was odd... Some cherry-picked quotes from the manifesto: http://alarmingdevelopment.org/index.php?p=5 - Visual languages are not the solution: ... common idea is to replace AST structures with some form of graphical diagram. ... - Programming is not Mathematics - Change is natural: There has been much effort expended to remove the concept of mutable state from programming, to be replaced by immutable values as in mathematics. This is entirely misguided. ... Monads are a reductio ad absurdum. [ Heresy! :-) ] - Control flow considered harmful: ... The primary reason for this is to permit side-effects to be ordered by the programmer. ... [ This appears to contradict the criticism of monads. ] But then the demo shows us how to define a Factorial function using an editor that (AFAICT) is simply operating on AST structures, in a tree-oriented layout. I must be missing something. Alistair. ----------------------------------------- ***************************************************************** Confidentiality Note: The information contained in this message, and any attachments, may contain confidential and/or privileged material. It is intended solely for the person(s) or entity to which it is addressed. Any review, retransmission, dissemination, or taking of any action in reliance upon this information by persons or entities other than the intended recipient(s) is prohibited. If you received this in error, please contact the sender and delete the material from any computer. *****************************************************************

2 1

Re: [Haskell-cafe] How to convert from "IO String" to String
by Dmitri Pissarenko 26 Jan '05

26 Jan '05

Hello! Thanks for your answer! > You probably want something like... > > l = [0, 255, 255, 255, 255, 0, 255, 255, 255, 255, 0, 255, 255, 255, 255, 0] > testConvertToList01 = do img <- readImage "../data-test/diagonalImage.pgm" > return $ TestCase $ assertEqual "" l > (convertToList img) When I use this test case definition, I'm getting an error when constructing the test suite: tests = TestList [testCommentLine01, testCommentLine02, testConvertToList01] GHCi writes TestLik.hs:22: Couldn't match `Test' against `IO Test' Expected type: Test Inferred type: IO Test In the list element: testConvertToList01 In the first argument of `TestList', namely `[testCommentLine01, testCommentLine02, testConvertToList01]' Best regards Dmitri Pissarenko -- Dmitri Pissarenko Software Engineer http://dapissarenko.com

2 2

Re: Visual Programming Languages
by Stijn De Saeger 26 Jan '05

26 Jan '05

> This was odd... > > Some cherry-picked quotes from the manifesto: > http://alarmingdevelopment.org/index.php?p=5 > > - Visual languages are not the solution: ... common idea is to replace AST > structures with some form of graphical diagram. ... > > - Programming is not Mathematics > > - Change is natural: There has been much effort expended to remove the > concept of mutable state from programming, to be replaced by immutable > values as in mathematics. This is entirely misguided. ... Monads are a > reductio ad absurdum. [ Heresy! :-) ] > > - Control flow considered harmful: ... The primary reason for this is to > permit side-effects to be ordered by the programmer. ... [ This appears to > contradict the criticism of monads. ] > > But then the demo shows us how to define a Factorial function using an > editor that (AFAICT) is simply operating on AST structures, in a > tree-oriented layout. I must be missing something. > > Alistair. Yes, it is a bit of a twist. I came across this thing a couple of days ago on the LtU blog, and somehow thought it relevant to the issue of visual programming. I'm curious why the author himself doesn't consider this to be a visual programming language, considering that the language only allows you to program by copying and pasting. stijn.

1 0

Re: Visual Programming Languages
by Stijn De Saeger 26 Jan '05

26 Jan '05

Hi, Don't know if this is exactly what you were thinking of, but you may want to have a look at www.subtextual.org if you do, make sure you watch the demo. cheers, stijn.

1 0