- Libraries - Haskell.org

Re: Tree Wars (latest round :-)
by Adrian Hey 27 May '04

27 May '04

On Wednesday 26 May 2004 10:53 am, Adrian Hey wrote: > I can post the test code to anyone who wants it. I've put the test code here.. http://homepages.nildram.co.uk/~ahey/HLibs/TreeWars.tar.gz Regards -- Adrian Hey

1 0

RE: DData
by Simon Marlow 25 May '04

25 May '04

On 25 May 2004 15:52, Daan Leijen wrote: > Ok, here is a new "IntMap" module that might improve the > performance of "lookup". Please, let's first test it before > adding the changes to the real distribution. > > I have: > 1) removed calls to "natFromInt" and "intFromNat". Supposedly, > they should expand to nothing but who knows... These calls were being optimised away by GHC. However, something else wasn't: namely the value of maxBound::Word which is used by complement. There's no substitue for actually looking at the code that GHC generates! > 2) I have commented out the guard that tests if the integer > is in the tree at all. When a key is present, lookup will be > faster -- if the key is not present, lookup might be slower. > > Simon, I would be interested to see how it performs with and > without the comment (2) (line 269). If performance is better > without the comment, it means that ghc is spending time doing > intFromNat/natFromInt which means that we might improve matters > by storing Nat's instead of Int's in the IntMap. (I don't know > if such tweaking is worth the trouble though.) I'll run your new code tomorrow and let you know the results. Cheers, Simon

1 0

RE: DData
by Simon Marlow 25 May '04

25 May '04

On 24 May 2004 12:03, Adrian Hey wrote: > On Thursday 20 May 2004 5:04 pm, Simon Marlow wrote: >> And after eliminating some bogosity in the benchmark, I now get: >> >> Insert Lookup Delete >> AVL 0.87 0.22 0.87 >> FiniteMap 1.07 0.17 1.11 >> DData.Map 1.08 0.16 1.02 >> DData.IntMap 0.65 0.16 0.61 >> >> So I declare that on random data, DData.Map has essentially the same >> performance as FiniteMap. IntMap is faster for insertion/deletion as >> expected. AVL is better than FiniteMap for insertion/deletion but >> slower for lookups. > > Could you explain the bogosity you eliminated? I did a full GC before running each part of the test to keep random GC effects to a minimum, and eliminated a couple of cases of badly optimised code in the test program. > The reason I ask is that those second results for lookup for AVL > trees seem pretty reasonable to me, considering the AVL library is > general purpose > and not specialised for any kind of map. Currently the AVL > implementation will have to read 3 heap records per tree node > visited, vs. 2 for FiniteMap and DData.Map. > > For the balanced tree implementations, I wouldn't expect to see any > significant difference in lookup times (given the same degree of > specialisation) and what differences there may be would most likely > be due to differences in how well they managed to balance trees. (But > I guess if random data is to be our benchmark, even simple unbalanced > trees would probably look quite reasonable :-) Of course, this isn't testing how well the balancing works. It is comparing raw performance of several balanced tree implementations, so measuring the overhead of balancing, if you like. > DData.IntMap is rather different from the other three, so I'm not > sure exactly how well I would expect it to perform, but if you assume > lookup time is proportional to the No. of heap records examined > (seems to be reasonable comparing AVL and FiniteMap/DData.Map), then > you'd expect a lookup time of about 0.08 for each if they were > specialised for Int maps. Yes, IntMap should get faster lookup. I looked at the code and managed to make a couple of improvements: adding a 'seq k $' at the beginning of lookup helps, and I fixed a small performance problem with the Word library, but interestingly these don't help the results. I still get 0.16s for the lookup test, so perhaps it is dominated by something else. Cheers, Simon

3 4

DData update
by JP Bernardy 24 May '04

24 May '04

Hi all, In the light of the recent discussion, I've updated DData as such 1. "Seq" has been reverted to what it was (strict append). If anyone is interested in the fully lazy version of sequences that I've hacked, I keep it available under "DData/LazySeq.hs". 2. I've added {# UNPACK #} as suggested. I understand that it suffices to keep DData on par with FiniteMap/Set as it exists now. Please correct me if I'm wrong. 3. I've modified IntSet and IntMap in the same fashion. data IntMap a = Nil | Tip {-# UNPACK #-} !Key a | Bin {-# UNPACK #-} !Prefix {-# UNPACK #-} !Mask !(IntMap a) !(IntMap a) -- notice that the Tip is unpacked as well. That change speeds up the following "benchmark" twofold. import DData.IntSet s = fromList [1..1000000] main = print $ all (`member` s) [1..1000000] I did not try to be precise in the measurement, since it seemed obvious that there was an improvement. The source is at the usual URL (users.skynet.be/jyp/DData/ddata.tar.gz) but I have not updated the docs. Cheers, JP. __________________________________ Do you Yahoo!? Yahoo! Domains � Claim yours for only $14.70/year http://smallbusiness.promotions.yahoo.com/offer

1 0

RE: DData
by Simon Marlow 24 May '04

24 May '04

On 14 May 2004 16:47, Christian Maeder wrote: > My experiments (with large maps) wrt. performance (and memory > consumption with and without optimization) of both Map and FiniteMap > implementations revealed differences, but no crucial ones. > > "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. If DData.Map performs worse than DData.FiniteMap, I'm sure it can be improved (they use the same algorithm, after all). > (We would need a pure HashMap with O(1) lookup while extending the > Map) Could you elaborate? Cheers, Simon

5 10

AVL Trees available
by Adrian Hey 23 May '04

23 May '04

Hello, I've put my candidate for Data.Trees.AVL up here.. http://homepages.nildram.co.uk/~ahey/HLibs/Local.Data.Trees.AVL/ It's not finished, but in the absence of any other AVL tree offerings that I'm aware of, I would like to strike the Local prefix from this library name and claim the currently vacant Data.Trees.AVL slot in Simon M's hierarchy. If you look at the code you'll see this is not Haskell at it's most elegant. Most of tt's like assembler written in Haskell, but it's fast :-) I'd also like to book "Data.COrdering" too, if that's OK. Regards -- Adrian Hey

1 2

RE: AVL Trees available
by Simon Marlow 21 May '04

21 May '04

On 20 May 2004 07:50, Adrian Hey wrote: > On Wednesday 19 May 2004 10:47 am, Simon Marlow wrote: > >> I'm happy for this to be "the" Data.Trees.AVL library. I'm sure >> others will want to comment on the details. I wonder whether it >> would make sense to have a specialised AVLMap type, which would let >> you optimise the representation of AVL-based finite maps? > > Do you mean a newtype wrapper for the current AVL type or distinct > algebraic type which contains both the key and the associated value > as separate fields (like the Map type folks were talking about > recently)? > > If you mean the former, one thing I was thinking about doing was > creating an AVL based clone of the current Data.FiniteMap library so > folk could experiment with the effect of using both on real programs > just by changing their imports. Actually I meant the latter, but this is a good idea too. Data.Map.AVL? > If you mean the latter, I'm not keen on this because it would mean > duplication of a lot of code for the new type, and I'm not sure that > it would be an optimisation at all. I considered this but decided > against it on the grounds that I suspect a major contributor to > the true cost of tree operations is heap burn rate. The AVL tree > type has only 3 fields in each constructor (not 5 as with the Map > type for example), and the code was carefully written to avoid > unnecessary heap construction wherever possible. Doing this would > result in 4 fields in each constructor. The total space overhead for the tree would be smaller, because the pair constructor is inlined. 5 words per tree node instead of 7, and one fewer eval each time you examine a node. However if a lot of rebalancing happens on the tree, then being able to share the key/value pairs might be a win. Code duplication is clearly a problem, though. Anyway, t'was just a thought... >>> I'd also like to book "Data.COrdering" too, if that's OK. >> >> Data.COrdering is less obviously the right thing. Can you give some >> motivation for the design here? > > Because you you generally do end up combining values which turn out > to be "equal", in some manner. If you don't use a function which > returns a COrdering, then you have to either.. > > Pass the comparison and combining function separately down your > recursive search or whatever. But this will have extra runtime > overhead, which is often unnecessary since the only time the > combining function is ever used is when the comparison returns EQ. > > or.. > > Use some default combining function (like pairing) and apply the > real combining function later. But pairing is the only reasonable > default combining function I can think of, and this not always > the right type (e.g. for pushing elements in a tree or set union), > and even when it's OK type wise you've still got the overhead of an > additional map operation (e.g for set intersection). You could get > around the type problem using lists I suppose, and use (++) as the > default combining function, but this doesn't seem very attractive > to me. Right, I think I see the reasoning. In the case of writing/pushing, the COrdering allows you to pass a composition of a comparison and a combining function around, which looks cleaner. It's not obviously more efficient than passing the two functions around, because the actual comparisons will be going through an extra level of higher-order function (except that you've INLINEd everything in sight, so the COrdering combinators probably disappear :-). In the case of lookup, it doesn't look like you need COrdering: just apply the "combining function" to the result of genRead/genTryRead, right? But given that you're using COrdering for writes, using it for read too is reasonable. Ok, I guess I'm more or less convinced. Cheers, Simon

2 1

Re: DData
by Adrian Hey 20 May '04

20 May '04

On Thursday 20 May 2004 11:32 am, Ross Paterson wrote: > > Unfortunately, I think a large part of the time here is probably > > accounted for by the time taken to generate the test data itself, if the > > results on my machine are anything to go by. Using your test data > > increases the execution time of the insertion test (for 100000 pairs) > > from 0.39 seconds to 1.88 seconds for AVL trees. > > Building random data costs more, but random insertions are also more > costly than ordered ones. (With ordered insertions, the insertion path > is much shorter than the average tree depth.) Also, the difference > varies between implementations. I don't know if that's true for the trees used in FiniteMap, but for AVL trees newly inserted elements always become leaves, so I would guess that the insertion path is always about the same as the average tree depth, regardless of order. In fact I find it hard to see how else things could work, but without knowing the details of other implementations I guess I can't say for sure. One possible alternative explanation that occurs to me is that ordered insertions give better cache behaviour. Typically the insertion path will change little from one insertion to the next, so most of the nodes concerned will likely be resident in cache already, as they were just created by the previous insertion. So maybe the apparent difference between AVL trees and FiniteMap in this case is really due almost entirely to differing heap burn rate, rather than differences in the notional efficiency of the rebalancing algorithm. It would be good to try to establish a set of representative benchmarks for the various tree types though. Trouble is with a garbage collected language modern cached CPU's it's hard to be sure that benchmarks are representative of the true costs in real progams. It's also hard to be sure that the measured time for random data generation in isolation is representative of the cost where it runs in the presence of other cache disrupting code, for example. Every time I've tried to normalise my results this way I get answers that don't seem to make much sense :-( Regards -- Adrian Hey

1 0

RE: DData
by Simon Marlow 20 May '04

20 May '04

On 19 May 2004 11:28, Ross Paterson wrote: > Inserting in random order gives a less dramatic difference. > I changed your testData to > > testData = take 100000 $ randomRs (0, 2^30-1) (mkStdGen 7) > > (I have a slower machine), changed isEmpty to size to guarantee > strictness, and got the following times (averaged over 50 runs each): > > ins ins+del > Data.FiniteMap 4.783 8.304 > Data.Tree.AVL 4.561 6.895 > DData.Map 4.765 7.369 > DData.IntMap 4.952 7.742 > > (I tried to be fair by only using ! and UNPACK on Ints in each case, > and compiling them all the same way: -O.) I assume that Christian's > results imply that IntMap is better for lookup, but it doesn't look > very attractive here. Yes! This is the kind of data we need. Daan - any idea why IntMap is underperforming here? Cheers, Simon

1 0

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

20 May '04

On 18 May 2004 09:24, Robert Will wrote: > On Tue, 11 May 2004, Simon Marlow wrote: > >> 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. > > Well, Dessy has only 1 and 3 and that for good reason. > > In fact, this discussion does somehow miss the point, since none of > these three are most "general-purpose Sequences", with a lot of > unnecessary O(N) operations (e.g. for 'last' and (!!)). The reason to prefer a sequence with an O(N) 'last' over one with O(log N) 'last' would be if the O(N) version had lower constant factor overhead and you didn't need to use the O(N) operations. Measurements please! Cheers, Simon

4 4