Why can't Haskell be faster?

[pmatos]

Hello all,

I, along with some friends, have been looking to Haskell lately. I'm
very happy with Haskell as a language, however, a friend sent me the
link:
http://shootout.alioth.debian.org/gp4/

which enables you compare several language implementations. Haskell
seems to lag behind of Clean.
>From what I've seen of Clean it seems almost like Haskell. It even
distributes a Haskell->Clean translator so the obvious question is,
why is Haskell slower?
Being similar languages and being GHC a very good compiler, can't it
get at least as fast as Clean?

What am I missing here? (I wrote this mail assuming the results from
the URL are trustworthy).

Cheers,

--
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

[manu-30]

>> From what I've seen of Clean it seems almost like Haskell. It even
>>
> distributes a Haskell->Clean translator so the obvious question is,
> why is Haskell slower?
>

It's also something I've wondered about, and I'm curious about the  
answer...

One of the differences between Haskell and Clean is how side-effects  
are allowed
(Uniqueness Types for Clean, and Monadic I/O for Haskell)

GHC also supports a lot of extensions beyong Haskell98.

Does it explain the difference in performances ? I don't know...

Experts please !


Manu


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

[Adrian Hey]

Paulo J. Matos wrote:

> Hello all,
>
> I, along with some friends, have been looking to Haskell lately. I'm
> very happy with Haskell as a language, however, a friend sent me the
> link:
> http://shootout.alioth.debian.org/gp4/
>
> which enables you compare several language implementations. Haskell
> seems to lag behind of Clean.
>>From what I've seen of Clean it seems almost like Haskell. It even
> distributes a Haskell->Clean translator so the obvious question is,
> why is Haskell slower?
> Being similar languages and being GHC a very good compiler, can't it
> get at least as fast as Clean?
>
> What am I missing here? (I wrote this mail assuming the results from
> the URL are trustworthy).

I don't know for certain that this is still the case (and if so why).
But I do remember that when I was a Clean user a few years ago both
the Clean compiler and the resulting executables were amazingly fast
(certainly by FPL standards).

I've often thought it's a real shame that two different but very
similar languages exist. I think that the Clean compiler would
be one of the best if not *the* best Haskell implementations available,
apart from minor snag that it isn't Haskell at all :-)

As things are at the moment ghc has no serious competition so we don't
really know how fast it "should be". Maybe this will change in future.

BTW, the reason I still jumped ship in the end and became a Haskell
user instead had nothing to do with performance. The reason was that if
I was going to invest a lot of time in progs/libs I wanted to have some
confidence I'd made the right choice long term and I had issues with the
Clean approach to concurrency (what the Clean folk call "deterministic
concurrency"). I didn't (and still don't) see this as viable, but during
a long and heated flame war on the Clean mailing list it became clear
that the Clean team did not agree with my point of view, so things
were not likely to change any time soon :-(

Regards
--
Adrian Hey
















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

[Peter Hercek]

I'm curious what experts think too.

So far I just guess it is because of clean type system getting
  better hints for optimizations:

* it is easy to mark stuff strict (even in function signatures
  etc), so it is possible to save on unnecessary CAF creations

* uniqueness types allow to do in-place modifications (instead
  of creating a copy of an object on heap and modifying the copy),
  so you save GC time and also improve cache hit performance

Peter.

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

[Peter Hercek]

Add to that better unbox / box annotations, this may make even
  bigger difference than the strictness stuff because it allows
  you to avoid a lot of indirect references do data.

Anyway, if Haskell would do some kind of whole program analyzes
  and transformations it probably can mitigate all the problems
  to a certain degree.

So the slowness of Haskell (compared to Clean) is consequence of
  its type system. OK, I'll stop, I did not write Clean nor Haskell
  optimizers or stuff like that :-D

Peter.

Peter Hercek wrote:

> I'm curious what experts think too.
>
> So far I just guess it is because of clean type system getting
>  better hints for optimizations:
>
> * it is easy to mark stuff strict (even in function signatures
>  etc), so it is possible to save on unnecessary CAF creations
>
> * uniqueness types allow to do in-place modifications (instead
>  of creating a copy of an object on heap and modifying the copy),
>  so you save GC time and also improve cache hit performance
>
> Peter.

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

[Dougal Stanton]

On 31/10/2007, Peter Hercek <peter@...> wrote:

> Anyway, if Haskell would do some kind of whole program analyzes
>   and transformations it probably can mitigate all the problems
>   to a certain degree.
>

I think JHC is supposed to do whole-program optimisations. Rumour has
it that its Hello World examples are the fastest around - I have heard
it has problems with larger code bases though. ;-) What's the current
state of play on this?

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

[pmatos]

On 31/10/2007, Peter Hercek <peter@...> wrote:
> Add to that better unbox / box annotations, this may make even
>   bigger difference than the strictness stuff because it allows
>   you to avoid a lot of indirect references do data.
>
> Anyway, if Haskell would do some kind of whole program analyzes
>   and transformations it probably can mitigate all the problems
>   to a certain degree.
>

So, I might assert that it is not a problem of the Haskell language
itself, it is a problem with the compiler. Which means that with
enough effort it would be possible for the compiler to generate
compiled code with performance as good as Clean.

> So the slowness of Haskell (compared to Clean) is consequence of
>   its type system. OK, I'll stop, I did not write Clean nor Haskell
>   optimizers or stuff like that :-D
>

type system? Why is that? Shouldn't type system in fact speed up the
generated code, since it will know all types at compile time?

> Peter.
>
> Peter Hercek wrote:
> > I'm curious what experts think too.
> >
> > So far I just guess it is because of clean type system getting
> >  better hints for optimizations:
> >
> > * it is easy to mark stuff strict (even in function signatures
> >  etc), so it is possible to save on unnecessary CAF creations
> >
> > * uniqueness types allow to do in-place modifications (instead
> >  of creating a copy of an object on heap and modifying the copy),
> >  so you save GC time and also improve cache hit performance
> >
> > Peter.
>
> _______________________________________________
> 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

[Reinier Lamers]

Paulo J. Matos wrote:

>>So the slowness of Haskell (compared to Clean) is consequence of
>>  its type system. OK, I'll stop, I did not write Clean nor Haskell
>>  optimizers or stuff like that :-D
>>
>>    
>>
>
>type system? Why is that? Shouldn't type system in fact speed up the
>generated code, since it will know all types at compile time?
>  
>

Yes, but apparently the Clean type system gives more information to the
compiler than the Haskell system does. The Haskell type system doesn't
say that a certain value can be updated in-place or that a certain value
should not be boxed (not counting the GHC extension for unboxed types).

Reinier

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

[Jules Bean]

Paulo J. Matos wrote:
> type system? Why is that? Shouldn't type system in fact speed up the
> generated code, since it will know all types at compile time?

The *existence* of a type system is helpful to the compiler.

Peter was referring to the differences between haskell and clean.

Specifically, clean's uniqueness types allow for a certain kind of
zero-copy mutation optimisation which is much harder for a haskell
compiler to automatically infer. It's not clear to me that it's actually
worth it, but I think that's the point at issue. I can *imagine*
algorithms in which copying is actually faster than mutation, if copying
gives you better locality.

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

[greenrd]

On Wed, 31 Oct 2007 14:17:13 +0000
Jules Bean <jules@...> wrote:

> Specifically, clean's uniqueness types allow for a certain kind of
> zero-copy mutation optimisation which is much harder for a haskell
> compiler to automatically infer. It's not clear to me that it's
> actually worth it, but I think that's the point at issue. I can
> *imagine* algorithms in which copying is actually faster than
> mutation, if copying gives you better locality.

If you want in-place update in Haskell, you can use the ST monad, or
IORefs. Yes, you have to refactor code, but anecdotally, uniqueness
types aren't without problems either - you can make one small change
and your code no longer satisfies the uniqueness condition.
--
Robin
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Jules Bean]

Robin Green wrote:

> On Wed, 31 Oct 2007 14:17:13 +0000
> Jules Bean <jules@...> wrote:
>
>> Specifically, clean's uniqueness types allow for a certain kind of
>> zero-copy mutation optimisation which is much harder for a haskell
>> compiler to automatically infer. It's not clear to me that it's
>> actually worth it, but I think that's the point at issue. I can
>> *imagine* algorithms in which copying is actually faster than
>> mutation, if copying gives you better locality.
>
> If you want in-place update in Haskell, you can use the ST monad, or
> IORefs. Yes, you have to refactor code, but anecdotally, uniqueness
> types aren't without problems either - you can make one small change
> and your code no longer satisfies the uniqueness condition.

IORefs don't give you in-place update.

They give you mutation, but new values are still allocated in new heap.

foo <- newIORef "hi"
writeIORef foo "bye"

-- "bye" is a new string, allocated in new heap. the only thing that got
-- mutated was a pointer.


STArrays and certain IO Arrays give you in-place update, though.

Jules

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

[Jeff.Harper]

Peter Hercek wrote:
> * it is easy to mark stuff strict (even in function signatures
>  etc), so it is possible to save on unnecessary CAF creations

Also, the Clean compiler has a strictness analyzer.  The compiler will analyze code and find many (but not all) cases where a function argument can be made strict without changing the behavior of the program.

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

[Neil Mitchell]

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.

Thanks

Neil

On 10/31/07, Jeff.Harper@... <Jeff.Harper@...> wrote:

>
> Peter Hercek wrote:
>  > * it is easy to mark stuff strict (even in function signatures
>  >  etc), so it is possible to save on unnecessary CAF creations
>
> Also, the Clean compiler has a strictness analyzer.  The compiler will
> analyze code and find many (but not all) cases where a function argument can
> be made strict without changing the behavior of the program.
>
> _______________________________________________
> 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

[Don Stewart-2]

ndmitchell:

> 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.

Yes, this was my analysis too -- its in the native code gen. Which is
perhaps the main GHC bottleneck now.

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

[Ryan Dickie]

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?

--ryan

On 10/31/07, Don Stewart <dons@...> wrote:

ndmitchell:

> 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.

Yes, this was my analysis too -- its in the native code gen. Which is
perhaps the main GHC bottleneck now.

-- Don
_______________________________________________
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

[Don Stewart-2]

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?
>

The current Clean compiler, for micro benchmarks, seems to be rather
good, yes. Any slowdown wrt. the same program in Clean could be
considered a bug in GHC...

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

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

[Sebastian Sylvan]

On 31/10/2007, Don Stewart <dons@...> wrote:

> 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?
> >
>
> The current Clean compiler, for micro benchmarks, seems to be rather
> good, yes. Any slowdown wrt. the same program in Clean could be
> considered a bug in GHC...
>
> And remember usually Haskell is competing against 'high level' languages
> like python for adoption, where we're 5-500x faster anyway...

Not so sure about that last thing. I'd love to use Haskell for
performance, in other words use it because it makes it easier to write
parallel and concurrent programs (NDP and STM mainly, though I
wouldn't mind some language support for message passing, and perhaps
Sing#-style static protocol specifications, with some high degree of
inference).

Anyway, in order for that to be reasonable I think it's important that
even the sequential code (where actual data dependencies enforce
evaluation sequence) runs very quickly, otherwise we'll lose out to
some C-based language (written with 10x the effort) again when we
start bumping into the wall of Almdahls law...


--
Sebastian Sylvan
[phone]
UIN: 44640862
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Neil Mitchell]

Hi

> 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?

No. The performance of many real world programs could be twice as fast
at least, I'm relatively sure. Clean is a good short term target, but
in the long run Haskell should be aiming for equivalence with highly
optimised C.

Thanks

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

[Dan Piponi-2]

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

[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".

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

Paulo J. Matos wrote:

> Hello all,
>
> I, along with some friends, have been looking to Haskell lately. I'm
> very happy with Haskell as a language, however, a friend sent me the
> link:
> http://shootout.alioth.debian.org/gp4/
>
> which enables you compare several language implementations. Haskell
> seems to lag behind of Clean.
> >From what I've seen of Clean it seems almost like Haskell. It even
> distributes a Haskell->Clean translator so the obvious question is,
> why is Haskell slower?
> Being similar languages and being GHC a very good compiler, can't it
> get at least as fast as Clean?
>
> What am I missing here? (I wrote this mail assuming the results from
> the URL are trustworthy).
>
> Cheers,
>
>  

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