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

[Bartosz Milewski]

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