[Haskell-cafe] using Map rather than FiniteMap

S. Alexander Jacobson alex at alexjacobson.com
Wed Jan 26 11:41:32 EST 2005

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?

>> 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. A 3 record Map would be:

    (Bin 3 2 2
 	(Bin 1 1 1 Tip Tip)
 	(Bin 1 3 3 Tip Tip))

Here is how I account for memory:

 		size	qty	subtotal
Ints		4	9	36
Pointers	4	7	28
Constructors	4	7	28
Total				92
Num Pairs			 3
Bytes/Pair			31

Is this accounting correct? Where do the other 70 
bytes/item go?

>> 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.

> 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?


S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com

More information about the Haskell-Cafe mailing list