[Haskell-cafe] Can Haskell outperform C++?

[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 <roma at ro-che.info> wrote:
> It is not tail-recursive.
>
> * Yves Parès <yves.pares at gmail.com> [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 <apeka1990 at gmail.com>
>>
>> > On 06.05.2012 10:44, Ivan Lazar Miljenovic wrote:
>> >
>> >> On 6 May 2012 16:40, Janek S.<fremenzone at poczta.onet.pl>  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
>> > Haskell-Cafe at haskell.org
>> > http://www.haskell.org/**mailman/listinfo/haskell-cafe<http://www.haskell.org/mailman/listinfo/haskell-cafe>
>> >
>
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
> --
> Roman I. Cheplyaka :: http://ro-che.info/
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe



-- 
Regards,
Austin