[Haskell-cafe] Re: Write Haskell as fast as C. [Was: Re: GHC
flippa at flippac.org
Fri May 16 17:42:07 EDT 2008
On Fri, 16 May 2008, Don Stewart wrote:
> I don't understand what's ugly about:
> go s l x | x > m = s / fromIntegral l
> | otherwise = go (s+x) (l+1) (x+1)
I suspect you've been looking at low-level code too long. How about the
total lack of domain concepts?
mean n m = let (sum, length, _) = go (0,0,n)
in sum / fromIntegral length
go :: (Double, Int, Double) -> (Double, Int, Double)
go t@(s,l,x) | x > m = t
| otherwise = go (s+x) (l+1) (x+1)
as a starting point. I might consider generalising to a "while" HOF while
I'm at it, because ultimately this is a while loop. Admittedly that would
be relying on the implementation doing a little inlining, which you're not
Given the audience it'd be good to see some of the working to pull it off
via fusion in a comment too:
-- [1 .. d ] = unfoldr (let f n | n > d = Nothing
-- f n = Just (n,n+1) in f) 1
-- sum = foldr ...
-- length = foldr ...
-- sumAndLength = foldr ... (as calculated from the above)
-- mean [1 .. d] = s / l where
-- (sum, length) = sumAndLength [1 .. d]
-- = sumAndLength . unfoldr ...
-- = foldr ... . unfoldr ...
-- = ...
Some things it might be nice to have and/or know about:
* We really ought to be able to build the sumAndLength fold by building
the appropriate tuple and tuple function from its components - with there
being a standard idiom for naming them, and a library of such things to
hand. Same thing for go, too - this means we retain the domain concepts in
its implementation by default. The interesting thing about go is that we
ourselves running the guts of an unfold at the same time, which means it
supplies our termination criteria - I suspect I ought to post a 'most
general' form of go on that basis soon?
* Does nesting unboxed tuples work appropriately?
I was about to suggest a standard way of doing the wiring for the tupling
as well, but so long as nesting unboxed tuples works and the optimiser
'gets it' then there's an arrow instance that ought to do nicely!
While not quite as low-level, the resulting code should hopefully be easy
bait for GHC's optimiser (if not, someone please yell!), while both
retaining much of the domain info of the original code and conveying much
about how it's made to go fast.
> Nothing beats understanding what you're writing at all levels of abstraction.
How about ensuring that a casual reader can do the same quickly?
flippa at flippac.org
Performance anxiety leads to premature optimisation
More information about the Haskell-Cafe