May 2004 - Libraries - Haskell.org

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

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

20 May '04

On 18 May 2004 07:23, Adrian Hey wrote: > 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. 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? The library infrastructure team will shortly provide you with a ship vehicle for your library. I promise ;-) > 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. Data.COrdering is less obviously the right thing. Can you give some motivation for the design here? Cheers, Simon

2 1

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

19 May '04

On 19 May 2004 10:48, Simon Marlow wrote: > On 18 May 2004 07:23, Adrian Hey wrote: > >> 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. > > I'm happy for this to be "the" Data.Trees.AVL library. Actually Data.Tree would be more consistent than Data.Trees, since the rest of the Data.XXX are singular. I'll change the document appropriately. Cheers, Simon

1 0

HaXML regression test suite (work-in-progress)
by Graham Klyne 18 May '04

18 May '04

I've placed a copy of my work-in-progress regression test suite for HaXml on the web, at: http://www.ninebynine.org/Software/HaskellUtils/HaXml-1.11/test/ There are a small number of home-grown tests, but the majority of test cases are based on the W3C XML test suite (currently, just a small part thereof). The W3C test data files are in a zip archive in the same directory: http://www.ninebynine.org/Software/HaskellUtils/HaXml-1.11/test/xmlts200312… I believe the test program should run with zero errors using the existing HaXml, "out of the box". Over time, I'll add in more of the W3C test cases (there are very many of them), but I'm hoping that this will serve for now as an effective regression-test suite for HaXML. #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0

Re: HaXml
by Graham Klyne 18 May '04

18 May '04

Malcolm, For your information... I'm starting a push to bring a version of the HaXml library code to the point of meeting my requirements. First step is to sort out the error handling and diagnostic reporting. (I've made the changes to the error handling, and the parser still works but the effect is that error diagnostics are not very good: everything reverts back to a failure of the top-level production.) The changes are looking a bit deeper than I first expected, so my current plan is: (a) beef up the test case library. I plan to track down a set of test data that you mentioned previously. (I can't get to the CVS to find these right now.) My test cases are based on (1) success/failure to parse a given collection of data, and (2) pretty-print and text comparison of the result with a stored (and previously checked) version. At some stage, the test code may be improved to be less sensitive to formatting detail, but it's serving my purposes well enough for the present. It's pretty easy to add new test cases. (b) refactor the parser combinator code so that the parser combinators access the token information (e.g. position and other diagnostic information) via a new type class. This is to keep the combinators as independent as possible of the lexer details. (c) enhance the error handling structure that I've already started on so that I can distinguish between parse failure (failure of an alternative) and definite failure (e.g. lexing error or tag mismatch), and also to make sure the right diagnostic information is propagated back to the calling program. Apart from the adding extended diagnostic interface I've already created (modulo some name change to make it more obvious what it does) I plan to keep existing external interface unchanged. (BTW, I've noticed some situations where I think the current code is not fully XML compliant with respect to recognizing alternative case variants such as XML, Xml, xMl, xml, etc. I'll try and add comments to them as I see them.) #g -- UPDATE: www.haskell.org seems to be down, so I can't locate the CVS to find your bug documents. But I've grabbed the W3C XML test suite, and added some 300 test cases based on James Clark's XMLTest collection for Valid and not-wellformed stand-alone documents. So far, I'm just performing parse/fail tests, not checking the output. I'm getting about 6 failures for valid documents, and lots of failures to reject not-well-formed documents. It also appears that formfeeds in the input document cause the parser all sorts of grief. The valid-document failures are all to do with odd characters (did you notice that ':' is a valid attribute name? I didn't!) Anyway, I reckon the c. 200 remaining tests probable make a fairly good regression test suite for my refactoring work to proceed. Over time, I should be able to hook in the entire applicable W3 test suite. #g -- At 13:31 23/03/04 +0000, you wrote: > > HuttonMeijerWallace.hs modified to include an option to return a > > diagnostic message or parser result, via an (Either String a) value. > > The original interface is (mostly) preserved, and new functions added > > to support the extended return values (e.g. papplydiag). > >If the original interface is largely preserved, I'll happily include >your modifications once I've had a look through them. By the way, >what is the mnemonic value of 'diag' in your additions? It suggests >"diagonalised" to me, but I don't quite see how that fits. > >Regards, > Malcolm > >P.S. I've seen your message to the libraries list stating that you >are going to continue your project using HXToolkit rather than HaXml, >so thanks for the effort you have already contributed, and all the >best with HXT. Perhaps one day I will get the chance to sit down >and compare the two systems myself and possibly develop a merger of >their good points. ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0