Re: Re: Write Haskell as fast as C. [Was: Re: GHC predictability]

andrewcoppin:
> 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)
> >
> >And the point is that it is *reliable*. If you make your money day in, 
> >day out
> >writing Haskell, and you don't want to rely on radical transformations for
> >correctness, this is a sensible idiom to follow.
> >
> >Nothing beats understanding what you're writing at all levels of 
> >abstraction.
> >  
> 
> What sets Haskell apart from every other programming language ever used 
> in mainstream programming? You might say conciseness, or the ability to 
> use lazy evaluation to structure your code in usual ways, or something 
> like that. I would say what sets Haskell apart is "abstraction". There 
> are other things, but this is the big one. Haskell allows you to 
> abstract almost everything. The result is often highly succinct yet very 
> readable programs. It would seem a terribly shame if you always have to 
> throw away Haskell's key advantage to get decent runtime performance.
> 
> If you're trying to get a real program to work, right now, then yes, you 
> may have no choice. But that doesn't mean we shouldn't strive for ways 
> to keep code high-level yet performant.
> 
> [I'm curios about your other comment. Does anybody, anywhere in the 

Re: Write Haskell as fast as C. [Was: Re: GHC predictability]

Andrew Coppin wrote:
> Bryan O'Sullivan wrote:
>> Andrew Coppin wrote:
>>  
>>> On the other hand, this is the anti-theisis of Haskell. We start with a
>>> high-level, declarative program, which performs horribly, and end up
>>> with a manually hand-optimised blob that's much harder to read but goes
>>> way faster.
>>>     
>>
>> Buh?  This is hard to read?
>>   
> 
> Look closer: it's hardER to read.
> 
>  mean xs = sum xs / fromIntegral (length xs)
> 
>  mean = go 0 0 n
>    where
>      go s l x
>        | x > m = s / fromIntegral l
>        | otherwise = go (s+x) (l+1) (x+1
> 
> One version makes it instantly clear, at a glance, what is happening. 
> The other requires you to mentally walk round a look, imperative style, 
> to figure out what's happening. It's not a *big* deal, but it's 
> unfortunate.
> 
> I'm more worried about what happens in less trivial examples. [Let's 
> face it, who wants to compute the sum of the numbers from 1 to N?]

Hm, it seems like you're expecting magic, aren't you?

Of course the first equation is easier to read, but it's no surprise 
that this may actually be slower. Like the imperative bubblesort is 
easier to read than the imperative quicksort but far slower.

Put differently, making Haskell as fast as C is easy: just write a 
slower C program! Namely one that is as easy to read as the Haskell 
version. If you implement

   mean xs = sum xs / fromIntegral (length xs)

directly in C, I bet you'll be delighted to discover that they perform 
similarly (using linked lists in the C version).

Regards,
apfelmus

Re: Re: Write Haskell as fast as C.

Andrew Coppin <andrewcoppin <at> btinternet.com> writes:

> I'm more worried about what happens in less trivial examples. [Let's
> face it, who wants to compute the sum of the numbers from 1 to N?]

Inspired by Don's blog post, and coincidentally working on a program
where profiling points to one particular, short function as
responsible for 60% of the work, I thought this would be a good time
to look into core and reveal the deep secrets of my code.  This is the
function: 

> mkAnn :: ByteString -> Annotation
> mkAnn = pick . B.words
>     where pick (_db:up:rest) = pick' up $ getGo rest
>           pick' up' (go:_:ev:_) = Ann (B.copy up') (read $ B.unpack go) (read $ B.unpack ev)
>           getGo = dropWhile (not . B.isPrefixOf (pack "GO:"))

A bit clunky, but simple enough: given a line of input, break into
words, pick word number two, the word starting with "GO:" and the
second-to-next word.  Here are the data types involved:

> data Annotation = Ann !UniProtAcc !GoTerm !EvidenceCode deriving (Show)
> newtype GoTerm = GO Int deriving (Eq,Ord)
> type UniProtAcc = ByteString
> data EvidenceCode = ... -- many nullary constructors

Unfortunately, this results in no less than four pages of core, with
tons of less intelligible identfiers and nested cases and
whatnot... any idea why this would be so slow?

-k
--

-- 
If I haven't seen further, it is by standing in the footprints of giants

Re: Write Haskell as fast as C.

Andrew Coppin <andrewcoppin <at> btinternet.com> writes:

> Look closer: it's hardER to read.
>
>  mean xs = sum xs / fromIntegral (length xs)
>
>  mean = go 0 0 n
>    where
>      go s l x
>        | x > m = s / fromIntegra l
>        | otherwise = go (s+x) (l+1) (x+1
>
> One version makes it instantly clear, at a glance, what is happening.
> The other requires you to mentally walk round a look, imperative
> style, to figure out what's happening. It's not a *big* deal, but it's
> unfortunate.

I am new to Haskell and when I first saw the two versions side by side I
too was disappointed with the second version.

But after reading the great blog post by Don, I realized that the whole
problem comes from the fact that lists in Haskell are not like arrays or
vectors in other languages: you don't know how long they are before you
have found the end.

In other words: they behave like a linked lists -- lists that are
generated lazily on demand. Because they are generated on demand you
*cannot* really know the length beforehand, and thus you *must* traverse
the list to its end to count the length.

When the list is too big to fit in memory then it's clear that the code
*must* let go of the beginning to allow the garbage collector to do its
job. You wouldn't be able to work with a 7.5 GiB linked list otherwise.

--

-- 
Martin Geisler

VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
SMPC (Secure Multi-Party Computation) to Python. See: http://viff.dk/.

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe