- Libraries - Haskell.org

List fusion for IntSet.toList
by Joachim Breitner 21 Sep '11

21 Sep '11

Hi, while experimenting with the code, I noticed that toList is not set up for list fusion. I’m using IntSet.toList (and IntMap.toList) a lot inside list comprehensions, so I think I’d benefit from it. I ran a quick experiment (benchmarking (length . filter odd . DS.toList) applied to fromList [0,2..2^24], and progression gave me the attached graph – looks worth-while :-) (Yes, I know, the benchmark is very much tailored to show the best possible effect :-)) As it is really easy and straight forward, I’ll add such a rule for IntSet and for the other modules in my pull request. Greetings, Joachim -- Joachim "nomeata" Breitner mail(a)joachim-breitner.de | nomeata(a)debian.org | GPG: 0x4743206C xmpp: nomeata(a)joachim-breitner.de | http://www.joachim-breitner.de/

1 0

Faster IntSet by using BitMaps in the lower branches
by Joachim Breitner 20 Sep '11

20 Sep '11

Hi, for one of my applications, I am generating huge IntSets (and IntMaps), and I am regularly hitting the memory constraints of my machine. Hence I am looking for a better implementation of IntSets with smaller memory foot print, at least in the case of dense sets, e.g. those where it is likely that a few values are equal in all but the lower 5 or 6 bits. So instead of a simple tree, I re-implemented IntSet as a tree where the nodes contain bit maps of one machine word (32 or 64 entries): Instead of Data.IntSet> putStr $ showTree $ fromList [-3, -1,1,2,42,100] * +--* | +--* | | +--* | | | +-- 1 | | | +-- 2 | | +-- 42 | +-- 100 +--* +-- -3 +-- -1 we have Data.DenesIntSet> putStr $ showTree $ fromList [-3, -1,1,2,42,100] * +--* | +-- 0 0000000000000000000001000000000000000000000000000000000000000110 | +-- 64 0000000000000000000000000001000000000000000000000000000000000000 +-- -64 1010000000000000000000000000000000000000000000000000000000000000 The results are promising. I have attached a "progress" graph, comparing the performance of IntMap with DenseIntMap. As you can see, performance is better for most common operations, greatly better for intersection and union, and comparable for fold/filter/findMax/findMin. And here is the memory usage of an IntSet with one million members and varying distance between the entries: $ cat membench.hs import qualified Data.IntSet as S import qualified Data.DenseIntSet as DS import System.Environment main = do [what, sizeS, stepS] <- getArgs let list = [0,read stepS .. read stepS * read sizeS] if what `elem` ["r","R"] then S.size ( S.fromList list) `seq` return () else DS.size (DS.fromList list) `seq` return () For IntSet, the memory consumption does not change notably with the step size: $ ./membench +RTS -t -RTS r 1000000 1 2>&1 | perl -n -e '/, (\d+M) in use/ && print "$1\n"' 80M $ ./membench +RTS -t -RTS r 1000000 2 2>&1 | perl -n -e '/, (\d+M) in use/ && print "$1\n"' 80M $ ./membench +RTS -t -RTS r 1000000 10 2>&1 | perl -n -e '/, (\d+M) in use/ && print "$1\n"' 79M $ ./membench +RTS -t -RTS r 1000000 100 2>&1 | perl -n -e '/, (\d+M) in use/ && print "$1\n"' 79M But for DenseIntMap, we see that dense maps are, as desired, much more compact: $ ./membench +RTS -t -RTS d 1000000 1 2>&1 | perl -n -e '/, (\d+M) in use/ && print "$1\n"' 2M $ ./membench +RTS -t -RTS d 1000000 2 2>&1 | perl -n -e '/, (\d+M) in use/ && print "$1\n"' 3M $ ./membench +RTS -t -RTS d 1000000 10 2>&1 | perl -n -e '/, (\d+M) in use/ && print "$1\n"' 18M $ ./membench +RTS -t -RTS d 1000000 100 2>&1 | perl -n -e '/, (\d+M) in use/ && print "$1\n"' 77M I have put the code here: https://github.com/nomeata/containers/blob/denseintmap/Data/DenseIntSet.hs It certainly needs a bit more cleanup, e.g. documenting, commenting and maybe improving the test coverage (as, after all, I added quite a bit of logic that can now go wrong). And I did not test the code on a 32 bit system yet. But I’d like to hear from you whether this could in principle go into the containers library (as IntSet, not as DenseIntSet) or if there is a reason not to use this implementation. Thanks, Joachim -- Joachim "nomeata" Breitner mail(a)joachim-breitner.de | nomeata(a)debian.org | GPG: 0x4743206C xmpp: nomeata(a)joachim-breitner.de | http://www.joachim-breitner.de/

5 21

Re: Please apply the comparison function given to nubBy to elements of the list in the order in which they occur in the list.
by Cale Gibbard 20 Sep '11

20 Sep '11

Except that I didn't really say anything about evaluation order, I said something about the semantics of the higher order function, and what I wanted those semantics to be. Now, of course, the Report definition leaves it completely ambiguous what set of tests nubBy will perform when applied to some equivalence relation, and there's a fair amount of wiggle room in how it gets implemented because of that. Maybe some implementations are a little more efficient than others, or perform fewer tests. But that's beside the point, because I want to apply nubBy to non-equivalence relations and have it do something sensible, because the Report sample implementation of nubBy is actually *useful* when applied to more general relations. Maybe not as frequently as something like foldr, but I have a case where I want to apply it to something which isn't an equivalence relation come up maybe every couple of months, and it's really frustrating that it's undefined. It's similar to only having a 'fold' function which is formally undefined for non-associative operators, and not being able to rely on the association that it gives you. Sure, there might be cases where that actually helps a lot with performance (it's certainly crucial for parallelism), but then there will also be cases where that is totally inappropriate and ensures that you can't really use the function for your task. The one which is in GHC right now happens to be exactly what I want every time that the need arises, except that in the current version, it flips the order of arguments to the predicate, which seems to indicate that it should not hurt very badly to insert a 'flip' into its definition. An implementation of nubBy which works for an arbitrary equivalence relation and doesn't require any additional assumptions is going to be quadratic in any case. You're not going to do better than that, because in the worst case (a list with all elements non-equivalent) you have to examine every unordered pair of elements of the list. So you're at most talking about a constant factor or special case performance gain, at the cost of not specifying semantics when it would be useful to be able to rely on them. On 8 September 2011 04:03, Ramin Honary <ramin.honary(a)gmail.com> wrote: > Greetings, > It might be nice to have "nubBy" work in a way that is more intuitive to > computer scientists who expect list evaluation to work in a specific > order. Unfortunately, Haskell is quite explicit about not specifying the > order of evaluation, which can make Haskell more intuitive for > mathematicians, and less intuitive for most other people. > I don't work on GHC or on the Haskell language committee, but my > understanding is that making the "nubBy" function undefined for operations > that do not test for equality is a simplifying assumption that allows more > freedom for evaluation and optimization. Here is an overly-simple example, > but I hope it makes sense: > a = nubBy (==) ([10-5] ++ takeWhile (<5) [0..20]) > b = nubBy (==) (nubBy (==) [5] ++ takeWhile (<5) (nubBy (==) [0..20])) > According to Haskell, both 'a' and 'b' are mathematically equivalent, > because "nubBy" is a distributive and associative function. This implies > that if the compiler can somehow produce more efficient code by first > converting 'a' into 'b' and then applying optimization, it should have the > freedom to do so, and laziness guarantees that freedom. This is a poor > example because obviously 'b' couldn't possibly be easier to optimize than > 'a'. But really, who can fathom the logic of those crazy programmers who > implemented the compiler with their ridiculous (but somehow always optimal) > optimization strategies? > If you require interpretation to go by list order, then you also must > eliminate the distributive and associative properties of the "nubBy" > function. By declaring "nubBy" only work on equality operations, you > guarantee that it is associative and distributive across lists, and this > allows a host of optimization strategies to be used which would otherwise be > impossible if list-order application were required. > If list order is important for you, it is easy enough to define your own > "nubBy" function that is not distributive or associative, and can be > therefore optimized differently than when you use "Data.List.nubBy". > This blog post: > <http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html> is > about C, but the principles are the same: it has a fantastic explanation > about how "undefined behavior" can be really helpful with simplifying > compiler implementation and optimization. > I hope that makes sense, and if I said anything inaccurate, I am at the > mercy of the Haskell-prime mailing list. > > On Thu, Sep 8, 2011 at 9:07 AM, Cale Gibbard <cgibbard(a)gmail.com> wrote: >> >> I just tried this in ghci-7.0.3: >> >> ghci> nubBy (>=) [1,2,3,4] >> [1] >> >> Think about what this is doing: it is excluding 2 from the list >> because 2 >= 1, rather than including it because 1 >= 2 fails. >> >> I think an important convention when it comes to higher order >> functions on lists is that to the extent which is possible, the >> function parameters take elements from the list (or things computed >> from those) in the order in which they occur in the original list. >> >> If we reimplement it in the obvious way: >> ghci> let nubBy f [] = []; nubBy f (x:xs) = x : filter (not . f x) (nubBy >> f xs) >> ghci> nubBy (>=) [1,2,3,4] >> [1,2,3,4] >> >> I'm aware that the Report (strangely!) explicitly leaves the behaviour >> of nubBy unspecified for functions which are not equivalence >> relations, but the behaviour given by the Report implementation (the >> opposite of the current behaviour in GHC) is useful and desirable >> nonetheless. >> >> I'm sure I've written about this before. I'm not entirely sure what >> happened to the previous thread of discussion about this, but it just >> came up again for me, and I decided that I was sufficiently irritated >> by it to post again. >> >> Another thing perhaps worth pointing out is that the parameters to >> mapAccumR have always been backwards (compare it with foldr). Few >> enough people use this function that I'm fairly sure we could just >> change it without harm. >> >> - Cale >> >> _______________________________________________ >> Haskell-prime mailing list >> Haskell-prime(a)haskell.org >> http://www.haskell.org/mailman/listinfo/haskell-prime > >

1 0

Is 'Q' required in 'dataToExpQ' of 'template-haskell'?
by Roman Beslik 16 Sep '11

16 Sep '11

Hi! Why 'template-haskell.Language.Haskell.TH.Quote.dataToExpQ' does not have a type @Data a => (forall b. Data b => b -> Maybe Exp) -> a -> Exp@ ? The argument of type @a@ does not contain variables (this makes no sense), so 'Q' is not used for generating names.

1 0

Control.Monad.Writer.Strict not as strict as expected
by Matt Brown 16 Sep '11

16 Sep '11

Hello all, I've been debugging a space leak, and believe I've traced it to a chain of unevaluated calls to mappend in the bind operator for Control.Monad.Writer.Strict. I had expected these calls to be evaluated strictly by the strict Writer, but it doesn't seem to be the case. Am I understanding this correctly? If so, is this the intended behavior? Below are two example programs with runtime stats demonstrating the issue. The first uses Control.Monad.Writer.Strict, the second uses an alternative implementation that is strict in the Writer's monoid. The first runs in 78.5s with total memory 630MB. The second runs in 38.15s with total memory 237MB. FWIW, the lazy writer monad turned out to be more efficient for my program (and this example -- it runs in 9.96s with total memory 389MB, and doesn't need an increased stack size). thanks, -matt -- BEGIN writerTest.hs import Control.Monad.Writer.Strict type M = Writer [()] go :: Integer -> M () go 0 = return () go n = return () >> go (n-1) main = print $ runWriter $ go 3000000 -- END writerTest.hs -- BEGIN ./writerTest +RTS -K1G -sstderr ((),[]) 1,521,548,048 bytes allocated in the heap 654,690,520 bytes copied during GC 380,421,720 bytes maximum residency (10 sample(s)) 268,515,200 bytes maximum slop 630 MB total memory in use (0 MB lost due to fragmentation) Generation 0: 1869 collections, 0 parallel, 77.34s, 77.40s elapsed Generation 1: 10 collections, 0 parallel, 0.40s, 0.40s elapsed INIT time 0.00s ( 0.00s elapsed) MUT time 0.76s ( 0.76s elapsed) GC time 77.75s ( 77.81s elapsed) EXIT time 0.00s ( 0.11s elapsed) Total time 78.50s ( 78.56s elapsed) %GC time 99.0% (99.0% elapsed) Alloc rate 2,008,440,129 bytes per MUT second Productivity 1.0% of total user, 1.0% of total elapsed -- END -- BEGIN writerTest2.hs import Data.Monoid data Writer w a = Writer a !w runWriter (Writer a w) = (a, w) instance (Monoid w) => Monad (Writer w) where return a = Writer a mempty m >>= k = case m of Writer a w -> case k a of Writer b w' -> Writer b (w `mappend` w') type M = Writer [()] go :: Integer -> M () go 0 = return () go n = return () >> go (n-1) main = print $ runWriter $ go 3000000 -- END writerTest2.hs -- BEGIN ./writerTest2 +RTS -K1G -sstderr ((),[]) 894,148,696 bytes allocated in the heap 221,145,720 bytes copied during GC 161,143,256 bytes maximum residency (9 sample(s)) 133,479,928 bytes maximum slop 257 MB total memory in use (11 MB lost due to fragmentation) Generation 0: 1185 collections, 0 parallel, 37.57s, 37.60s elapsed Generation 1: 9 collections, 0 parallel, 0.14s, 0.14s elapsed INIT time 0.00s ( 0.00s elapsed) MUT time 0.44s ( 0.44s elapsed) GC time 37.72s ( 37.75s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 38.15s ( 38.18s elapsed) %GC time 98.8% (98.9% elapsed) Alloc rate 2,036,159,030 bytes per MUT second Productivity 1.1% of total user, 1.1% of total elapsed -- END

3 5

ANNOUNCE: time-1.4
by Ashley Yakeley 14 Sep '11

14 Sep '11

It's got NFData instances, at Herbert's prodding. -- Ashley Yakeley

1 0

Proposal: Make `NFData` a fundamental/primitive type-class (by making `deepseq` a GHC-boot package)
by Herbert Valerio Riedel 07 Sep '11

07 Sep '11

Proposal: ~~~~~~~~~ Make `NFData` a fundamental/primitive type-class (by making `deepseq` a GHC-boot package) Discussion deadline: 2 weeks. Note: This is a reboot of a previous unresolved proposal[1] by Johan Tibell with a slightly different emphasis. Current Issues: ~~~~~~~~~~~~~~~ - The `deepseq` package should not depend on `containers` and `array` (ideally `deepseq` would be merged with `base` and `containers`/`array` would define their own `NFData` instances) - Not all data types defined by "core libraries" have `NFData` instances defined (e.g. `time` and `bytestring`). The lack of such "standard" instances causes users of `deepseq` to define local orphan instances - GHC boot packages can't depend on `deepseq` as it is not a GHC-boot package yet, and thus orphan instances are required for those packages -- which would benefit in terms of maintainability[4] and efficiency[3] from being defined locally by having access to the internal representations Rationale: ~~~~~~~~~~ The principal idea this proposal is based upon is that the `NFData` type-class is similarly universal/basic/fundamental as the `Ord`, `Show`, or `Eq` type-classes are -- it might be even desirable to make `NFData` part of a future Haskell Prelude at some point and maybe even allow automatic instance derivation. Building on this idea that `NFData` is a "primitive" type-class, the next best thing that can be done relatively easy and short-term as a transitional step is to 1) make `deepseq` a GHC-boot package[2], 2) remove `deepseq`'s dependancy on `array` and `containers`, 3) move the affected instance definitions to the `array` and `containers` packages respectively, and 4) satisfy the PVP by incrementing package versions where necessary. This should provide a path of least resistance, as no packages depending on `deepseq` would have to be adapted except for maybe PVP-related version constraint widening. Moreover, this would pave the way for a future proposal to merge the `deepseq` into `base` at some later point. References: ~~~~~~~~~~~ [1]: http://hackage.haskell.org/trac/ghc/ticket/4868 [2]: http://www.haskell.org/pipermail/libraries/2010-December/015427.html [3]: http://www.haskell.org/pipermail/libraries/2010-December/015428.html [4]: http://www.haskell.org/pipermail/libraries/2011-January/015488.html -- hvr

14 21

RFC: decodeFloat
by Daniel Fischer 27 Aug '11

27 Aug '11

Occasionally, the behaviour of decodeFloat and its consequences causes concern and/or bug reports (e.g. http://hackage.haskell.org/trac/ghc/ticket/3898) The main problem is the treatment of NaNs and infinities (that it doesn't distinguish between 0.0 and -0.0 is a minor thing), which are converted as if they were ordinary finite values. Thus, for example, decodeFloat (1/0 :: Double) = (2^52,972) and consequently floor (1/0 :: Double) = 2^1024 (corresponding for round, truncate, ceiling, properFraction), significand (1/0 :: Double) = 0.5, Prelude> uncurry encodeFloat (decodeFloat (1/0 :: Float)) :: Double 3.402823669209385e38 and similar meaningless/nonsensical results for NaNs. At its type, decodeFloat :: RealFloat a => a -> (Integer, Int), I see only two reasonable options, 1. leave the behaviour as it is, just warn about the exceptional cases in the documentation, 2. let decodeFloat raise an error when its argument is a NaN or infinite. Both options have disadvantages, 1. makes it easy to get meaningless results when there's a non-finite value around, 2. incurs a nontrivial performance penalty. Paying that performance penalty when dealing only with known-to-be-good values is undesirable, but so are meaningless results. A third option would be providing both behaviours by adding a function. That could take several forms, a) leave decodeFloat as is and add safeDecodeFloat outside the RealFloat class, that would check the value first and then either raise an error on NaN/Infinity or return a Maybe (Integer, Int), b) add a function to the RealFloat class, either leave decodeFloat as is and add safeDecodeFloat with the behaviour as in a) or change decodeFloat according to 2. and add unsafeDecodeFloat with the current behaviour. The drawback of a) is that safeDecodeFloat would have to perform two checks, while with IEEE Doubles/Floats, the result could be determined by one check (which would also be simpler than each of isNaN and isInfinite). Also, which module should export it? The drawback of b) is adding a function to RealFloat, as if that wasn't big enough already. Since both behaviours allow a default definition in terms of the other, only code that by chance uses the new name would break. What would be the community's preferred way to handle this issue? Cheers, Daniel

4 4

Proposal: Add Data.Bits.popCount
by Johan Tibell 25 Aug '11

25 Aug '11

Hi! Now when we have a fast popCnt# primop* it would be nice to expose it to the world through an official API. I propose we add this method to the Bits class in Data.Bits: -- | Return the number of set bits in the argument, know as the -- population count or the Hamming weight. popCount :: a -> Int I will provide a default implementation, which means that this change won't break any existing user defined instances. All the instances for the basic types (Ints, Words, etc) will use the primops. * These primops compile to a single POPCNT instruction if the user compile using -msse4.2 and a fast lookup table based implementation otherwise. Discussion period: 2 weeks Cheers, Johan

8 10

Adding unsafeShiftL, unsafeShiftR to Data.Bits(Bits)
by Simon Marlow 25 Aug '11

25 Aug '11

Johan Tibell has proposed that we add unsafeShiftL and unsafeShiftR methods to the Bits class, as per the patch here: http://hackage.haskell.org/trac/ghc/attachment/ticket/5414/0001-Add-unsafeS… I've talked this through with Johan, and we came to the conclusion that while "unsafeShiftL" is a bit unsightly, this is the most workable solution. For example, optimising away the test in shiftL directly in the backend is not possible when compiling via LLVM, which only provides the unsafe operation as a primitive. Any objections before I push this in? Cheers, Simon

5 4