September 2010 - Libraries

Proposal: Add "writer" Monad instance (, ) o to Control.Monad.Instances
by Jake McArthur 24 Sep '10

24 Sep '10

This proposal [1] was originally submitted to Trac by Conal Elliott, but it was apparently abandoned and closed after some time. I've picked it back up and written out a patch. Here is the text of the proposal: > I'd like to have a (,)-style writer instance alongside the (->)-based reader instance for Monad in Control.Monad.Instances. > > Here's the current reader: > > instance Monad ((->) r) where > return = const > f >>= k = \ r -> k (f r) r > > and my proposed writer: > > instance Monoid o => Monad ((,) o) where > return = pure > (o,a) >>= f = (o `mappend` o', a') where (o',a') = f a > > where the return definition relies on the Applicative instance of ((,) o). Written out explicitly, > > return a = (mempty,a) > > Control.Monad.Instances will also need two new imports: > > import Data.Monoid (Monoid(..)) > import Control.Applicative (pure) - Jake [1] http://hackage.haskell.org/trac/ghc/ticket/1951

6 5

Proposal: Better recip for Ratio a
by Daniel Fischer 24 Sep '10

24 Sep '10

I propose to change the implementation of recip in the Fractional instance of Ratio a to make it faster. Currently, the instance defines recip (x:%y) = y % x which means that the gcd of numerator and denominator is recalculated, although for all properly generated values, they are known to be coprime. (Invalid vlaues can be obtained via direct use of the constructor or via fromRational cf. http://hackage.haskell.org/trac/ghc/ticket/4335.) Period of discussion: Three weeks, unitl 15th October (because of ICFP). Ticket: http://hackage.haskell.org/trac/ghc/ticket/4336 For Rationals with large numerators and denominators, the proposed implementation recip (0:%_) = error "Ratio.%: zero denominator" recip (x:%y) | x < 0 = negate y :% negate x | otherwise = y :% x gives a huge speedup.

2 1

Summary of containers patches
by Milan Straka 24 Sep '10

24 Sep '10

Hi Simon, as you probably know, there are several containers patches dealing with performance, separate testsuite and benchmarking. Specifically, I mean tickets http://hackage.haskell.org/trac/ghc/ticket/4277 http://hackage.haskell.org/trac/ghc/ticket/4279 http://hackage.haskell.org/trac/ghc/ticket/4280 http://hackage.haskell.org/trac/ghc/ticket/4311 http://hackage.haskell.org/trac/ghc/ticket/4312 http://hackage.haskell.org/trac/ghc/ticket/4333 I have all of them in the following repository http://fox.auryn.cz/darcs/containers/ There are no user-visible changes, just performance and the split testsuite. There were no comments in some time, so I would like to push them to containers. There is just the code-bloat issue to solve. The excessive use of INLINE pragma causes a large code bloat. I am aware of it, it happened even when I was benchmarking the containers. Personally I vote for: - changing INLINE to INLINABLE - leave INLINE just in - member/lookup functions - insert* functions as these benefit from specialization a lot and do not cause such a bloat (measured during the internship, do not recall the numbers now). I suspect the performance to drop a bit, but I think it is better to have a bit slower containers without such a code bloat. Simon, I will be flying to IFCP soon, but if you want, I can prepare the INLINE->INLINABLE patches and put them in the repo. Cheers, Milan

12 31

Solving the containers INLINE issue
by Milan Straka 24 Sep '10

24 Sep '10

Hi, I suggest following variants for solving INLINE containers issues. This solution will be short-term only, the long-term one will probably go in the way of being able to specialize INLINABLE functions. a) remove all INLINEs - smallest code - up to 50% worse - the numbers are in one of my previous mail b) leave all INLINEs - biggest code - fastest - numbers are in one of my previous mail c) remove all INLINEs, but leave small amount of reasonable INLINEs - on functions needing Ord, ie. Map and Set - on 'small' functions only -- member, notMember, lookup*, insert*, delete*, alter*, update*, adjust* and fold* - set balance, balanceL and balanceR as NOINLINE (otherwise they get inlined in insert*, making them too big) - smaller code bloat - ghc binary is 1.4% larger than a) instead of 3.8% (which is the amount b) is larger than a)) - map-properties test is 0.4% larger instead of 126% - Map benchmark is actually 0.2% smaller (probably because of balanceL and balanceR not inlining to insert) - reasonable performance. Here is the speedup of c) against b), measured in % (+= several pct). alter 2.73 delete 3.01 difference 3.76 insert -16.40 insertLookupWithKey empty -1.60 insertLookupWithKey update -2.32 insertLookupWithKey' empty -8.39 insertLookupWithKey' update -15.75 insertWith empty -16.04 insertWith update -15.26 insertWith' empty -17.13 insertWith' update -14.67 insertWithKey empty -15.35 insertWithKey update -13.01 insertWithKey' empty -17.09 insertWithKey' update -16.81 intersection -3.46 lookup 2.73 lookupIndex 0.52 union 0.66 update 3.28 updateLookupWithKey -1.44 The only penalty is 15% loss on insert because of not inlining balanceL and balanceR. But when doing so, the bloat is nearly as in b). I vote for c) and have the patches ready. If there are no major objections, I will push the patches in several hours. (or should I do it sooner? Ian? Simon?) Milan

3 4

Re: Summary of containers patches
by John Lato 24 Sep '10

24 Sep '10

> > From: Don Stewart <dons(a)galois.com> > > ivan.miljenovic: > > On 24 September 2010 14:36, Michael Snoyman <michael(a)snoyman.com> wrote: > > > On Fri, Sep 24, 2010 at 6:26 AM, Don Stewart <dons(a)galois.com> wrote: > > >> Perhaps a containers-inline fork is needed, for those who still need > the speed. > > > > > > Would it be possible to use CPP to turn the INLINE flags into a > > > compile-time argument, ie: > > > > > > #ifdef INLINE > > > {-# INLINE #-} > > > #endif > > > > Since containers ships with GHC, wouldn't this then require an extra > > flag being used when building GHC to enable this? > > > > And then to use it, you'd have to build your own GHC rather than using > > a pre-built binary like just about everyone does... > > > > > I'd hate to start seeing incompatible Data.Map.Maps floating around. > > > > Agreed. At the very least if there was a fork it would presumably > > have to be in a different module namespace to avoid namespace > > collisions, which would make the incompatability obvious. > > We're talking about a 3% increase in the size of the Map, a 2% size in > the Map.hs benchmark binary, right? > > For a 50% increase in Map function performance. > I agree. The benefits are significant, and Map is one of the most fundamental (and widely-used) data structures in the language. The binary size increase just doesn't seem important in comparison. John

1 0

INLINE pragma bogus
by Simon Peyton-Jones 24 Sep '10

24 Sep '10

In Data.Map we see mapKeysMonotonic :: (k1->k2) -> Map k1 a -> Map k2 a mapKeysMonotonic _ Tip = Tip mapKeysMonotonic f (Bin sz k x l r) = Bin sz (f k) x (mapKeysMonotonic f l) (mapKeysMonotonic f r) {-# INLINE mapKeysMonotonic #-} But mapKeysMonotonic is recursive, so it isn't going to get inlined. Lint bleats about this. Remove the pragma? Same for Data.IntMap.submapCmp, which is again recursive. Incidentally submapCmp is a MASSIVE function to put an INLINE pragma on! Do you really need this much inlining? Simon

2 1

Proposal: Further performance improvements of Data.Map
by Milan Straka 23 Sep '10

23 Sep '10

Hi, see http://hackage.haskell.org/trac/ghc/ticket/4311. The following text is the description of ticket 4311: This proposal depends on #4277 and #4278. This proposal further improves the performance of Data.Map. It consists of four patches: 1. improvements to union and difference implementation( by eliminating high-order function) 2. improvements to balance function which is used by nearly all methods modifying a map (making one monolithic function which allows perform only one pattern-match on the tree nodes) 3. correction of the test (the Arbitrary instance could generate unbalanced trees, which the patch 2. discovered) 4. added benchmark of union, difference and intersection methods On i386 Intel Core2 and GHC 6.12.1, the improvements are alter 5.61 delete 10.80 difference 20.33 insert 8.09 intersection 7.69 union 21.74 update 7.96 The repository of the containers package with these patches (and also several others) is at http://fox.auryn.cz/darcs/containers/. The patches are also attached.

3 4

Proposal: Performance improvements for Data.IntMap
by Don Stewart 23 Sep '10

23 Sep '10

#4279: Proposal: Performance improvements for Data.IntMap http://hackage.haskell.org/trac/ghc/ticket/4279 Following on from ticket #4277 here is a similar patch for Data.IntMap. This proposal provides a patch that improves performance for many parts of the API. Two standard techniques are applied to the code: * worker/wrapper transformations of functions with multiple static arguments * inlining of non-recursive wrappers Three complementary, but orthogonal patches are provided. 1. Add a testsuite, with [http://code.haskell.org/~dons/tests/containers/intmap/hpc_index.html coverage data] (currently 82% of top level functions, and all core functions). 2. Add a micro-benchmark suite based on Criterion, for empirical evidence of improvements to each function. 3. The optimization patch itself. All 3 patches should be applied, under this proposal. The [http://is.gd/eN7qN benchmark results] are relatively clear: * 13.3% faster on i7 / x86_64 / Linux * 9.95% faster on Mac OS X 10.5 / Xeon / 32 bit http://i.imgur.com/RJ7dH.png No bugs were identified in the development of the comprehensive testsuite, which includes a large set of unit tests from Kazu Yamamoto. ''Discussion'' Unlike Data.Map (#4277) the performance results are less significant for Data.IntMap. There is one main reasons: * Data.IntMap already has strict keys So the strict key improvements seen there are less impressive here. Similarly, worker/wrapper to float out a single Int key has less of an impact than floating out more complex structures used as keys. Hence, a number of functions are unchanged (modulo inlining), including lookup and delete. insert is slightly improved (due to inlining). ------------ A fork of the containers package, with the 3 patches (and a version bump to make it easier to test out) is available: darcs get http://code.haskell.org/~dons/code/containers/ Separately, the patches are attached to this ticket. The consideration period is 3 weeks (before ICFP). Work carried out over 28/29th August, 2010 in Utrecht, NL, by Johan Tibell

6 6

Containers patch for GHC 7.0
by Simon Peyton-Jones 23 Sep '10

23 Sep '10

Dear Container folk GHC 7.0 is going to warn about lambdas with incomplete patterns (if you have -fwarn-incomplete-patterns), such as \[x] -> e The Sequence module in 'containers' has a couple of occurrences, which the enclosed patch fixes. Of course there's no change in functionality, or even what code is generated. Can you apply please Simon

1 0

Re: Proposal: Make intersperse lazier
by John Lato 21 Sep '10

21 Sep '10

Message: 1 > Date: Mon, 20 Sep 2010 15:55:58 +0200 > From: Christian Maeder <Christian.Maeder(a)dfki.de> > Subject: Re: Proposal: Make intersperse lazier > To: Daniel Fischer <daniel.is.fischer(a)web.de> > Cc: libraries(a)haskell.org > Message-ID: <4C9767EE.902(a)dfki.de> > Content-Type: text/plain; charset=UTF-8 > > Am 17.09.2010 20:17, schrieb Daniel Fischer: > > Okay, if you don't then I do :) > > I've benchmarked a couple of variants: > > > > module Interspersing where > > > > isgo :: a -> [a] -> [a] > > isgo _ [] = [] > > isgo s (x:xs) = x : go xs > > where > > go [] = [] > > go (y:ys) = s : y: go ys > > > > isrec :: a -> [a] -> [a] > > isrec s l = case l of > > [] -> l > > (x:r) -> x : if null r then r else (s : isrec s r) > > > > [..] > > > Results: > > With -O2: > > unsurprisingly, isgo and ispreplc have nearly identical means in each > run, > > about 33.6 ms for the small benchmark and 153 ms for the large. > > isprepD is slightly slower, 33.9 ms resp 155 ms. > > isprepM and isprepT are a little slower again, 34.4 ms resp 157 ms. > > isrec lags behind, 43.4 ms resp. 193 ms. > > I also did some benchmarking. It made no difference if ones uses a > global function "prepend" or the local "go" function. (Also prepend is > not faster if written using a worker.) > > The function isrec seem to be rewritten to a form that does not test "r" > twice: > > isrec2 :: a -> [a] -> [a] > isrec2 s l = case l of > [] -> l > x : r -> myGo s x r > > myGo :: a -> a -> [a] -> [a] > myGo s x r = x : case r of > [] -> r > y : t -> s : myGo s y t > > (making myGo local makes it worse) > > myGo produces a non-empty list. Therefore it is safe to change > the recursive call "s : myGo s y t" to "(s :) $! myGo s y t". > > After this change or the change "(s :) $! isrec s r" in Daniel's isrec > function, these function are almost as fast as isgo. > > Cheers Christian > Which compiler/version are you using for your tests? Is the behavior the same for other compilers/versions? In particular, is it similar for ghc-6.10, ghc-6.12, and ghc-HEAD? When benchmarking variants like this, I'm always suspicious that my optimizations may be ghc-version-specific, since I've had occasional experience to the contrary. John Lato

2 1