DData

[Daan Leijen]

On Mon, 17 May 2004 16:14:44 +0200, Daan Leijen <daanleijen at xs4all.nl> wrote:

>>> When I omitted the "!" in " !k a !(Map k a) !(Map k a)"
>>>
>>> time was faster but page faults increased:
>>>
>>> Map-only:   7.37    29767
>>
>> You should measure this version, because it is closer to what FiniteMap
>> does (plus there seems to be no good reason to force strictness on the
>> elements in a general purpose Map type).
>
> I agree with this. Note however that this forced strictness on the *key*
> not the element. It is ok to force strictness on the key as they are
> evaluated anyway -- and that is why I am surprised to see a speedup :-)

Ah, I read it too fast -- I assume that you also removed the strictness on
the branches (instead of just the key), i.e. you changed:

   !k a !(Map k a) !(Map k a)"

to

   k a (Map k a) (Map k a)

Right?

If this is the case, analysis becomes more complicated. The application could
speed up now when you don't use certain paths in the tree (as these are not
evaluated). However, I think that it may also lead to a space leak: if someone
inserts the same element a thousand times, there will be thunk of a thousand
insertions. In the strict case, the insertion is evaluated each time and no
drag can occur. (I think there some text about this in Simon PJ's book on
implementing functional languages). Of course, I don't know if this ever happens
in practice. Are the branches in FiniteMap strict?

All the best,
  Daan.
>
> All the best,
>   Daan.