- Haskell-Cafe - Haskell.org

Performance question
by haskell＠kudling.de 26 Feb '09

26 Feb '09

Hi, i have compared a C++ implementation with a Haskell implementation of the Monte Carlo Pi approximation: http://lennart.kudling.de/haskellPi/ The Haskell version is 100 times slower and i wonder whether i do something obvious wrong. Profiling says that the majority of the time is spend in "main". But i have no idea where. Can someone give me a hint? Thanks, Lenny individual inherited COST CENTRE MODULE no. entries %time %alloc %time %alloc MAIN MAIN 1 0 0.0 0.0 100.0 100.0 main Main 254 1 88.1 90.8 100.0 100.0 monteCarloPi Main 255 1 0.6 1.1 11.9 9.2 pairs Main 257 10000000 0.7 1.4 0.7 1.4 countHits Main 256 10000001 4.2 2.9 10.6 6.7 accumulateHit Main 258 27852236 3.0 2.3 6.4 3.8 isInCircle Main 259 30000000 3.3 1.5 3.3 1.5 CAF:lit_r1A7 Main 248 1 0.0 0.0 0.0 0.0 isInCircle Main 260 0 0.0 0.0 0.0 0.0

10 12

Performance Issue
by James Swaine 26 Feb '09

26 Feb '09

i'm implementing a benchmark which includes a detailed specification for a random number generator. for any of the kernels outlined in the benchmark, i might have to generate a set of random numbers R, which has a length n, using the following formulas: R[k] = ((2^-46)(X[k])) mod 2^46, where X[k] = (a^k)s where the values of a and s are constant and defined below. many of the kernels in the benchmark require a large number of randoms to be generated (in the tens of millions). when i invoke the following getRandAt function that many times to build up a list, evaluation of the list takes forever (somewhere between 5 and 10 minutes). i've tried optimizing this several different ways, with no luck. i though i might post my code here and see if anyone notices anything i'm doing wrong that might be causing such a large bottleneck: --constants a :: Int64 a = 5^13 divisor :: Int64 divisor = 2^46 multiplier :: Float multiplier = 2**(-46) --gets r[k], which is the value at the kth --position in the overall sequence of --pseudorandom numbers getRandAt :: Int64 -> Int64 -> Float getRandAt 0 seed = multiplier * (fromIntegral seed) getRandAt k seed = multiplier * (fromIntegral x_next) where x_prev = (a^k * seed) `mod` divisor x_next = (a * x_prev) `mod` divisor thanks all in advance for your help! -james

4 3

Memoization local to a function
by Dusan Kolar 26 Feb '09

26 Feb '09

Dear all, I have a function a computation of which is quite expensive, it is recursively dependent on itself with respect to some other function values - we can roughly model its behaviour with fib function (returns n-th number of Fibonacci's sequence). Unfortunately, it is not fib, it is far more complicated. Nevertheless, for demonstration of my question/problem I will use fib, it's quite good. I want to store results in a list (array, with its strong size limit that I do not know prior to computation, is not suitable) and then pick them up using (!!) operator. Well, if the list is "global" function/constant then it works quite well. Unfortunately, this is not, what I would like to have. Nevertheless, local version does not work. Could someone point me to some text that explains it? Memoization text on wiki does not seem to be helpful. Time/operation consumption is deduced from number of reductions reported by hugs and winhugs (tested both on Linux and Windows). Thank you for hints, Dusan P.S. Code I used for testing. module Testmemo ( fibW , fibL , fibM ) where fibW m = allfib !! m where allfib = 0:1:[allfib!!n + allfib!!(n+1) | n <- [0..]] fibL m = let allfib = 0:1:[allfib!!n + allfib!!(n+1) | n <- [0..]] in allfib !! m fibM n = myallfib !! n myallfib = 0:1:[myallfib!!n + myallfib!!(n+1) | n <- [0..]]

5 5

Re: [Haskell-cafe] Performance question
by haskell＠kudling.de 26 Feb '09

26 Feb '09

Do you think it would be feasable to replace the GHC implementation of System.Random with something like System.Random.Mersenne? >Here is a variant that uses mersenne-random-pure64 and works less than >2x slower than C++: > > - You don't need to compute samples count an extra time > - You don't need to assemble double pairs from a list > - Notice the strictness in randomDoublePairs: it doubled performance > >{-# LANGUAGE BangPatterns #-} > >import System.Random.Mersenne.Pure64 >import System( getArgs ) >import Data.List( foldl' ) > >isInCircle :: (Double,Double) -> Bool >isInCircle (!x,!y) = sqrt (x*x + y*y) <= 1.0 > >accumulateHit :: Int -> (Double,Double) -> Int >accumulateHit !hits pair = if isInCircle pair then hits + 1 else hits > >monteCarloPi :: Int -> [(Double,Double)] -> Double >monteCarloPi n xs = 4.0 * fromIntegral hits / fromIntegral n > where hits = foldl' accumulateHit 0 . take n $ xs > >randomDoublePairs g = let > !(!x,!g') = randomDouble g > !(!y,!g'') = randomDouble g' > in (x,y):randomDoublePairs g'' > >main = do > samples <- (read . head) `fmap` getArgs > randomNumbers <- randomDoublePairs `fmap` newPureMT > putStrLn . show $ monteCarloPi samples randomNumbers > >jkff@*****:~/montecarlo$ time ./mc-hs 10000000 >3.1417088 > >real 0m1.141s >user 0m1.140s >sys 0m0.000s >jkff@*****:~/montecarlo$ time ./mc 10000000 >10000000 >3.14113 > >real 0m0.693s >user 0m0.690s >sys 0m0.000s > > > >2009/2/26 Ben Lippmeier <Ben.Lippmeier(a)anu.edu.au>: >> >> On 26/02/2009, at 9:27 PM, haskell(a)kudling.de wrote: >>> >>> Currently i can only imagine to define a data type in order to use unboxed >>> Ints instead of the accumulator tuple. >> >> That would probably help a lot. It would also help to use two separate >> Double# parameters instead of the tuple. >> >>> The thing is that i don't see in the profile output yet what to improve. >>> There are some allocations going on in "main", but i don't know what >>> causes it. >>> >>>> The first thing I would do is replace your >>>> isInCircle :: (Floating a, Ord a) => (a,a) -> Bool >>>> with >>>> isInCircle :: (Double, Double) -> Bool >>> >>> Can you point me to why that matters? >> >> At the machine level, GHC treats the (Floating a, Ord a) as an extra >> argument to the function. This argument holds function pointers that tell >it >> how to perform multiplication and <= for the unknown type 'a'. If you use >> Double instead of 'a', then it's more likely to use the actual machine op. >> >> Ben. >> >> >> _______________________________________________ >> Haskell-Cafe mailing list >> Haskell-Cafe(a)haskell.org >> http://www.haskell.org/mailman/listinfo/haskell-cafe >> > > > >-- >Eugene Kirpichov >Web IR developer, market.yandex.ru

6 6

Re: Hoogle and Network.Socket
by John Lato 26 Feb '09

26 Feb '09

> John Lato <jwlato(a)gmail.com> writes: > >> Brandon Allbery wrote: >>> On 2009 Feb 21, at 20:47, Jonathan Cast wrote: >>>> On Sat, 2009-02-21 at 07:25 -0700, John A. De Goes wrote: > >>>>> Not showing platform-specific packages by default *might* make >>>>> package writers more likely to develop cross-platform >>>>> packages. > > You're saying a developer would think, oh, I need to test this on > windows, or else Hoogle won't index it? > > I think it is way more likely that not showing platform-specific > packages will result in yet another platform-specific library > duplicating (the necessary) part of the functionality. > > On the other hand, displaying platfom-specific libraries might lead to > them being more used, and in turn being ported. I agree with both of these points. I think at least the first would be adequately addressed if Hoogle categorized results by platform compatibility in some way. Then a person looking for, e.g. a BSD-Sockets package should be able to find it more quickly. > >>>>> We've heard many times someone say, "I don't know if it >>>>> works on Windows, never really thought of that." > > I'd say it. I'd be happy to accept patches for Windows compatibility, > but I'm not going to go out and buy an OS, install it, install all the > required software and so on - just to tick a checkbox I'm not sure > anybody - a potential user of software, that is, not a user of > checkboxes - even cares about. I certainly don't expect every developer to run out and buy Windows just to test their stuff. I have access to a Windows box, and I hate testing my code on it because I have to reboot to do so. I'll freely admit it's a pain. That's not the point, though. In my experience, most haskell code works on windows, unless you have a Unix or FFI dependency. In those cases, yes, it's a lot more work to port and test. But if you don't, or could use a cross-platform equivalent, then there's a good chance your code will work on Windows *with no extra effort.* That's what I'm arguing for: making it easier to make cross-platform choices without any extra work on the developer's part. > >> 1. It's often easier (and almost never more difficult) to design for >> cross-platform support from the beginning than to add it later. > > I don't entirely agree. I have no particular experience writing > cross-platform software, and no way to test it - chances are I'd just > mess it up anyway. Better that an expert, with a real need to cater > to, do this later on. I didn't phrase this well. In the context of my argument, "design for cross-platform" meant "avoid platform-limiting choices in the absence of any compelling reasons otherwise", which really isn't the same. In the specific case of Haskell software, I argue that this goes a long way to ensuring ease of porting (if necessary at at all). Again, with very little impact on the actual work that you need to do. Note that "compelling reasons" would include better features, better API, industry standards compliance, etc. I wouldn't say that a half-implemented, poorly documented cross-platform library is functionally equivalent to an alternative well-supported product. > >> 2. As of now, the "Windows Group" seems to be mostly Duncan. And >> while I greatly appreciate all the time and effort he continues to put >> into Windows support, he's got a lot to do and could use some help. >> If you can't help by joining the Windows group, at least you could >> make your own packages cross-platform. > > If you care about Windows support, the least you can do is to install > my stuff, and mail me the required patches to make it work - or let me > know if it works already. I am most definitely not a Windows programmer, so I'm in only a slightly better position than you to make such patches if necessary. I will test your code, though. > > As far as I know, none of those 80% of users even know I exist. > In your case, I suppose that >80% of users don't care about bioinformatics, which seems to be your area of specialization. Fine. Even when coding for a broad audience, as opposed to coding for oneself, it's not true that you're coding for *everyone*. > >> 4. Cross-platform concerns are something that responsible developers >> need to consider, just like localization and i18n. I.e., why >> *shouldn't* you think of that? > > I don't consider those other two either, for about the same reasons. > I don't need it for the software I'm writing, and I have no reason to > believe anybody else does either. > > I suppose that one might think that my views here are quite selfish. > Where's the community spirit? Where is social responsibility? In a > way you'd be right, but I also think that if you start *imposing* this > kind of responsibility and community spirit, you'd start to se less > free software out there. The cost of releasing software is low, but > hell, if I'm going to be flamed for it, the cost of *not* releasing it > is not any higher. I'm really not trying to argue that this should be imposed upon developers, for exactly the reasons you give. One of the great things about hackage is the extremely low barrier to entry. I think that the "publish stuff and see what gets used" model is very effective, and I certainly don't want that to change. I do apologize if you think I'm flaming you (or anyone else). That was certainly not my intent. Honestly, I'm quite surprised that so many experienced Haskellers, all of whom have made far more contributions than I have, responded so strongly to my comments. I'm certainly not saying that I think every developer should go out of their way to actively support OS's they don't even have access to. I'm not even asking anyone to write any more code than they already feel like doing. I'm simply saying that, in the cases in which Windows compatibility can be had *for free*, the community should encourage it. I also thought that most developers would be happy to take advantage of such a situation, but it seems I was mistaken. Sincerely, John Lato

4 4

ANN: gitit 0.5.1
by John MacFarlane 26 Feb '09

26 Feb '09

I've just uploaded gitit 0.5.1 to HackageDb. Gitit is a wiki program that uses git or darcs as a filestore and HAppS as a server. Changes: * Major code reorganization, making gitit more modular. * Gitit can now optionally be built using Happstack instead of HAppS (just use -fhappstack when cabal installing). * Fixed bug with directories that had the same names as pages. * Added code from HAppS-Extra to fix cookie parsing problems. * New command-line options for --port, --debug. * New debug feature prints the date, the raw request, and the processed request data to standard output on each request. * Files with ".page" extension can no longer be uploaded. * Apostrophes and quotation marks now allowed in page names.

4 5

Grapefruit infrastructure
by Wolfgang Jeltsch 26 Feb '09

26 Feb '09

Hello, I just want to mention that the Grapefruit FRP library now has a mailing list and a Trac instance which contains a bug tracker. See: <http://www.haskell.org/haskellwiki/Grapefruit#Community> Please also note that the Grapefruit repositories have moved to code.haskell.org. Best wishes, Wolfgang

2 1

Re: [Haskell-cafe] Performance question
by haskell＠kudling.de 26 Feb '09

26 Feb '09

>accumulateHit because it doesn't need to count to total. That is >already known. Well in theory i agree. But somone could feed a non-infite number of doubles. Then the argument "n" would not necessarily be the same as the number of random number pairs really used.

1 0

Re: [Haskell-cafe] Performance question
by haskell＠kudling.de 26 Feb '09

26 Feb '09

>> But you can remove sqrt from the C++ implementation as well, so it only >> improves the relative performance if the C++ implementation of sqrt is >> worse than its Haskell counterpart. > >Oops, of course I mean, you only improve if Haskell's implementation is >worse than C++'s implementation :) Actually i intend to compare real life performance of comparable algorithms. If sqrt is a problem in GHC/Haskell then this would be a valuable result. I want to know about these problems and not work around them at this point. Thanks, lenny

1 0

popularity context with Cabal
by Manlio Perillo 26 Feb '09

26 Feb '09

Hi. Debian some time ago introduced the popularity context, to find the most installed/used packages: http://popcon.debian.org/ Is it possible to do something similar with Cabal? From popularity-context FAQ: "For each package, popularity-contest looks at the most recently used (based on atime) files, and reports the filename, its last access time (atime) and last change time (ctime). However, some files are not considered, because they have unreliable atime." "A computer 'vote' for a package if according to the data provided in the report, a program provided or depending on the package was used less than thirty days ago. This computation is performed by the popcon server." Manlio Perillo

3 2