September 2010 - Libraries

Make lines stricter to fix a space leak
by Daniel Fischer 06 Oct '10

06 Oct '10

Proposal: A stricter implementation of lines. Reason: The current implementation causes a space leak (cf. http://homepages.inf.ed.ac.uk/wadler/papers/leak/leak.ps) at least in GHC. The proposed implementation fixes the leak at the small cost of being stricter if the first _|_ in the String is the first character of a line. Discussion period: Three weeks, until 15th October (because of ICFP). Ticket: http://hackage.haskell.org/trac/ghc/ticket/4334 Cheers, Daniel

10 22

Proposal: Better power for Rational
by Daniel Fischer 04 Oct '10

04 Oct '10

Proposal: A better implementation of powers for Rational Discussion period: Three weeks, until 16^th^ October 2010 (ICFP again) Exponentiation by repeated squaring, as is used in (^) is bad for Rational since on each multiplication a gcd has to be calculated. For well-formed Rationals, the numerator and denominator are known to be coprime, hence all powers of the numerator and denominator are also coprime. To avoid superfluous work, I propose a special power function for Rationals and a rewrite rule to replace calls to (^) for Rational bases by the special function. It might also be beneficial to export the specialised function from Data.Ratio to be used if the rule doesn't fire. Proposed function and rule: ratPow :: Integral a => Rational -> a -> Rational ratPow _ e | e < 0 = error "Negative exponent" ratPow _ 0 = 1 :% 1 ratPow r 1 = r ratPow (0:%y) _ = 0 :% 1 ratPow (x:%1) e = (x^e) :% 1 ratPow (x:%y) e = (x^e) :% (y^e) {-# RULES "power/Rational" (^) = ratPow #-} Like the elimination of `gcd` from recip (#4336), this would yield a great performance boost. Cheers, Daniel

8 21

Monadic version of functions for containers (adjustM, updateWithKeyM, etc)
by Thomas DuBuisson 29 Sep '10

29 Sep '10

All, Is there a reason not to have monadic version of the functions in containers? I've a need for functions of type: adjustM :: (Monad m, Ord k) => (a -> m a) -> k -> Map k a -> m (Map k a) updateWithKeyM :: (Monad m, Ord k) => (k -> a -> m (Maybe a)) -> k -> Map k a -> m (Map k a) where adjustM can be ~ half the cost of separate insert/lookup calls and would obey the following rule: adjustM f k m == liftM (\x -> insert k x m) (f $ lookup k m ) They aren't large, but must be in the containers package due to opacity of Map/Set/etc. Perhaps someone can provide a reason for their omission? If not then I'll probably start yet-another proposal in a week or two (once the current containers proposals and my System.Random proposals have concluded). Tentatively I expect to make a patch that includes proper *M functions for Map, Set, IntMap, and IntSet. Cheers, Thomas

8 14

Re: Monadic version of functions for containers (adjustM, updateWithKeyM, etc)
by John Lato 28 Sep '10

28 Sep '10

> Message: 2 > Date: Mon, 27 Sep 2010 23:32:42 -0400 > From: Johan Tibell <johan.tibell(a)gmail.com> > Subject: Re: Monadic version of functions for containers (adjustM, > updateWithKeyM, etc) > To: Thomas DuBuisson <thomas.dubuisson(a)gmail.com> > Cc: Haskell Libraries <libraries(a)haskell.org> > Message-ID: > <AANLkTinUkkfeaHMZUi7x8Czh0CipFzS1gOK2pxp+0nv2(a)mail.gmail.com<AANLkTinUkkfeaHMZUi7x8Czh0CipFzS1gOK2pxp%2B0nv2(a)mail.gmail.com> > > > Content-Type: text/plain; charset=ISO-8859-1 > > On Mon, Sep 27, 2010 at 6:13 PM, Thomas DuBuisson > <thomas.dubuisson(a)gmail.com> wrote: > > All, > > > > Is there a reason not to have monadic version of the functions in > > containers? I've a need for functions of type: > > Ack! Haskell needs effect polymorphism. The API already has 150 > functions. How many more do we need to add if we want to cover all the > monadic versions? > More than anything else, I wish this would be solved for Haskell'. Unfortunately I don't have anything like an implementation or even a proposal. John

1 0

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