Why can't Haskell be faster?

[Don Stewart-2]

bf3:
> Are these benchmarks still up-to-date? When I started learning FP, I had
> to choose between Haskell and Clean, so I made a couple of little
> programs in both. GHC 6.6.1 with -O was faster in most cases, sometimes
> a lot faster... I don't have the source code anymore, but it was based
> on the book "The Haskell road to math & logic".

Could be in the better Haskell libraries? We only really have the
shootout programs, which are very small.
 
> However, the Clean compiler itself is really fast, which is nice, it
> reminds me to the feeling I had with Turbo Pascal under DOS :-) I find
> GHC rather slow in compilation. But that is another topic of course.

I find it comforting that GHC thinks so hard about my code. :)

-- Don
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Henning Thielemann]

On Wed, 31 Oct 2007, Dan Piponi wrote:

> But every day, while coding at work (in C++), I see situations where
> true partial evaluation would give a big performance payoff, and yet
> there are so few languages that natively support it. Of course it
> would require part of the compiler to be present in the runtime. But
> by generating code in inner loops specialised to the data at hand it
> could easily outperform C code in a wide variety of real world code. I
> know there has been some research in this area, and some commercial
> C++ products for partial evaluation have appeared, so I'd love to see
> it in an easy to use Haskell form one day.

I weakly remember an article on Hawiki about that ...

If you write

 foo :: X -> Y -> Z
 foo x =
    let bar y = ... x ... y ...
    in  bar

would this give you true partial evaluation?
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Peter Hercek]

The site claims it is quite up to date:

about Haskell GHC
The Glorious Glasgow Haskell Compilation System, version 6.6

Examples are compiled mostly in the middle of this year and
  at least -O was used. Each test has a log available. They
  are good at documenting what they do.

Peter.

Peter Verswyvelen wrote:

> Are these benchmarks still up-to-date? When I started learning FP, I had
> to choose between Haskell and Clean, so I made a couple of little
> programs in both. GHC 6.6.1 with -O was faster in most cases, sometimes
> a lot faster... I don't have the source code anymore, but it was based
> on the book "The Haskell road to math & logic".
>
> However, the Clean compiler itself is really fast, which is nice, it
> reminds me to the feeling I had with Turbo Pascal under DOS :-) I find
> GHC rather slow in compilation. But that is another topic of course.
>
> Peter
>

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

[david48]

I'd like to see Supero and Jhc - compiled examples in the language shootout.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Lennart Augustsson]

There are many ways to implement currying.  And even with GHC you can get it to do some work given one argument if you write the function the right way.  I've used this in some code where it was crucial.

But yeah, a code generator at run time is a very cool idea, and one that has been studied, but not enough.

  -- Lennart

On 10/31/07, Dan Piponi <dpiponi@...> wrote:

On 10/31/07, Neil Mitchell <ndmitchell@...> wrote:
> in the long run Haskell should be aiming for equivalence with highly
> optimised C.

Really, that's not very ambitious. Haskell should be setting its
sights higher. :-)

When I first started reading about Haskell I misunderstood what
currying was all about. I thought that if you provided one argument to
a two argument function, say, then it'd do partial evaluation. Very I
soon I was sorely let down as I discovered that it simply made a
closure that waits for the second argument to arrive so the reduction
can be carried out.

But every day, while coding at work (in C++), I see situations where
true partial evaluation would give a big performance payoff, and yet
there are so few languages that natively support it. Of course it
would require part of the compiler to be present in the runtime. But
by generating code in inner loops specialised to the data at hand it
could easily outperform C code in a wide variety of real world code. I
know there has been some research in this area, and some commercial
C++ products for partial evaluation have appeared, so I'd love to see
it in an easy to use Haskell form one day.

Just dreaming, I know...
--
Dan
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

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

[Derek Elkins]

On Wed, 2007-10-31 at 23:44 +0100, Henning Thielemann wrote:

> On Wed, 31 Oct 2007, Dan Piponi wrote:
>
> > But every day, while coding at work (in C++), I see situations where
> > true partial evaluation would give a big performance payoff, and yet
> > there are so few languages that natively support it. Of course it
> > would require part of the compiler to be present in the runtime. But
> > by generating code in inner loops specialised to the data at hand it
> > could easily outperform C code in a wide variety of real world code. I
> > know there has been some research in this area, and some commercial
> > C++ products for partial evaluation have appeared, so I'd love to see
> > it in an easy to use Haskell form one day.
>
> I weakly remember an article on Hawiki about that ...

Probably RuntimeCompilation (or something like that and linked from the
Knuth-Morris-Pratt implementation on HaWiki) written by Andrew Bromage.
>
> If you write
>
>  foo :: X -> Y -> Z
>  foo x =
>     let bar y = ... x ... y ...
>     in  bar
>
> would this give you true partial evaluation?

No.  Partial evaluation (usually) implies a heck of a lot more than what
you are trying to do.

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

[Stefan O'Rear]

On Wed, Oct 31, 2007 at 03:37:12PM +0000, Neil Mitchell wrote:

> Hi
>
> I've been working on optimising Haskell for a little while
> (http://www-users.cs.york.ac.uk/~ndm/supero/), so here are my thoughts
> on this.  The Clean and Haskell languages both reduce to pretty much
> the same Core language, with pretty much the same type system, once
> you get down to it - so I don't think the difference between the
> performance is a language thing, but it is a compiler thing. The
> uniqueness type stuff may give Clean a slight benefit, but I'm not
> sure how much they use that in their analyses.
>
> Both Clean and GHC do strictness analysis - I don't know which one
> does better, but both do quite well. I think Clean has some
> generalised fusion framework, while GHC relies on rules and short-cut
> deforestation. GHC goes through C-- to C or ASM, while Clean has been
> generating native code for a lot longer. GHC is based on the STG
> machine, while Clean is based on the ABC machine - not sure which is
> better, but there are differences there.
>
> My guess is that the native code generator in Clean beats GHC, which
> wouldn't be too surprising as GHC is currently rewriting its CPS and
> Register Allocator to produce better native code.

I don't think the register allocater is being rewritten so much as it is
being written:

stefan@stefans:/tmp$ cat X.hs
module X where

import Foreign
import Data.Int

memset :: Ptr Int32 -> Int32 -> Int -> IO ()
memset p v i = p `seq` v `seq` case i of
    0 -> return ()
    _ -> poke p v >> memset (p `plusPtr` sizeOf v) v (i - 1)
stefan@stefans:/tmp$ ghc -fbang-patterns -O2 -c -fforce-recomp -ddump-asm X.hs
...
X_zdwa_info:
        movl 8(%ebp),%eax
        testl %eax,%eax
        jne .LcH6
        movl $base_GHCziBase_Z0T_closure+1,%esi
        addl $12,%ebp
        jmp *(%ebp)
.LcH6:
        movl 4(%ebp),%ecx
        movl (%ebp),%edx
        movl %ecx,(%edx)
        movl (%ebp),%ecx
        addl $4,%ecx
        decl %eax
        movl %eax,8(%ebp)
        movl %ecx,(%ebp)
        jmp X_zdwa_info
...

Admittedly that's better than it used to be (I recall 13 memory
references last time I tested it), but still... the reason for your
performance woes should be quite obvious in that snippet.

Stefan


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

[Neil Mitchell]

Hi

> I don't think the register allocater is being rewritten so much as it is
> being written:

>From talking to Ben, who rewrote the register allocator over the
summer, he said that the new graph based register allocator is pretty
good. The thing that is holding it back is the CPS conversion bit,
which was also being rewritten over the summer, but didn't get
finished. I think these are both things which are likely to be done
for 6.10.

Thanks

Neil
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Stefan O'Rear]

On Thu, Nov 01, 2007 at 02:30:17AM +0000, Neil Mitchell wrote:

> Hi
>
> > I don't think the register allocater is being rewritten so much as it is
> > being written:
>
> >From talking to Ben, who rewrote the register allocator over the
> summer, he said that the new graph based register allocator is pretty
> good. The thing that is holding it back is the CPS conversion bit,
> which was also being rewritten over the summer, but didn't get
> finished. I think these are both things which are likely to be done
> for 6.10.

Oh, that's good news.  I look forward to a massive increase in the
performance of GHC-compiled programs, most specifically GHC itself.

Stefan


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

[Bernie Pope]

On 01/11/2007, at 2:37 AM, Neil Mitchell wrote:
>
> My guess is that the native code generator in Clean beats GHC, which
> wouldn't be too surprising as GHC is currently rewriting its CPS and
> Register Allocator to produce better native code.

I discussed this with Rinus Plasmeijer (chief designer of Clean) a  
couple of years ago, and if I remember correctly, he said that the  
native code generator in Clean was very good, and a significant  
reason why Clean produces (relatively) fast executables. I think he  
said that they had an assembly programming guru on their team.  
(Apologies to Rinus if I am mis-remembering the conversation).

At the time I was impressed by how fast Clean could recompile itself.

Cheers,
Bernie.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[ajb-2]

G'day all.

Quoting Derek Elkins <derek.a.elkins@...>:

> Probably RuntimeCompilation (or something like that and linked from the
> Knuth-Morris-Pratt implementation on HaWiki) written by Andrew Bromage.

I didn't keep a copy, but if someone wants to retrieve it from the Google
cache and put it on the new wiki (under the new licence, of course), please
do so.

Cheers,
Andrew Bromage
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Ketil Malde-3]

Don Stewart <dons@...> writes:

> goalieca:

>>    So in a few years time when GHC has matured we can expect performance to
>>    be on par with current Clean? So Clean is a good approximation to peak
>>    performance?

If I remember the numbers, Clean is pretty close to C for most
benchmarks, so I guess it is fair to say it is a good approximation to
practical peak performance.

Which proves that it is possible to write efficient low-level code in
Clean.

> And remember usually Haskell is competing against 'high level' languages
> like python for adoption, where we're 5-500x faster anyway...

Unfortunately, they replaced line counts with bytes of gzip'ed code --
while the former certainly has its problems, I simply cannot imagine
what relevance the latter has (beyond hiding extreme amounts of
repetitive boilerplate in certain languages).

When we compete against Python and its ilk, we do so for programmer
productivity first, and performance second.  LOC was a nice measure,
and encouraged terser and more idiomatic programs than the current
crop of performance-tweaked low-level stuff.

BTW, Python isn't so bad, performance wise.  Much of what I do
consists of reading some files, building up some hashes (associative
arrays or finite maps, depending on where you come from :-), and
generating some output.  Python used to do pretty well here compared
to Haskell, with rather efficient hashes and text parsing, although I
suspect ByteString IO and other optimizations may have changed that
now.

-k
--
If I haven't seen further, it is by standing in the footprints of giants
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Bulat Ziganshin-2]

Hello Lennart,

Thursday, November 1, 2007, 2:45:49 AM, you wrote:

> But yeah, a code generator at run time is a very cool idea, and one
> that has been studied, but not enough.

vm-based languages (java, c#) has runtimes that compile bytecode to
the native code at runtime

--
Best regards,
 Bulat                            mailto:Bulat.Ziganshin@...

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

[Rodrigo Queiro]

I assume the reason the switched away from LOC is to prevent
programmers artificially reducing their LOC count, e.g. by using
a = 5; b = 6;
rather than
a = 5;
b = 6;

in languages where newlines aren't syntactically significant. When
gzipped, I guess that the ";\n" string will be represented about as
efficiently as just the single semi-colon.

On 01/11/2007, Ketil Malde <ketil+haskell@...> wrote:

> Don Stewart <dons@...> writes:
>
> > goalieca:
>
> >>    So in a few years time when GHC has matured we can expect performance to
> >>    be on par with current Clean? So Clean is a good approximation to peak
> >>    performance?
>
> If I remember the numbers, Clean is pretty close to C for most
> benchmarks, so I guess it is fair to say it is a good approximation to
> practical peak performance.
>
> Which proves that it is possible to write efficient low-level code in
> Clean.
>
> > And remember usually Haskell is competing against 'high level' languages
> > like python for adoption, where we're 5-500x faster anyway...
>
> Unfortunately, they replaced line counts with bytes of gzip'ed code --
> while the former certainly has its problems, I simply cannot imagine
> what relevance the latter has (beyond hiding extreme amounts of
> repetitive boilerplate in certain languages).
>
> When we compete against Python and its ilk, we do so for programmer
> productivity first, and performance second.  LOC was a nice measure,
> and encouraged terser and more idiomatic programs than the current
> crop of performance-tweaked low-level stuff.
>
> BTW, Python isn't so bad, performance wise.  Much of what I do
> consists of reading some files, building up some hashes (associative
> arrays or finite maps, depending on where you come from :-), and
> generating some output.  Python used to do pretty well here compared
> to Haskell, with rather efficient hashes and text parsing, although I
> suspect ByteString IO and other optimizations may have changed that
> now.
>
> -k
> --
> If I haven't seen further, it is by standing in the footprints of giants
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe@...
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>

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

[Simon Peyton-Jones]

Yes, that's right.  We'll be doing a lot more work on the code generator in the rest of this year and 2008.  Here "we" includes Norman Ramsey and John Dias, as well as past interns Michael Adams and Ben Lippmeier, so we have real muscle!

Simon

| > I don't think the register allocater is being rewritten so much as it is
| > being written:
|
| >From talking to Ben, who rewrote the register allocator over the
| summer, he said that the new graph based register allocator is pretty
| good. The thing that is holding it back is the CPS conversion bit,
| which was also being rewritten over the summer, but didn't get
| finished. I think these are both things which are likely to be done
| for 6.10.
|
| Thanks
|
| Neil
| _______________________________________________
| Haskell-Cafe mailing list
| Haskell-Cafe@...
| http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Stefan Holdermans]

Bernie wrote:

> I discussed this with Rinus Plasmeijer (chief designer of Clean) a  
> couple of years ago, and if I remember correctly, he said that the  
> native code generator in Clean was very good, and a significant  
> reason why Clean produces (relatively) fast executables. I think he  
> said that they had an assembly programming guru on their team.  
> (Apologies to Rinus if I am mis-remembering the conversation).

That guru would be John van Groningen...

If I understood correctly, and I think I did, John is now working on  
a Haskell front end for the Clean compiler---which is actually quite  
interesting in the light of the present discussion.

Cheers,

   Stefan
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Stefan Holdermans]

Neil wrote:

> The Clean and Haskell languages both reduce to pretty much
> the same Core language, with pretty much the same type system, once
> you get down to it - so I don't think the difference between the
> performance is a language thing, but it is a compiler thing. The
> uniqueness type stuff may give Clean a slight benefit, but I'm not
> sure how much they use that in their analyses.

 From what I know from the Nijmegen team, having the uniqueness  
information available and actually using it for code generation does  
allow for an impressive speed-up.

The thing is: in principle, there is, I think, no reason why we can't  
do the same thing for Haskell.  Of course, the Clean languages  
exposes uniqueness types at its surface level, but that is in no way  
essential to the underlying analysis.  Exposing uniqueness types is,  
in that sense, just an alternative to monadic encapsulation of side  
effects.  So, a Haskell compiler could just implement a uniqueness  
analysis under the hood and use the results for generating code that  
does in-place updates that are guaranteed to maintain referential  
transparency.

Interestingly---but now I'm shamelessly plugging a paper of Jurriaan  
Hage, Arie Middelkoop, and myself, presented at this year's ICFP  
[*]---such an analysis is very similar to sharing analysis, which may  
be used by compilers for lazy languages to avoid unnecessary thunk  
updates.

Cheers,

   Stefan

[*] Jurriaan Hage, Stefan Holdermans, and Arie Middelkoop. A generic  
usage analysis with subeffect qualifiers. In Ralf Hinze and Norman  
Ramsey, editors, Proceedings of the 12th ACM SIGPLAN International  
Conference on Functional Programming, ICFP 2007, Freiburg, Germany,  
October 1–-3, pages 235–-246. ACM Press, 2007. http://doi.acm.org/ 
10.1145/1291151.1291189.


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

[pmatos]

On 01/11/2007, Simon Peyton-Jones <simonpj@...> wrote:
> Yes, that's right.  We'll be doing a lot more work on the code generator in the rest of this year and 2008.  Here "we" includes Norman Ramsey and John Dias, as well as past interns Michael Adams and Ben Lippmeier, so we have real muscle!
>

That's very good to know. I wonder where could I read more about
current state of the art on Haskell compilation techniques and about
the implementation of ghc in general?
Is there a book on it or maybe some group of papers that would aid me
to understand it?

Cheers,

Paulo Matos

> Simon
>
> | > I don't think the register allocater is being rewritten so much as it is
> | > being written:
> |
> | >From talking to Ben, who rewrote the register allocator over the
> | summer, he said that the new graph based register allocator is pretty
> | good. The thing that is holding it back is the CPS conversion bit,
> | which was also being rewritten over the summer, but didn't get
> | finished. I think these are both things which are likely to be done
> | for 6.10.
> |
> | Thanks
> |
> | Neil
> | _______________________________________________
> | Haskell-Cafe mailing list
> | Haskell-Cafe@...
> | http://www.haskell.org/mailman/listinfo/haskell-cafe
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe@...
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
>

--
Paulo Jorge Matos - pocm at soton.ac.uk
http://www.personal.soton.ac.uk/pocm
PhD Student @ ECS
University of Southampton, UK
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Simon Peyton-Jones]

http://hackage.haskell.org/trac/ghc/wiki/Commentary

| -----Original Message-----
| From: pocmatos@... [mailto:pocmatos@...] On Behalf Of Paulo J. Matos
| Sent: 01 November 2007 13:42
| To: Simon Peyton-Jones
| Cc: Neil Mitchell; Stefan O'Rear; Jeff.Harper@...; haskell-cafe@...
| Subject: Re: [Haskell-cafe] Re: Why can't Haskell be faster?
|
| On 01/11/2007, Simon Peyton-Jones <simonpj@...> wrote:
| > Yes, that's right.  We'll be doing a lot more work on the code generator in the rest of this year and 2008.
| Here "we" includes Norman Ramsey and John Dias, as well as past interns Michael Adams and Ben Lippmeier, so we
| have real muscle!
| >
|
| That's very good to know. I wonder where could I read more about
| current state of the art on Haskell compilation techniques and about
| the implementation of ghc in general?
| Is there a book on it or maybe some group of papers that would aid me
| to understand it?
|
| Cheers,
|
| Paulo Matos
|
| > Simon
| >
| > | > I don't think the register allocater is being rewritten so much as it is
| > | > being written:
| > |
| > | >From talking to Ben, who rewrote the register allocator over the
| > | summer, he said that the new graph based register allocator is pretty
| > | good. The thing that is holding it back is the CPS conversion bit,
| > | which was also being rewritten over the summer, but didn't get
| > | finished. I think these are both things which are likely to be done
| > | for 6.10.
| > |
| > | Thanks
| > |
| > | Neil
| > | _______________________________________________
| > | Haskell-Cafe mailing list
| > | Haskell-Cafe@...
| > | http://www.haskell.org/mailman/listinfo/haskell-cafe
| > _______________________________________________
| > Haskell-Cafe mailing list
| > Haskell-Cafe@...
| > http://www.haskell.org/mailman/listinfo/haskell-cafe
| >
| >
| >
|
|
| --
| Paulo Jorge Matos - pocm at soton.ac.uk
| http://www.personal.soton.ac.uk/pocm
| PhD Student @ ECS
| University of Southampton, UK
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Heinrich Apfelmus]

Stefan Holdermans wrote:
> Exposing uniqueness types is, in that sense, just an alternative
> to monadic encapsulation of side effects.  

While  *World -> (a, *World)  seems to work in practice, I wonder what
its (denotational) semantics are. I mean, the two programs

   loop, loop' :: *World -> ((),*World)

   loop  w = loop w
   loop' w = let (_,w') = print "x" w in loop' w'

both have denotation _|_ but are clearly different in terms of side
effects. (The example is from SPJs awkward-squad tutorial.) Any pointers?

Regards,
apfelmus

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