On Mon, 17 May 2004 16:14:44 +0200, Daan Leijen
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.