Can Haskell outperform C++?

[Janek S.]

Hi,

a couple of times I've encountered a statement that Haskell programs can have performance
comparable to programs in C/C++. I've even read that thanks to functional nature of Haskell,
compiler can reason and make guarantess about the code and use that knowledge to automatically
parallelize the program without any explicit parallelizing commands in the code. I haven't seen
any sort of evidence that would support such claims. Can anyone provide a code in Haskell that
performs better in terms of execution speed than a well-written C/C++ program? Both Haskell and C
programs should implement the same algorithm (merge sort in Haskell outperforming bubble sort in
C doesn't count), though I guess that using Haskell-specific idioms and optimizations is of
course allowed.

Jan

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Ivan Lazar Miljenovic]

On 6 May 2012 16:40, Janek S. <[hidden email]> wrote:

> Hi,
>
> a couple of times I've encountered a statement that Haskell programs can have performance
> comparable to programs in C/C++. I've even read that thanks to functional nature of Haskell,
> compiler can reason and make guarantess about the code and use that knowledge to automatically
> parallelize the program without any explicit parallelizing commands in the code. I haven't seen
> any sort of evidence that would support such claims. Can anyone provide a code in Haskell that
> performs better in terms of execution speed than a well-written C/C++ program? Both Haskell and C
> programs should implement the same algorithm (merge sort in Haskell outperforming bubble sort in
> C doesn't count), though I guess that using Haskell-specific idioms and optimizations is of
> course allowed.

How about http://donsbot.wordpress.com/2007/11/29/use-those-extra-cores-and-beat-c-today-parallel-haskell-redux/
?

--
Ivan Lazar Miljenovic
[hidden email]
http://IvanMiljenovic.wordpress.com

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Artur]

On 06.05.2012 10:44, Ivan Lazar Miljenovic wrote:

> On 6 May 2012 16:40, Janek S.<[hidden email]>  wrote:
>> Hi,
>>
>> a couple of times I've encountered a statement that Haskell programs can have performance
>> comparable to programs in C/C++. I've even read that thanks to functional nature of Haskell,
>> compiler can reason and make guarantess about the code and use that knowledge to automatically
>> parallelize the program without any explicit parallelizing commands in the code. I haven't seen
>> any sort of evidence that would support such claims. Can anyone provide a code in Haskell that
>> performs better in terms of execution speed than a well-written C/C++ program? Both Haskell and C
>> programs should implement the same algorithm (merge sort in Haskell outperforming bubble sort in
>> C doesn't count), though I guess that using Haskell-specific idioms and optimizations is of
>> course allowed.
> How about http://donsbot.wordpress.com/2007/11/29/use-those-extra-cores-and-beat-c-today-parallel-haskell-redux/
> ?
>

Hi,

  isn't it that particular Haskell code is outperforming C (22 seconds
vs. 33), just because the author uses recursion in C? I surely love
Haskell, and the way it's code is easy parallelized, but that example
seams not fair.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Yves Parès-3]

I do not agree: the fib function is tail-recursive, any good C compiler is able to optimize away the calls and reduce it to a mere loop.
At least that's what I learnt about tail recursion in C with GCC.

2012/5/6 Artur <[hidden email]>

On <a href="tel:06.05.2012%2010" value="[phone]" target="_blank">06.05.2012 10:44, Ivan Lazar Miljenovic wrote:

On 6 May 2012 16:40, Janek S.<[hidden email]>  wrote:

Hi,

a couple of times I've encountered a statement that Haskell programs can have performance
comparable to programs in C/C++. I've even read that thanks to functional nature of Haskell,
compiler can reason and make guarantess about the code and use that knowledge to automatically
parallelize the program without any explicit parallelizing commands in the code. I haven't seen
any sort of evidence that would support such claims. Can anyone provide a code in Haskell that
performs better in terms of execution speed than a well-written C/C++ program? Both Haskell and C
programs should implement the same algorithm (merge sort in Haskell outperforming bubble sort in
C doesn't count), though I guess that using Haskell-specific idioms and optimizations is of
course allowed.

How about http://donsbot.wordpress.com/2007/11/29/use-those-extra-cores-and-beat-c-today-parallel-haskell-redux/
?

Hi,

 isn't it that particular Haskell code is outperforming C (22 seconds vs. 33), just because the author uses recursion in C? I surely love Haskell, and the way it's code is easy parallelized, but that example seams not fair.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Roman Cheplyaka-2]

It is not tail-recursive.

* Yves Parès <[hidden email]> [2012-05-06 10:58:45+0200]

> I do not agree: the fib function is tail-recursive, any good C compiler is
> able to optimize away the calls and reduce it to a mere loop.
> At least that's what I learnt about tail recursion in C with GCC.
>
> 2012/5/6 Artur <[hidden email]>
>
> > On 06.05.2012 10:44, Ivan Lazar Miljenovic wrote:
> >
> >> On 6 May 2012 16:40, Janek S.<[hidden email]>  wrote:
> >>
> >>> Hi,
> >>>
> >>> a couple of times I've encountered a statement that Haskell programs can
> >>> have performance
> >>> comparable to programs in C/C++. I've even read that thanks to
> >>> functional nature of Haskell,
> >>> compiler can reason and make guarantess about the code and use that
> >>> knowledge to automatically
> >>> parallelize the program without any explicit parallelizing commands in
> >>> the code. I haven't seen
> >>> any sort of evidence that would support such claims. Can anyone provide
> >>> a code in Haskell that
> >>> performs better in terms of execution speed than a well-written C/C++
> >>> program? Both Haskell and C
> >>> programs should implement the same algorithm (merge sort in Haskell
> >>> outperforming bubble sort in
> >>> C doesn't count), though I guess that using Haskell-specific idioms and
> >>> optimizations is of
> >>> course allowed.
> >>>
> >> How about http://donsbot.wordpress.com/**2007/11/29/use-those-extra-**
> >> cores-and-beat-c-today-**parallel-haskell-redux/<http://donsbot.wordpress.com/2007/11/29/use-those-extra-cores-and-beat-c-today-parallel-haskell-redux/>
> >> ?
> >>
> >>  Hi,
> >
> >  isn't it that particular Haskell code is outperforming C (22 seconds vs.
> > 33), just because the author uses recursion in C? I surely love Haskell,
> > and the way it's code is easy parallelized, but that example seams not fair.
> >
> >
> > ______________________________**_________________
> > Haskell-Cafe mailing list
> > [hidden email]
> > http://www.haskell.org/**mailman/listinfo/haskell-cafe<http://www.haskell.org/mailman/listinfo/haskell-cafe>
> >

> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe


--
Roman I. Cheplyaka :: http://ro-che.info/

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Yves Parès-3]

Sorry sorry sorry ^^
I read too fast and realized I was wrong before you sent this.

Okay so then it would be nice that somewhere with higher skills tells us where does Haskell recursive calls stand when compared to C's.

2012/5/6 Roman Cheplyaka <[hidden email]>

It is not tail-recursive.

* Yves Parès <[hidden email]> [2012-05-06 10:58:45+0200]

> I do not agree: the fib function is tail-recursive, any good C compiler is
> able to optimize away the calls and reduce it to a mere loop.
> At least that's what I learnt about tail recursion in C with GCC.
>
> 2012/5/6 Artur <[hidden email]>
>
> > On <a href="tel:06.05.2012%2010" value="[phone]">06.05.2012 10:44, Ivan Lazar Miljenovic wrote:
> >
> >> On 6 May 2012 16:40, Janek S.<[hidden email]>  wrote:
> >>
> >>> Hi,
> >>>
> >>> a couple of times I've encountered a statement that Haskell programs can
> >>> have performance
> >>> comparable to programs in C/C++. I've even read that thanks to
> >>> functional nature of Haskell,
> >>> compiler can reason and make guarantess about the code and use that
> >>> knowledge to automatically
> >>> parallelize the program without any explicit parallelizing commands in
> >>> the code. I haven't seen
> >>> any sort of evidence that would support such claims. Can anyone provide
> >>> a code in Haskell that
> >>> performs better in terms of execution speed than a well-written C/C++
> >>> program? Both Haskell and C
> >>> programs should implement the same algorithm (merge sort in Haskell
> >>> outperforming bubble sort in
> >>> C doesn't count), though I guess that using Haskell-specific idioms and
> >>> optimizations is of
> >>> course allowed.
> >>>

> >> How about http://donsbot.wordpress.com/**2007/11/29/use-those-extra-**
> >> cores-and-beat-c-today-**parallel-haskell-redux/<http://donsbot.wordpress.com/2007/11/29/use-those-extra-cores-and-beat-c-today-parallel-haskell-redux/>

> >> ?
> >>
> >>  Hi,
> >
> >  isn't it that particular Haskell code is outperforming C (22 seconds vs.
> > 33), just because the author uses recursion in C? I surely love Haskell,
> > and the way it's code is easy parallelized, but that example seams not fair.
> >
> >

> > ______________________________**_________________
> > Haskell-Cafe mailing list
> > [hidden email]
> > http://www.haskell.org/**mailman/listinfo/haskell-cafe<http://www.haskell.org/mailman/listinfo/haskell-cafe>

> >

> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe

--
Roman I. Cheplyaka :: http://ro-che.info/

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Roman Cheplyaka-2]

* Artur <[hidden email]> [2012-05-06 11:41:58+0300]
>  isn't it that particular Haskell code is outperforming C (22 seconds
> vs. 33), just because the author uses recursion in C? I surely love
> Haskell, and the way it's code is easy parallelized, but that example
> seams not fair.

I think the point was to take two programs of similar code complexity
(or, rather, simplicity) implementing the same algorithm (modulo
parallelism).

So I'm not sure what exactly you're objecting to.

If you're saying that there are better algorithms to compute Fibonacci
numbers, it's not relevant — the important thing that the two
programs are computing the same thing in the same way.

If you're saying that in C an explicit stack should have been used
instead of recursion, then it would increase the code complexity while
having non-obvious performance benefits.

In any case, assuming that on this particular task Haskell is x times
slower than C, taking sufficiently many cores and large enough N would
outweigh that.

The again, I don't think that article was meant as a fair comparison
between Haskell and C on an average task. (The chosen example consists of
one loop which is easily parallelisable.) All it demonstrates is that
it is very easy to exploit parallelism in Haskell when there's an
opportunity.

--
Roman I. Cheplyaka :: http://ro-che.info/

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Austin Seipp]

In this case it doesn't matter; while it isn't technically tail
recursive, GCC is very capable of transforming it into a direct loop
likely because it knows about the associative/commutative properties
of "+" so it's able to re-arrange the body as it sees fit since
combined, both calls are in 'tail position.'

With GCC 4.6.3 at -O3 optimization level on my Ubuntu 12.04 machine,
the example in the linked article executes in 9s (Intel Core i5-2520M
CPU @ 2.50GHz, dual core with 4 total logical cores) and the body of
fib does no contain any call instructions - in fact, it seems to not
only transform the body into a loop, but unroll a very good portion of
it leading to very very fast code.

Technically, if you want to be a pedant, the benchmarks aren't even
equivalent anyway; GCC is able to use the native 'long long' datatype
while GHC promotes the results of 'fib' to Integer, and thus is backed
by GMP and a lot of extra code. GMP is fast, but it's not as fast as a
native data type. It should use Int64.That change alone speeds up the
benchmark by approximately 30% for me using GHC 7.4.1 (~30s at -N4 vs
~19s at -N4.)

I don't think the point of that post was to outwit the C compiler, but
show how easy it is to add parallelism to a Haskell program
(ironically, pseq/par has proven quite difficult to leverage for nice
wall-clock speedups in practice, hence the advent of libraries like
strategies and more recently monad-par, that make speedups easier to
get.) I do think it's much easier to add parallelism to Haskell
programs - even if they are not as fast, it's far easier to write,
understand, and safer to do so. And ultimately all this code is very
old (5+ years) and not reflective of either toolchain anymore. GHC has
had immesurable amounts of overhauls in its parallelism support as
well as the libraries supporting it, and both GHC and GCC have far
better optimisation capabilities.

On Sun, May 6, 2012 at 4:09 AM, Roman Cheplyaka <[hidden email]> wrote:

> It is not tail-recursive.
>
> * Yves Parès <[hidden email]> [2012-05-06 10:58:45+0200]
>> I do not agree: the fib function is tail-recursive, any good C compiler is
>> able to optimize away the calls and reduce it to a mere loop.
>> At least that's what I learnt about tail recursion in C with GCC.
>>
>> 2012/5/6 Artur <[hidden email]>
>>
>> > On 06.05.2012 10:44, Ivan Lazar Miljenovic wrote:
>> >
>> >> On 6 May 2012 16:40, Janek S.<[hidden email]>  wrote:
>> >>
>> >>> Hi,
>> >>>
>> >>> a couple of times I've encountered a statement that Haskell programs can
>> >>> have performance
>> >>> comparable to programs in C/C++. I've even read that thanks to
>> >>> functional nature of Haskell,
>> >>> compiler can reason and make guarantess about the code and use that
>> >>> knowledge to automatically
>> >>> parallelize the program without any explicit parallelizing commands in
>> >>> the code. I haven't seen
>> >>> any sort of evidence that would support such claims. Can anyone provide
>> >>> a code in Haskell that
>> >>> performs better in terms of execution speed than a well-written C/C++
>> >>> program? Both Haskell and C
>> >>> programs should implement the same algorithm (merge sort in Haskell
>> >>> outperforming bubble sort in
>> >>> C doesn't count), though I guess that using Haskell-specific idioms and
>> >>> optimizations is of
>> >>> course allowed.
>> >>>
>> >> How about http://donsbot.wordpress.com/**2007/11/29/use-those-extra-**
>> >> cores-and-beat-c-today-**parallel-haskell-redux/<http://donsbot.wordpress.com/2007/11/29/use-those-extra-cores-and-beat-c-today-parallel-haskell-redux/>
>> >> ?
>> >>
>> >>  Hi,
>> >
>> >  isn't it that particular Haskell code is outperforming C (22 seconds vs.
>> > 33), just because the author uses recursion in C? I surely love Haskell,
>> > and the way it's code is easy parallelized, but that example seams not fair.
>> >
>> >
>> > ______________________________**_________________
>> > Haskell-Cafe mailing list
>> > [hidden email]
>> > http://www.haskell.org/**mailman/listinfo/haskell-cafe<http://www.haskell.org/mailman/listinfo/haskell-cafe>
>> >
>
>> _______________________________________________
>> Haskell-Cafe mailing list
>> [hidden email]
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
> --
> Roman I. Cheplyaka :: http://ro-che.info/
>
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe

--
Regards,
Austin

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Artur]

Well, I believe that comparison is about solving a task, not writing code in some particular way. I get your point, but I think that when comparing language speed, you should use the best techniques each one has to offer, it makes no sense otherwise.

If there was some kind of comparison made recently between Haskell and C++, I'd be really glad to read a report. I like Haskell much more than C++, and it'd be good to know, how write code in Haskell of speed equal or greater to that of C++ (at least in some typical functional language tasks, like math and data processing).

On Sun, May 6, 2012 at 12:23 PM, Roman Cheplyaka <[hidden email]> wrote:

* Artur <[hidden email]> [2012-05-06 11:41:58+0300]

>  isn't it that particular Haskell code is outperforming C (22 seconds
> vs. 33), just because the author uses recursion in C? I surely love
> Haskell, and the way it's code is easy parallelized, but that example
> seams not fair.

I think the point was to take two programs of similar code complexity
(or, rather, simplicity) implementing the same algorithm (modulo
parallelism).

So I'm not sure what exactly you're objecting to.

If you're saying that there are better algorithms to compute Fibonacci
numbers, it's not relevant — the important thing that the two
programs are computing the same thing in the same way.

If you're saying that in C an explicit stack should have been used
instead of recursion, then it would increase the code complexity while
having non-obvious performance benefits.

In any case, assuming that on this particular task Haskell is x times
slower than C, taking sufficiently many cores and large enough N would
outweigh that.

The again, I don't think that article was meant as a fair comparison
between Haskell and C on an average task. (The chosen example consists of
one loop which is easily parallelisable.) All it demonstrates is that
it is very easy to exploit parallelism in Haskell when there's an
opportunity.

--
Roman I. Cheplyaka :: http://ro-che.info/

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Jerzy Karczmarczuk]

Roman Cheplyaka:
> If you're saying that in C an explicit stack should have been used
> instead of recursion, then it would increase the code complexity while
> having non-obvious performance benefits.
This is a fragment of a bigger message I won't comment.

But THIS is a little dubious. You may accuse anything of anything by
such vacuous statements as "non-obvious performance benefits". If the
stack frame allocation policy is lousy (not because of incompetence of
the compiler writers, but because of its "universalism"), then the gain
may be quite visible. My favourite examples are the classical "flood
fill" algorithms for filling closed regions in computer graphics, and
also some models of percolation (finding paths in rather big graphs).
Everything depends on the language used, but I have seen  the
acceleration by a factor of 5 after having replaced the recursion by
explicit stacks + loops.

Jerzy Karczmarczuk



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Ertugrul Söylemez]

"Janek S." <[hidden email]> wrote:

> a couple of times I've encountered a statement that Haskell programs
> can have performance comparable to programs in C/C++. I've even read
> that thanks to functional nature of Haskell, compiler can reason and
> make guarantess about the code and use that knowledge to automatically
> parallelize the program without any explicit parallelizing commands in
> the code. I haven't seen any sort of evidence that would support such
> claims. Can anyone provide a code in Haskell that performs better in
> terms of execution speed than a well-written C/C++ program? Both
> Haskell and C programs should implement the same algorithm (merge sort
> in Haskell outperforming bubble sort in C doesn't count), though I
> guess that using Haskell-specific idioms and optimizations is of
> course allowed.

While Haskell usually gets close to C/C++ speed for number crunching
algorithms it seldomly beats them.  Of course the execution model gives
potential to do so, but currently GHC doesn't do enough low level
optimization.  It is amazing at high level optimization so you often get
similar speeds for much less code that is close to the problem domain.
Combined with the fact that it's more difficult to write incorrect
programs in Haskell there is an overall save in time to get to the
result and that is amplified whenever you have to change the program
later.

Where Haskell really gets beyond C and C++ is in concurrency.
Multithreaded network servers written in Haskell are not only a lot
easier to write, but they also perform better than well written server
programs in C/C++.  This is because Haskell's concurrency goes well with
its parallel execution model, where in machine code you don't really
have a notion of procedures.  You have thunks and they can not only be
executed in parallel, but they can also be moved between threads freely.

Imagine that in C/C++ you would move a client to another thread in the
middle of a function.  The Haskell run-time system does this all the
time to distribute computing time evenly between all CPUs.  Of course
this preemptive execution model can be replicated in C/C++, but that is
an amazingly difficult task, so difficult that you would practically
write very verbose Haskell in C/C++.


Greets,
Ertugrul

--
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://ertes.de/

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Ertugrul Söylemez]

Roman Cheplyaka <[hidden email]> wrote:

> >  isn't it that particular Haskell code is outperforming C (22
> > seconds vs. 33), just because the author uses recursion in C? I
> > surely love Haskell, and the way it's code is easy parallelized, but
> > that example seams not fair.
>
> I think the point was to take two programs of similar code complexity
> (or, rather, simplicity) implementing the same algorithm (modulo
> parallelism).
>
> So I'm not sure what exactly you're objecting to.

I think while this is a valid argument it is not very convincing.  You
have to acknowledge that C and C++ can give better performance at number
crunching.  The gain is small enough that personally I wouldn't go
through the trouble of writing my algorithms in C/C++, but simple-minded
people often have a desire to get the best performance possible, in
which case you really want to use C, C++, Fortran or whatever high level
assembler language you like.

In other words:  Writing Haskell in C is just as wrong as writing C in
Haskell.  A comparison of algorithm /implementation styles/ does not
have much semantic content.  It just shows that Haskell rocks at high
level optimization while C rocks at low level optimization.  By the same
experiment you can see that Haskell is bad at low level optimization
while C is bad at high level optimization.

In order to compare code performance you have to implement the same
algorithm in the idiomatic style in both languages.  This experiment
would show that Haskell, even though it gets close, is still slower than
C.  It would however show that interpreted Python and Ruby are
considerably slower than both.


Greets,
Ertugrul

--
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://ertes.de/

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Bartosz Milewski-2]

An equivalent parallel version in C++11 would look something like this:

long long fib(long long n) {
       if (n<  2) {
         return 1;
       }
       std::future<long long>  r = std::async(fib, n-2);
       long long l = fib(n-1);
       return r.get() + l;
}


My bet though is that it would perform worse that the serial version
because of much higher overheads in starting threads in C++.

[:Bartosz:]


On 5/6/2012 02:51, Austin Seipp wrote:

> In this case it doesn't matter; while it isn't technically tail
> recursive, GCC is very capable of transforming it into a direct loop
> likely because it knows about the associative/commutative properties
> of "+" so it's able to re-arrange the body as it sees fit since
> combined, both calls are in 'tail position.'
>
> With GCC 4.6.3 at -O3 optimization level on my Ubuntu 12.04 machine,
> the example in the linked article executes in 9s (Intel Core i5-2520M
> CPU @ 2.50GHz, dual core with 4 total logical cores) and the body of
> fib does no contain any call instructions - in fact, it seems to not
> only transform the body into a loop, but unroll a very good portion of
> it leading to very very fast code.
>
> Technically, if you want to be a pedant, the benchmarks aren't even
> equivalent anyway; GCC is able to use the native 'long long' datatype
> while GHC promotes the results of 'fib' to Integer, and thus is backed
> by GMP and a lot of extra code. GMP is fast, but it's not as fast as a
> native data type. It should use Int64.That change alone speeds up the
> benchmark by approximately 30% for me using GHC 7.4.1 (~30s at -N4 vs
> ~19s at -N4.)
>
> I don't think the point of that post was to outwit the C compiler, but
> show how easy it is to add parallelism to a Haskell program
> (ironically, pseq/par has proven quite difficult to leverage for nice
> wall-clock speedups in practice, hence the advent of libraries like
> strategies and more recently monad-par, that make speedups easier to
> get.) I do think it's much easier to add parallelism to Haskell
> programs - even if they are not as fast, it's far easier to write,
> understand, and safer to do so. And ultimately all this code is very
> old (5+ years) and not reflective of either toolchain anymore. GHC has
> had immesurable amounts of overhauls in its parallelism support as
> well as the libraries supporting it, and both GHC and GCC have far
> better optimisation capabilities.
>
> On Sun, May 6, 2012 at 4:09 AM, Roman Cheplyaka<[hidden email]>  wrote:
>> It is not tail-recursive.
>>
>> * Yves Parès<[hidden email]>  [2012-05-06 10:58:45+0200]
>>> I do not agree: the fib function is tail-recursive, any good C compiler is
>>> able to optimize away the calls and reduce it to a mere loop.
>>> At least that's what I learnt about tail recursion in C with GCC.
>>>
>>> 2012/5/6 Artur<[hidden email]>
>>>
>>>> On 06.05.2012 10:44, Ivan Lazar Miljenovic wrote:
>>>>
>>>>> On 6 May 2012 16:40, Janek S.<[hidden email]>    wrote:
>>>>>
>>>>>> Hi,
>>>>>>
>>>>>> a couple of times I've encountered a statement that Haskell programs can
>>>>>> have performance
>>>>>> comparable to programs in C/C++. I've even read that thanks to
>>>>>> functional nature of Haskell,
>>>>>> compiler can reason and make guarantess about the code and use that
>>>>>> knowledge to automatically
>>>>>> parallelize the program without any explicit parallelizing commands in
>>>>>> the code. I haven't seen
>>>>>> any sort of evidence that would support such claims. Can anyone provide
>>>>>> a code in Haskell that
>>>>>> performs better in terms of execution speed than a well-written C/C++
>>>>>> program? Both Haskell and C
>>>>>> programs should implement the same algorithm (merge sort in Haskell
>>>>>> outperforming bubble sort in
>>>>>> C doesn't count), though I guess that using Haskell-specific idioms and
>>>>>> optimizations is of
>>>>>> course allowed.
>>>>>>
>>>>> How about http://donsbot.wordpress.com/**2007/11/29/use-those-extra-**
>>>>> cores-and-beat-c-today-**parallel-haskell-redux/<http://donsbot.wordpress.com/2007/11/29/use-those-extra-cores-and-beat-c-today-parallel-haskell-redux/>
>>>>> ?
>>>>>
>>>>>   Hi,
>>>>   isn't it that particular Haskell code is outperforming C (22 seconds vs.
>>>> 33), just because the author uses recursion in C? I surely love Haskell,
>>>> and the way it's code is easy parallelized, but that example seams not fair.
>>>>
>>>>
>>>> ______________________________**_________________
>>>> Haskell-Cafe mailing list
>>>> [hidden email]
>>>> http://www.haskell.org/**mailman/listinfo/haskell-cafe<http://www.haskell.org/mailman/listinfo/haskell-cafe>
>>>>
>>> _______________________________________________
>>> Haskell-Cafe mailing list
>>> [hidden email]
>>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
>> --
>> Roman I. Cheplyaka :: http://ro-che.info/
>>
>> _______________________________________________
>> Haskell-Cafe mailing list
>> [hidden email]
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[wren ng thornton]

On 5/6/12 2:40 AM, Janek S. wrote:

> Hi,
>
> a couple of times I've encountered a statement that Haskell programs can have performance
> comparable to programs in C/C++. I've even read that thanks to functional nature of Haskell,
> compiler can reason and make guarantess about the code and use that knowledge to automatically
> parallelize the program without any explicit parallelizing commands in the code. I haven't seen
> any sort of evidence that would support such claims. Can anyone provide a code in Haskell that
> performs better in terms of execution speed than a well-written C/C++ program? Both Haskell and C
> programs should implement the same algorithm (merge sort in Haskell outperforming bubble sort in
> C doesn't count), though I guess that using Haskell-specific idioms and optimizations is of
> course allowed.

For a quantitative comparison in a very narrow domain, check out:

     Duncan Coutts, Don Stewart, Roman Leshchinskiy (2007).
     Rewriting Haskell Strings.
     http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.90.3166

Fundamentally, neither language can be faster than the other since it's
possible to hack around in assembly code with both of them. Therefore,
asking which is faster when implementing identical algorithms is not a
meaningful question. In reality, most people don't spend time
microoptimizing assembly code these days; instead, people implement
whatever seems good enough given the constraints on development time and
execution time. Thus, the real question should be: which algorithms are
made easy to implement by the language?--- either in terms of raw syntax
(hence maintainability), or in terms of man-hours worked (hence
development time).

The ease of parallelism in Haskell is a prime example of the fact that,
while all of it is technically possible to re-implement in C with
identical performance, Haskell is simply better because the parallel
code is already implemented and programs using it are statically checked
for type safety, which reduces the development time significantly. But
for the most part, that isn't a comparison of languages, it's a
comparison of libraries (for which the language of Haskell facilitates
making good libraries).

Once you approach the real question and try to quantify it, you're going
to run into the issues that arise any time you try to quantify human
populations. What works well for one project or company is not
necessarily going to generalize to a different set of developers; thus,
in order to ensure ecological validity in your comparison, you'll need
to compare lots of different kinds of groups. But of course, your
ability to do so is biased by the social environment; e.g., imperative
languages are more mainstream and therefore afford different developer
communities than functional languages do. Thus, not only can you not
come up with a simple metric that does justice to the question, but the
answer to the question is going to evolve and change over time ---even
if the underlying languages and compilers do not change--- because
society changes and evolves over time.

For as often as this question is asked, and for as much as it could be
interesting to actually get an answer, this isn't the sort of research
that computer scientists are (generally) trained to do. Which is why it
isn't generally done.

--
Live well,
~wren

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Silvio Frischknecht]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

> Can anyone provide a code in Haskell that performs better in terms
> of execution speed than a well-written C/C++ program?

http://shootout.alioth.debian.org/ compares a lot of programming
languages on a lot of problems. Haskell is never as fast as C++, but
for some problems it comes close.

Also I challenge anyone to improve one of the haskell programs there.
It'd be cool if we could make haskell get a higher rank. I recently
managed to improve the Fasta algorithm, but not by much. Also I think
the benchmarks don't use llvm flag. It says somewhere that they don't
measure llvm because they don't have time. But I think they are
refering to clang. So maybe someone should tell them to turn on the
llvm flag since it makes a lot of haskell programs faster.

Silvio
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQIcBAEBAgAGBQJPqKicAAoJEDLsP+zrbatWmSIP+gNSI61KMvY2VRsWRhd7+j5U
YAO3CnBTt6lSbMNplFf5AZnbPnY3NVJSG2ZUN12n7ZcaOawmwub3H+N9e0XTXv38
vOEGzFb/t/OTIx4GHXiWz6kZfzyiTVQpEhzoqx/ZX4KZqrUBt5ZuSpmWtPrPXCfF
joCZiBZIwxfOkI/l1zsb8vW3Xaqxs9dfRQOJEf7GLB5zGXwUA2ZLWG5HYvAUHu0G
9xB9cBgaX7HKdBwo3af2WZEFznZnZ1LUpc8TuacL54wVmLpLNJU2EaeqH2LsH0R3
VxX9yU1TIQUBubDa1Tui73xJ2L4Ns7AVD7Kx14yK5cu61wpz/KeUOU/wgedp+wNe
o54alfqzrfOC+GAJGJFg+3aIkXuij4j1jTXZ+/3ya7nofcBZwtqoZUWCvjYSoEaI
xecxuHLCK2pd3zwPk7ZUnG0Mo0vu4ZpVKpCs4u8nPRzVl0101mGkHSVTVXjVP8R/
d3AIPwy74B4nvCk9gohxHwtsvsmzxoRZr7E5XkGDTQdbj0Ly5bJfBW3c1X/jvq9c
FHvxCspERGf6S+aX9L6lg9v3/aje/av2q0zUL7jizA4no3q7D/ZvWkmIWF5ySyRh
+QrC39I6GHDMvxXn0HIp9m2226sNGL4vpvBTgucJWJcHUX+FdytFIe7VQ0ZvdXvx
IjxCrgMAPVy5/TH44PP+
=TaFj
-----END PGP SIGNATURE-----

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Yves Parès-3]

One thing that baffles me is the comparison Haskell V. Java: http://shootout.alioth.debian.org/u32/benchmark.php?test=all&lang=ghc&lang2=java

Would've expected always shorter code and better performances on average.

2012/5/8 Silvio Frischknecht <[hidden email]>

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

> Can anyone provide a code in Haskell that performs better in terms
> of execution speed than a well-written C/C++ program?

http://shootout.alioth.debian.org/ compares a lot of programming
languages on a lot of problems. Haskell is never as fast as C++, but
for some problems it comes close.

Also I challenge anyone to improve one of the haskell programs there.
It'd be cool if we could make haskell get a higher rank. I recently
managed to improve the Fasta algorithm, but not by much. Also I think
the benchmarks don't use llvm flag. It says somewhere that they don't
measure llvm because they don't have time. But I think they are
refering to clang. So maybe someone should tell them to turn on the
llvm flag since it makes a lot of haskell programs faster.

Silvio
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQIcBAEBAgAGBQJPqKicAAoJEDLsP+zrbatWmSIP+gNSI61KMvY2VRsWRhd7+j5U
YAO3CnBTt6lSbMNplFf5AZnbPnY3NVJSG2ZUN12n7ZcaOawmwub3H+N9e0XTXv38
vOEGzFb/t/OTIx4GHXiWz6kZfzyiTVQpEhzoqx/ZX4KZqrUBt5ZuSpmWtPrPXCfF
joCZiBZIwxfOkI/l1zsb8vW3Xaqxs9dfRQOJEf7GLB5zGXwUA2ZLWG5HYvAUHu0G
9xB9cBgaX7HKdBwo3af2WZEFznZnZ1LUpc8TuacL54wVmLpLNJU2EaeqH2LsH0R3
VxX9yU1TIQUBubDa1Tui73xJ2L4Ns7AVD7Kx14yK5cu61wpz/KeUOU/wgedp+wNe
o54alfqzrfOC+GAJGJFg+3aIkXuij4j1jTXZ+/3ya7nofcBZwtqoZUWCvjYSoEaI
xecxuHLCK2pd3zwPk7ZUnG0Mo0vu4ZpVKpCs4u8nPRzVl0101mGkHSVTVXjVP8R/
d3AIPwy74B4nvCk9gohxHwtsvsmzxoRZr7E5XkGDTQdbj0Ly5bJfBW3c1X/jvq9c
FHvxCspERGf6S+aX9L6lg9v3/aje/av2q0zUL7jizA4no3q7D/ZvWkmIWF5ySyRh
+QrC39I6GHDMvxXn0HIp9m2226sNGL4vpvBTgucJWJcHUX+FdytFIe7VQ0ZvdXvx
IjxCrgMAPVy5/TH44PP+
=TaFj
-----END PGP SIGNATURE-----

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Simon Marlow-7]

On 06/05/2012 07:40, Janek S. wrote:

> a couple of times I've encountered a statement that Haskell programs
> can have performance comparable to programs in C/C++. I've even read
> that thanks to functional nature of Haskell, compiler can reason and
> make guarantess about the code and use that knowledge to
> automatically parallelize the program without any explicit
> parallelizing commands in the code. I haven't seen any sort of
> evidence that would support such claims. Can anyone provide a code in
> Haskell that performs better in terms of execution speed than a
> well-written C/C++ program? Both Haskell and C programs should
> implement the same algorithm (merge sort in Haskell outperforming
> bubble sort in C doesn't count), though I guess that using
> Haskell-specific idioms and optimizations is of course allowed.

On the subject of parallelism in particular, there is no fully implicit
parallelism in Haskell at the moment.  When people ask about this I
typically point to this paper:

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.145.8183

which shows that it is possible to get some gains doing this, but it is
hard and the gains were not great.


However, what Haskell does give you is a guarantee that you can safely
call any function in parallel (with itself or with something else), as
long as the function does not have an IO type.  This is about as close
to automatic parallelisation as you can practically get.  Take any pure
function from a library that someone else wrote, and you can use it with
parMap or call it from multiple threads, and reasonably expect to get a
speedup.  Furthermore with parMap you're guaranteed that the result will
be deterministic, and there are no race conditions or deadlocks to worry
about.

Cheers,
        Simon

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Daniël de Kok]

On May 8, 2012, at 12:18 PM, Yves Parès wrote:
> Would've expected always shorter code

It's not so surprising if you consider that some of the programs are practically imperative programs in Haskell. To give an example:

http://shootout.alioth.debian.org/u32/program.php?test=fannkuchredux&lang=ghc&id=3

-- Daniël
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Ryan Newton]

through the trouble of writing my algorithms in C/C++, but simple-minded
people often have a desire to get the best performance possible, in
which case you really want to use C, C++, Fortran or whatever high level
assembler language you like.

I think this is a bit of an unfair accusation ("simple-minded").  Performance is only relevant to certain domains, sure.  But program performance is an entire *industry*.  And I'd argue it's of massive importance to the world at large.  Intel has an army of "AE"s (application engineers) that go out to other companies to make applications perform better.  There are plenty of compute bound industries -- i.e. movie companies are limited by what kind of frame they can render in ~24 hrs; sequencing centers are limited by certain very slow bioinformatics algorithms; you can look almost anywhere you like for examples.

As a community I think we have to face the fact that writing the hot inner loop of your application as idiomatic Haskell is not [yet] going to give you C/Fortran performance off the bat.  Though in some cases there's not really anything stopping us but more backend/codegen work (I'm thinking of arithmetically intensive loops with scalars only).  For example, the following Mandel kernel is in many ways the *same* as the C version:

https://github.com/simonmar/monad-par/blob/662fa05b2839c8a0a6473dc490ead8dd519ddd1b/examples/src/mandel.hs#L24H

We have the types; we've got strictness (for this loop); but the C version was 6X faster when I tested it.

  -Ryan

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Manuel M T Chakravarty]

Ryan Newton:

As a community I think we have to face the fact that writing the hot inner loop of your application as idiomatic Haskell is not [yet] going to give you C/Fortran performance off the bat.  Though in some cases there's not really anything stopping us but more backend/codegen work (I'm thinking of arithmetically intensive loops with scalars only).  For example, the following Mandel kernel is in many ways the *same* as the C version:

https://github.com/simonmar/monad-par/blob/662fa05b2839c8a0a6473dc490ead8dd519ddd1b/examples/src/mandel.hs#L24H

We have the types; we've got strictness (for this loop); but the C version was 6X faster when I tested it.

Did you use the LLVM backend? I am asking because I have seen dramatic differences between the code generators in similar example. Have a look at

  https://wiki.cse.unsw.edu.au/cs3141/12s1/Parallelism%20notes

With GHC's native code generator, the C version is much faster than the Haskell version (by a factor of 2 or 3 IIRC), but using GHC's LLVM backend, the Haskell version is even a few percent faster than the C version on my machine. (This is on OS X using llvm-gcc to compile the C code — that is, the code generator for the C and Haskell version goes via LLVM.)

I think that is an interesting example, because it shows (a) just how much of a difference a good code generator can make and (b) that using the same code generator, a Haskell compiler has no inherent disadvantage to a C compiler. (Nevertheless, especially for small examples, it is much easier to write a slow Haskell than to write a slow C program.)

Manuel

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe