On 17 May 2004 14:53, Christian Maeder wrote:
Today there's additionally running a fat (600MB) vmware on davinci. I thought page faults somehow correlate with memory consumption. Have you a better idea to measure time and space?
Page faults, assuming you got the information from time(1) are pretty useless. For memory consumption you can measure two things: total allocation, which is gotten from '+RTS -sstderr -RTS', and live data, which is gotten from a heap profile. Beware laziness effects when making measurements: try to ensure that both examples are evaluating exactly the "same" things. By the way, can we see the code for your tests? What mix of operations are you measuring? What is the Map+IntMap version of your test measuring?
You can play the {-# UNPACK #-} trick in the IntMap code too, BTW. -- | A map of integers to values @a@.
data IntMap a = Nil | Tip !Key a | Bin !Prefix !Mask !(IntMap a) !(IntMap a)
On Prefix and Mask?
Yep.
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). Cheers, Simon
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 :-) All the best, Daan.
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.
----- Original Message -----
I assume that you also removed the strictness on the branches (instead of just the key), .... 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.
No, the balancing algorithm does force the evaluation of all paths. We cannot have balanced lazy data structures (exept for lazyness in the elements). This page contains a longer explanation (search for "lazy"): http://www.stud.tu-ilmenau.de/~robertw/dessy/fun/principles.html Robert
On Mon, 17 May 2004 16:36:27 +0200, Robert Will
----- Original Message -----
I assume that you also removed the strictness on the branches (instead of just the key), .... 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.
No, the balancing algorithm does force the evaluation of all paths.
Hmm, I think you are right. As "balance" will force structure on the entire tree it seems that removing the strictness on the branches will be safe. It still could lead to "drag" -- but it may also speed up many applications due to less explicit evaluation (as remarked by Simon). Let the benchmark be the judge than :-) -- Daan.
participants (4)
-
Christian Maeder -
Daan Leijen -
Robert Will -
Simon Marlow