May 2004 - Libraries - Haskell.org

RE: How lazy is DData.Seq?
by Simon Marlow 18 May '04

18 May '04

On 10 May 2004 14:56, JP Bernardy wrote: > --- Simon Marlow <simonmar(a)microsoft.com> wrote: > >> Ross's point about requiring append to be strict in order to >> guarantee O(n) toList is a good one. In fact, the current >> implementation isn't >> quite correct: either fromList should be strict, or append should >> check for an empty Many constructor. > > That's what exists in the current published version > (on my "web page"): fromList guarantees that the Many > constructor never has [] as argument. True, thanks for pointing it out. > Anyways, 'toList' will still be O(m) where m = number > of subtrees. Moreover, I hardly expect more that O(n) > empty subtrees in a sequence. O(number of elements) is a tighter constraint than O(number of subtrees). If you build a list with 10 elements using 100 appends, then toList will only require O(10) rather than O(100). If you do more than one toList on the same Seq, you'll notice the difference. But, the tradeoff is strictness in append. It may be that we need multiple versions of Seq, but I suspect that not much would be gained by having all three: 1. ordinary lists with lazy append 2. Seq with O(1) lazy append 3. Seq with O(1) strict append and O(n) toList If we have 1 & 3, then I'm guessing that 2 would be very rarely required. Cheers, Simon

2 1

RE: DData
by Simon Marlow 18 May '04

18 May '04

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

4 5

RE: DData
by Simon Marlow 18 May '04

18 May '04

On 17 May 2004 15:15, Daan Leijen 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 :-) Oops, good point. DData.Map isn't strict in the elements, I misread it. It is possible that being strict in the key is slower, if it introduced extra unnecessary evals. eg. if at the point at which the Map constructor is built, the compiler couldn't figure out that the key was already evaluated, it would have to eval it again. This is probably what happened. Cheers, Simon

1 0

RE: DData
by Simon Marlow 17 May '04

17 May '04

On 17 May 2004 14:33, Christian Maeder wrote: > Simon Marlow wrote: >> On 14 May 2004 19:14, Christian Maeder wrote: >> >> >>> for a map with several hundred thousand entries: >>> (user seconds) (page faults) >>> FiniteMap-only: 5.61 30613 >>> DData.Map-only: 6.50 36911 >>> DData.Map+IntMap: 4.14 21296 >>> FiniteMap+IntMap: 3.85 19973 >>> >> Could you try changing the definition of Map from >> to >> >> data Map k a = Tip >> | Bin {-# UNPACK #-} !Size !k a !(Map k a) !(Map k a) >> >> and see if that helps? > > Yes, that helps. For some reason the user time decreased today, but > the page faults for the unchanged code kept the same: > > FiniteMap-only: 7.94 30613 > DData.Map-only: 7.88 29700 > DData.Map+IntMap: 5.72 20178 > FiniteMap+IntMap: 5.54 19973 I'm not sure what page faults is measuring, but the fact that you get significantly different results today is disturbing! You can play the {-# UNPACK #-} trick in the IntMap code too, BTW. Cheers, Simon

2 1

RE: DData
by Simon Marlow 17 May '04

17 May '04

On 14 May 2004 19:14, Christian Maeder wrote: > for a map with several hundred thousand entries: > (user seconds) (page faults) > FiniteMap-only: 5.61 30613 > DData.Map-only: 6.50 36911 > DData.Map+IntMap: 4.14 21296 > FiniteMap+IntMap: 3.85 19973 > > for optimized code only (I'll send you the sources separately) Could you try changing the definition of Map from data Map k a = Tip | Bin !Size !k a !(Map k a) !(Map k a) to data Map k a = Tip | Bin {-# UNPACK #-} !Size !k a !(Map k a) !(Map k a) and see if that helps? Cheers, Simon

3 2

RE: DData
by Simon Marlow 17 May '04

17 May '04

On 17 May 2004 13:46, Daan Leijen wrote: > I just wondered: is Data.FiniteMap strict in its elements? No it isn't. Removing the strictness annotation on the element type for DData.Map might increase performance too. > ps. Simon: The cvs source browse link on the GHC page seems broken, > so I couldn't look it up myself... Yes I know, the cvs.haskell.org admins are working on it. Cheers, Simon

1 0

RE: DData
by Simon Marlow 17 May '04

17 May '04

On 14 May 2004 18:17, Christian Maeder wrote: > Simon Marlow wrote: >>> "FiniteMap Int a" performs better than "Map Int a", but not as good >>> as "IntMap a", but the differences are unimportant for us. >> >> How much better? I'm not keen to import something that's going to >> degrade performance of existing code noticeably. > > Ok, I'll send you numbers (later). Are you going to reimplement > FiniteMap via DData.Map (or how could existing code suffer)? Sorry, I should have been clearer. I mean that programmers who migrate code to Data.Map will see a performance loss; that's something I'd like to avoid. Furthermore, there shouldn't be any need for Map to be slower than FiniteMap. A 10% loss in performance for FiniteMap isn't going to show up in many profiles, but it'll cause a performance degradation in *lots* of applications, so fixing it is worthwhile. Indeed, we should take the opportunity to see if the code can be tuned any further and improve on the performance of FiniteMap. Cheers, Simon

1 0

RE: How lazy is DData.Seq?
by Simon Marlow 11 May '04

11 May '04

On 10 May 2004 00:02, JP Bernardy wrote: >> What do you mean with this? Do you mean: "I think >> *I* was mistaken [...]"? > > Huh, yes. > >>> The current version behaves ok for sequences mainly constructed with >>> fromList, cons or snoc; a sequence made up of 'append' is strict. >> >> Would it be possible to change this behavior? > > Sure. > I attach the modified version, for reference. Ross's point about requiring append to be strict in order to guarantee O(n) toList is a good one. In fact, the current implementation isn't quite correct: either fromList should be strict, or append should check for an empty Many constructor. Cheers, Simon

4 4

Re: How lazy is DData.Seq?
by Wolfgang Jeltsch 11 May '04

11 May '04

Am Samstag, 8. Mai 2004 18:37 schrieben Sie: > --- Wolfgang Jeltsch <wolfgang(a)jeltsch.net> wrote: > > Hello, > > > > I would suspect that in DData.Seq the result of > > head (singleton 'a' `append` undefined) > > is 'a' but instead it is _|_. Why is this the case? > > I have the invariant that sublists are not empty. > There is, for example: > > append as None = as Is this necessary/desirable? I have an application where I think that it can be important for efficiency that the above expression evaluates to 'a'. So I would like it to not result in _|_. > Cheers, > JP. Wolfgang

4 11

How lazy is DData.Seq?
by Wolfgang Jeltsch 09 May '04

09 May '04

Hello, I would suspect that in DData.Seq the result of head (singleton 'a' `append` undefined) is 'a' but instead it is _|_. Why is this the case? Wolfgang

1 0