[Haskell-cafe] using Map rather than FiniteMap

[Simon Marlow]

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