- Libraries - Haskell.org

Proposal: Make intersperse lazier
by Daniel Fischer 27 Sep '10

27 Sep '10

The current implementation of Data.List.intersperse causes a space leak under certain not uncommon circumstances. Trac ticket: http://hackage.haskell.org/trac/ghc/ticket/4282 The proposed implementation, intersperse :: a -> [a] -> [a] intersperse _ [] = [] intersperse sep (x:xs) = x : go xs where go [] = [] go (y:ys) = sep : y : go ys changes the semantics from intersperse (x : _|_) = _|_ to intersperse (x : _|_) = x : _|_ apart from that, I think only the run-time behaviour is changed. Period of discussion: Two weeks, until 30 Sep. 2010. Cheers, Daniel

7 19

Containers INLINE issue continues
by Milan Straka 26 Sep '10

26 Sep '10

Hi, we still need to find consensus on containers INLINE issue (sorry about me already deciding and pushing :(). To recapitulate, one part of the containers performance improvements was to put INLINE on nearly all Data.Map methods. That has positive impact on performance (especially for Map Int, Map Word, Map Char, etc, where the comparison is just an instruction; for fold method the speedup works for almost any type). The reason for this is that inlining allows specialization to happen. The negative effect is that the code for insert, lookup, etc. is repeated on every call site. That is not very reasonable (code bloat, I-cache misses). In the long run we could have something like 'SPECIALISABLE' pragma, which would work like c++ template specialization -- every specialization of a method would be only once in the resulting binary. That would have both speed and reasonably small code bloat. GHC 7.0 supports INLINABLE -- the method unfolding is present in the .hi file and GHC decides whether to inline or not. In the short run we need to choose some kind of compromise. What are the possibilities: a) we remove all INLINE and will mark every method INLINABLE. This keeps smallest code, but if someone needs great performance, they can persuade GHC-7.0 inliner to inline the methods from containers. b) we leave INLINE on small amount of small methods where there is a big gain, and mark the rest as INLINABLE. This is what is currently present in the repo (what I pushed without consensus). This is a compromise, some code bloat, small performance losses. The performance gains are present also on ghc-6.* family (not true with a). c) leave all methods marked INLINE. Biggest code bloat (numbers in some of my previous mails), theoretically biggest performance (theoretically I-cache misses could be larger). I think b) is good in the short run, but it is only my opinion. But a) is good idea too and I would also support it. I am flying to ICFP in an hour. I will investigate a) [what switches to give to GHC-7.0 to inline] and post the results, but it will take some time. Thank you, Milan

5 4

Proposal: Max and Min for Monoid
by Jake McArthur 26 Sep '10

26 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 (including a correction mentioned in the first comment on the ticket): > I'd like to add two instances to Data.Monoid, alongside of All/Any, Sum/Product, and First/Last. > > Here's a current instance (as a style example): > > -- | Boolean monoid under conjunction. > newtype All = All { getAll :: Bool } > deriving (Eq, Ord, Read, Show, Bounded) > > instance Monoid All where > mempty = All True > All x `mappend` All y = All (x && y) > > My proposed addition: > > -- | Ordered monoid under 'max'. > newtype Max a = Max { getMax :: a } > deriving (Eq, Ord, Read, Show, Bounded) > > instance (Ord a, Bounded a) => Monoid (Max a) where > mempty = Max minBound > Max a `mappend` Max b = Max (a `max` b) > > -- | Ordered monoid under 'min'. > newtype Min a = Min { getMin :: a } > deriving (Eq, Ord, Read, Show, Bounded) > > instance (Ord a, Bounded a) => Monoid (Min a) where > mempty = Min maxBound > Min a `mappend` Min b = Min (a `min` b) > > I have a niggling uncertainty about the Ord & Bounded instances for Min a? Is there a reason flip the a ordering instead of preserving it? - Jake [1] http://hackage.haskell.org/trac/ghc/ticket/1951

11 19

Containers and folds
by Milan Straka 25 Sep '10

25 Sep '10

Hi, the Set, and IntSet have one 'fold' that does not specify order of folding (but in fact are right folds). Map and IntMap have 'fold' and 'foldWithKey' which is a right fold (and documented as such). Recently foldrWithKey and foldlWithKey was added to Data.Map (foldWithKey is deprecated and a synonymous for foldrWithKey). There are two thinks to sort out: a) add left/right folds, b) add strict folds. I therefore propose to: a) add foldrWithKey and foldlWithKey to IntMap, make foldWithKey deprecated and synonymous for foldrWithKey. b) add foldl and foldr to Set and IntSet, make fold deprecated and synonymous to foldr. c) add strict variants of left and right folds, namely Data.Map, Data.IntMap: foldlWithKey' foldrWithKey' Data.Set, Date.IntSet: foldl', foldr' Some issues: - should we really rename fold -> foldr? Maybe we could cla that fold and foldWithKey are right folds and add only foldl and foldlWithKey. - should we really deprecate fold and foldWithKey? It could break a lot of code. - adding foldl, foldr, foldl' and foldr' to Set and IntSet is going to cause a lot of trouble because of shadowing. Maybe some better name? On the other hand, these are the "right" names. Discussion period: three weeks (because of ICFP). Discussion ends: 15th Oct. Milan

7 13

The libraries proposal process and containers
by Don Stewart 25 Sep '10

25 Sep '10

Milan just pushed all the following patches directly to the containers repo, and closed all the tickets associated with the effort. * Fix warnings in Data.Map and Data.Set. * Finish the started worker/wrapper transformation. * Merge all the OPTIONS and LANGUAGE module pragmas. * Remove most INLINE from Map, Set, IntMap and IntSet. * Comment tests and benchmarks on foldlWithKey' * Worker/wrapper transformation for Data.IntSet. * Compile only the benchmark source, not the Data/*.hs. * Add criterion-based benchmark for IntSet.hs * Add a testsuite for Data.IntSet. * Further improve Data.Set balance function * Further improve Data.Map balance function * Changing delta to 3 in Data.Set. * Changing delta to 3 in Data.Map. * Correct Data.Set Arbitrary instance never to return unbalanced trees. * Correct Data.Map Arbitrary instance never to return unbalanced trees. * Improve Data.Set benchmark. * Improve benchmark infrastructure and Data.Map benchmark * Improve the performance of Data.Set balance function * Improve the performance of Data.Map balance function. * Improve performance of Data.Set union and difference operations * Improve performance of Data.Map union* and difference operations * Make the Set store the elements evaluated (bang added). Have *any* of these patches been proposed for review? containers is a critical library, and under libraries@ maintainance. This is not what you do prior to a release. Ian, Simon M.: did you get a chance to sign off on this? -- Don

5 8

Re: [GHC] #4277: Proposal: Significant performance improvements for Data.Map
by Don Stewart 25 Sep '10

25 Sep '10

This didn't follow the libraries process at all, and I've not actually seen the final patch. I understand the release deadlines are coming up, but clobbering the workflow like this is frustrating. Where is the final patch for review? Did Milan decide for us? -- Don ----- Forwarded message from GHC <cvs-ghc(a)haskell.org> ----- Date: Fri, 24 Sep 2010 16:49:04 -0000 From: GHC <cvs-ghc(a)haskell.org> Cc: glasgow-haskell-bugs(a)haskell.org Subject: Re: [GHC] #4277: Proposal: Significant performance improvements for Data.Map #4277: Proposal: Significant performance improvements for Data.Map --------------------------------------+------------------------------------- Reporter: dons | Owner: dons Type: proposal | Status: closed Priority: normal | Milestone: Component: libraries (other) | Version: 6.12.3 Resolution: fixed | Keywords: map, containers Testcase: | Blockedby: Difficulty: | Os: Unknown/Multiple Blocking: 4278, 4311 | Architecture: Unknown/Multiple Failure: Runtime performance bug | --------------------------------------+------------------------------------- Changes (by milan): * status: new => closed * resolution: => fixed Comment: Applied with INLINE => INLINABLE changes. --

3 2

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

25 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