May 2004 - Libraries - Haskell.org

Subprocesses (was: [ANNOUNCE] shell-haskell 1.0.0)
by Simon Marlow 08 Jul '04

08 Jul '04

Libraries people, There are currently two ways to create and communicate with external processes: - System.Cmd.system (very basic, doesn't give you access to the process's output but you can use shell primitives to redirect its input/output). - Posix.runProcess (can specify Handles for the process's input/output, but it doesn't create pipes so you can't actually communicate with the subprocess using these Handles.). - POpen.popen (can specify an input String, and gives you lazy output Strings. No interactive communication is possible.) Ok, *three* ways. System.Cmd.system, Posix.runProcess, POpen.popen, and shell-haskell. Er. *Four* ways. David Sankel's shell-haskell creates pipes for stdin/stdout/stderr, and lets you communicate interactively with the sub-process via Handles. It could do with a way to specify the environment and working directory of the sub-process (ala POpen and runProcess), but apart from that it seems to be the most flexible of the four. It could be simplified slightly by using one Handle rather than two for stdin/stdout. We should think about what functionality we want to provide in the core libraries. My preference would be to go for a full version with three pipes (like shell-haskell) and perhaps one or two more specialised versions covering common cases (I don't know what these should be, though). What do people think? Cheers, Simon -----Original Message----- From: haskell-admin(a)haskell.org [mailto:haskell-admin@haskell.org] On Behalf Of David Sankel Sent: 06 May 2003 03:06 To: haskell(a)haskell.org Subject: [ANNOUNCE] shell-haskell 1.0.0 =================== shell-haskell 1.0.0 =================== shell-haskell provides utilities to communicate with other process's via Haskell code. This library can be used for something as simple as getting the output of another program or as complex as interacting with an interpreter. see http://www.electronconsulting.com/shell-haskell for details. David J. Sankel _______________________________________________ Haskell mailing list Haskell(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell

5 10

DData
by Christian Maeder 03 Jul '04

03 Jul '04

Hi, may I warm up an old subject? I would appreciate if at least the Map and the Set module could be added to the base package, soon! DData.Set and the current Data.Set can be merged together (as Sven Panne mentioned earlier). Data.FiniteMap and Data.Map should co-exist for a while. The current Data.FiniteMap and Data.Set have various missing functions and instances. It would make sense to add Data.Bag also (but I don't use Bags currently) (I also don't care about Seq, Queue and Int-specializations.) The last proposal was made by JP Bernardy: http://users.skynet.be/jyp/DData/doc Daan wanted to look into it. 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. (We would need a pure HashMap with O(1) lookup while extending the Map) Christian

4 3

FunctorM
by John Meacham 04 Jun '04

04 Jun '04

Pretty simple, and quite useful. perhaps it could be added as Control.FunctorM ? just as Functor generalises 'map', FunctorM generalises 'mapM'. there are probably some instances I missed. note that unlike Functor, an instance for IO cannot be written for FunctorM. module FunctorM where import Array class FunctorM f where fmapM :: Monad m => (a -> m b) -> f a -> m (f b) instance FunctorM [] where fmapM f xs = mapM f xs instance FunctorM Maybe where fmapM _ Nothing = return Nothing fmapM f (Just x) = f x >>= return . Just instance Ix i => FunctorM (Array i) where fmapM f a = sequence [ f e >>= return . (,) i | (i,e) <- assocs a] >>= return . array b where b = bounds a -- John Meacham - ⑆repetae.net⑆john⑈

3 3

RE: Tree Wars, IntMap strikes back.
by Simon Marlow 01 Jun '04

01 Jun '04

On 28 May 2004 13:59, JP Bernardy wrote: > --- Simon Marlow <simonmar(a)microsoft.com> wrote: > >> Interesting, I get pretty much the same results as >> you, except that >> DData.Map is now quicker on the lookup test than >> both FiniteMap and AVL >> (0.120 vs. 0.134 and 0.138 respectively). > > Ok, so that means that I should merge in the last > change by Daan (and in IntSet too)? I wasn't using that patch for my measurements. Cheers, Simon

2 1

RE: Tree Wars (latest round :-)
by Simon Marlow 28 May '04

28 May '04

On 27 May 2004 17:18, Adrian Hey wrote: > 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 Interesting, I get pretty much the same results as you, except that DData.Map is now quicker on the lookup test than both FiniteMap and AVL (0.120 vs. 0.134 and 0.138 respectively). I'm not going to investigate this any further, because it'll take forever to get to the bottom of. I think we've arrived at a reasonable conclusion, that the old FiniteMap is definitely superceded but there isn't a clear choice between the others, so we should provide them all. How about the following modules: Data.Map -- a default implementation of maps, eg. DData.Map Data.Map.AVL -- same interface, based on AVL trees Data.Map.Int -- current DData.IntMap Cheers, Simon

3 2

Re: Tree Wars (latest round :-)
by Daan Leijen 28 May '04

28 May '04

On Wed, 26 May 2004 10:53:54 +0100, Adrian Hey <ahey(a)iee.org> wrote: > I got these results: > > For 500,000 random elements > Insert Lookup Delete > Data.Tree.AVL 0.923 0.203 0.798 > Data.FiniteMap 1.150 0.203 1.259 > DData.Map 1.177 0.205 1.084 > DData.IntMap 0.648 0.163 0.627 > > > For 500,000 ordered elements: > Insert Lookup Delete > Data.Tree.AVL 0.210 0.060 0.117 > Data.FiniteMap 0.473 0.076 0.137 > DData.Map 0.488 0.079 0.145 > DData.IntMap 0.108 0.039 0.054 Very cool results for AVL :-) > We still have no idea how well AVL trees perform for > set operations (haven't written the necessary code yet). Let me take this opportunity to remind us all of being careful when interpreting these numbers: most programs don't just insert and lookup in that order, but mix the operations in a lazy fashion which can lead to wildly different results. Furthermore, I tend to use "union" a lot -- I know/suspect from simple tests that DData.IntMap tends to outperform Data.Map by a wide margin on those kind of operations, etc. Btw. Given the good performance of AVL, maybe we should try to make the interface look like DData.Map (or maybe provide a seperate AVL.Map module to does that). This would allow one to use IntMap, AVL.Map or Map without changing (much) code. All the best, Daan. > > I can post the test code to anyone who wants it. > The mods to test287.hs are: > > Removed size calculation, as this O(n) for AVL trees but O(1) for > FiniteMap and DData.map and is irrelevant to insertion/deletion times. > > Increased testData size from 100,000 to 500,000. > > Used foldl' instead of foldr to prevent stack overflow. > > PerformGC at start of each test in test10 > > Had to swap args of Map.lookup in lookupsMap > > Changed the way results are displayed to be more comprehensible (to me:-) > > Regards > -- > Adrian Hey > > > > _______________________________________________ > Libraries mailing list > Libraries(a)haskell.org > http://www.haskell.org/mailman/listinfo/libraries >

2 1

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

28 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 26 May '04

26 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