Can Haskell outperform C++?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
56 messages Options
123
Reply | Threaded
Open this post in threaded view
|

Re: Can Haskell outperform C++?

wren ng thornton
On 5/16/12 7:43 AM, Yves Parès wrote:
>> On the one hand, characterizing those who desire the best performance
>> possible as "simple-minded" is, at best, a gross over-generalization. Like
>> you, I work in a field where optimization is king (e.g., in machine
>> translation, program runtimes are measured in days).
>
> You misread the logical implication, Ertugrul said:
>
>> simple-minded people often have a desire to get the best performance
>> possible

For the record, I was replying to Ryan's response to Ertugrul, rather
than to Ertugrul directly. I make no claims about what Ertugrul said or
the (in)validity thereof.

However, while the "logical" interpretation of Ertugrul's words may be
that simple-mindedness implies performance-desire, that interpretation
is not the only one available to the standard interpretation of his
words, nor IMO the dominant interpretation. It is equally valid to
interpret them as saying that the people under discussion are
simpletons, and that those people desire the best performance possible.
(I.e., an attributive rather than restrictive reading of the adjective.)
This latter interpretation is perfectly valid ---as the semantics of the
utterance---, but is pejorative of the people under discussion; and that
pejoration is what Ryan was (fairly) calling Ertugrul out on.

While I think it was fair for Ryan to call Ertugrul out on the matter, I
also thought the subject warranted further discussion since the
pejorative claim comes from somewhere, and so dismissing it entirely
fails to address the underlying issue. Not that I think Ryan was
dismissing it outright, just that it would be easy to interpret his
words as doing so.

--
Live well,
~wren

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Can Haskell outperform C++?

Ertugrul Söylemez
wren ng thornton <[hidden email]> wrote:

> However, while the "logical" interpretation of Ertugrul's words may be
> that simple-mindedness implies performance-desire, that interpretation
> is not the only one available to the standard interpretation of his
> words, nor IMO the dominant interpretation. It is equally valid to
> interpret them as saying that the people under discussion are
> simpletons, and that those people desire the best performance
> possible. (I.e., an attributive rather than restrictive reading of the
> adjective.) This latter interpretation is perfectly valid ---as the
> semantics of the utterance---, but is pejorative of the people under
> discussion; and that pejoration is what Ryan was (fairly) calling
> Ertugrul out on.
Well, the meaning was the logical one:  Simple-mindedness implies desire
for maximum performance possible.  Even that is an overgeneralization.
People can be simple-minded in many ways.  I hoped that my point would
come across.

Ryan got right that it was indeed an accusation.  I did not specify to
what group it was directed, which was probably the reason for the
confusion.  The unconditional desire for maximum possible object code
performance is usually very stupid, not to mention impossible to reach
with any high level language and any multi-tasking operating system.  To
get the maximum possible performance you must write an ring 0
application in assembly language and boot directly into it.

Haskell delivers reasonable performance for almost all non-embedded
applications, and for the extreme edge cases one can still switch to C
or assembly using the FFI.  Haskell's average penalty compared to C is
no reason to write the entire application in C.  That was my main point.


Greets,
Ertugrul

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

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

signature.asc (853 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Can Haskell outperform C++?

wren ng thornton
In reply to this post by glebovitz
On 5/16/12 4:37 PM, Gregg Lebovitz wrote:
> 1) Outstanding best practices documents that capture this knowledge and
> provides useful answers. Organizing this information in an online
> document that can be searched by keyword or index would be really
> helpful. The hard part will be maintaining it. As someone already
> pointed out the wiki entry on performance is already dated.

In light of that fact, and the general high-pace of innovation in
Haskell, I think that rather than trying to keep a wiki up-to-date, it
would probably be better to create a series of time-stamped "formal"
documents--- like how HCAR is published.

The benefit of such an approach is two-fold. On the one hand, there's a
date right there which shows when the contents were relevant (e.g., on
which version of GHC one particular style performed better than
another). On the other hand, when putting out the next issue/version the
authors are forced to revisit the old content and ask whether it's still
relevant or whether the tides have shifted; and if they're not willing
to commit one way or another, the content can be dropped without eliding
the fact (written in the previous issue) that it used to be an optimization.

Another thing I think is important is to give the actual reasons why
some particular thing is an optimization, and more particularly why it
is no longer an optimization once things have changed. A big issue I've
run into with blog-posts etc on performance in Haskell is that there's a
lot of folkloreism and just-so stories which tell people "just do X",
without explaining how X differs from Y, why X is better or worse than
Y, or the circumstances under which you may prefer Y to X. Without
providing the details about why something is an
optimization/pessimization, we don't provide users with the tools to
figure things out for themselves in this everchanging world.

--
Live well,
~wren

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Can Haskell outperform C++?

paolino
In reply to this post by Janek S.
Hello,

I would like to add questions to yours. I'm not sure that C++ programs
are same performance as C actually, so I can have a bad logic.

How much is hard to port a haskell program to C ?
If it will become harder and harder, (i.e. for parallelizations) than
it's fair to choose haskell for performance, but if it's not, I think
it's hard to think that such a high level language could ever compile
down to something running faster than its port to C.

Many of the abstractions used for nice haskell code are based on
boxing values, so we have to take away all the boxing to make it run
faster, and so we are porting to C.

Will hardware really go for hundreds of cores ?
If yes than all languages supporting simple parallelization will be
used to code, but this will not make C  slower, just more difficult to
use in contests.

Also a leading haskell point is , how does it take to make a correct
code, which can be performance in the wild.

So it makes some sense to choose haskell for performance to me, but
not to try to compete in sequential algorithmic performance, with the
exception for who do it to learn what is behind the abstractions that
makes their code slow and not compile down to perfect C.

paolino

P.S. The performance problems are actually learning haskell
programming abstractions and the intuition development on when to use
each.



2012/5/6 Janek S. <[hidden email]>:

> 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

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Can Haskell outperform C++?

Richard A. O'Keefe

> How much is hard to port a haskell program to C ?
> If it will become harder and harder, (i.e. for parallelizations) than
> it's fair to choose haskell for performance, but if it's not, I think
> it's hard to think that such a high level language could ever compile
> down to something running faster than its port to C.

There is a logic programming language called Mercury;
it has strict polymorphic types and strict modes and it supports
functional syntax as well as Horn clause syntax.  You could think
of it as 'strict Clean with unification'.

In the early days, they had a list processing benchmark where
the idiomatic Mercury version of the program was faster than
the idiomatic C version of the program, despite the fact that
at the time Mercury was compiling via C.

The answer was that the kind of C code being generated by Mercury
was not the kind of code any sane programmer would ever have written
by hand.  It really does depend on how you write it.

> Will hardware really go for hundreds of cores ?

You can already buy a >700 core machine (I have _no_ idea how many
chips are involved in that) for Java.



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Can Haskell outperform C++?

Ryan Newton
In reply to this post by Ertugrul Söylemez
The unconditional desire for maximum possible object code
performance is usually very stupid, not to mention impossible to reach
with any high level language and any multi-tasking operating system.  

Definitely.  I don't know if we have a catchy term for "kneejerk optimization" or if it falls under the broader umbrella of "premature optimization" [including misdirected or unneeded optimization].  

I do think we have the opposite problem, however, in much Haskell code -- people are using the clean, obviously correct, but inefficient code even in standard library functions that really should be optimized like crazy! 
 
 Haskell's average penalty compared to C is
no reason to write the entire application in C. 

Yes, this seems to be a separate disease.  Not just using low-level langs, per se, but using them for *everything*.  I have worked at places in industry where teams automatically use C++ for everything.  For example, they use it for building all complete GUI applications, which surprises me a little bit.  I would have thought in recent years that almost everyone was using *something* else (Java,Python, whatever) to do much of the performance-non-critical portions of their application logic.
 
  -Ryan


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Can Haskell outperform C++?

Ertugrul Söylemez
Ryan Newton <[hidden email]> wrote:

> I do think we have the opposite problem, however, in much Haskell code
> -- people are using the clean, obviously correct, but inefficient code
> even in standard library functions that really should be optimized
> like crazy!

Not necessarily.  For example the 'nub' function from Data.List could be
much faster.  Unfortunately this would also change its type.  O(n²)
complexity is really the best you can get with the Eq constraint.  You
have to change to Ord for better performance.

In other words:  Some optimizations change the semantics, and semantics
is taken very seriously in Haskell, for which I'm grateful.


Greets,
Ertugrul

--
Key-ID: E5DD8D11 "Ertugrul Soeylemez <[hidden email]>"
FPrint: BD28 3E3F BE63 BADD 4157  9134 D56A 37FA E5DD 8D11
Keysrv: hkp://subkeys.pgp.net/

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

signature.asc (853 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Can Haskell outperform C++?

Yves Parès-3
In reply to this post by Ryan Newton
> I do think we have the opposite problem, however, in much Haskell code -- people are using the clean, obviously correct, but inefficient code even in standard library functions that really should be optimized like crazy!

And even before optimizing "like crazy", I think the functions that are "more often" good should be emphasized: Prelude should export foldl' together with/instead of foldl, sum should have its sum' counterpart (or even be rewritten to use foldl'), and so on...
It baffles me that functions that are said to be more efficient in the majority of cases are not the default.

> I have worked at places in industry where teams automatically use C++ for everything.

Have they looked at you like if you were an alien (and even said you were not a serious developper) when you emitted the possibility of evaluating the feasibility of using/making a more expressive language for a specific task?

2012/5/21 Ryan Newton <[hidden email]>
The unconditional desire for maximum possible object code
performance is usually very stupid, not to mention impossible to reach
with any high level language and any multi-tasking operating system.  

Definitely.  I don't know if we have a catchy term for "kneejerk optimization" or if it falls under the broader umbrella of "premature optimization" [including misdirected or unneeded optimization].  

I do think we have the opposite problem, however, in much Haskell code -- people are using the clean, obviously correct, but inefficient code even in standard library functions that really should be optimized like crazy! 
 
 Haskell's average penalty compared to C is
no reason to write the entire application in C. 

Yes, this seems to be a separate disease.  Not just using low-level langs, per se, but using them for *everything*.  I have worked at places in industry where teams automatically use C++ for everything.  For example, they use it for building all complete GUI applications, which surprises me a little bit.  I would have thought in recent years that almost everyone was using *something* else (Java,Python, whatever) to do much of the performance-non-critical portions of their application logic.
 
  -Ryan


_______________________________________________
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
Reply | Threaded
Open this post in threaded view
|

Re: Can Haskell outperform C++?

Yves Parès-3
In reply to this post by Ertugrul Söylemez
> Not necessarily.  For example the 'nub' function from Data.List could be
> much faster.  Unfortunately this would also change its type.  O(n²)
> complexity is really the best you can get with the Eq constraint.

Why not in that kind of cases provide a second function (named differently), together with the original function, and specify they're differences (i.e. wrt performances) in the doc?
It seems like a pretty quick and honest trade-off to me.

2012/5/21 Ertugrul Söylemez <[hidden email]>
Ryan Newton <[hidden email]> wrote:

> I do think we have the opposite problem, however, in much Haskell code
> -- people are using the clean, obviously correct, but inefficient code
> even in standard library functions that really should be optimized
> like crazy!

Not necessarily.  For example the 'nub' function from Data.List could be
much faster.  Unfortunately this would also change its type.  O(n²)
complexity is really the best you can get with the Eq constraint.  You
have to change to Ord for better performance.

In other words:  Some optimizations change the semantics, and semantics
is taken very seriously in Haskell, for which I'm grateful.


Greets,
Ertugrul

--
Key-ID: E5DD8D11 "Ertugrul Soeylemez <[hidden email]>"
FPrint: BD28 3E3F BE63 BADD 4157  9134 D56A 37FA E5DD 8D11
Keysrv: hkp://subkeys.pgp.net/

_______________________________________________
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
Reply | Threaded
Open this post in threaded view
|

Re: Can Haskell outperform C++?

Thomas DuBuisson
On Mon, May 21, 2012 at 7:53 AM, Yves Parès <[hidden email]> wrote:
>> Not necessarily.  For example the 'nub' function from Data.List could be
>> much faster.  Unfortunately this would also change its type.  O(n²)
>> complexity is really the best you can get with the Eq constraint.
>
> Why not in that kind of cases provide a second function (named differently),
> together with the original function, and specify they're differences (i.e.
> wrt performances) in the doc?
> It seems like a pretty quick and honest trade-off to me.


WRT nub, Bart Massey did exactly this in his "nubOrd" proposal.  He
obtained consensus then failed to finish the ticket [1].  If this
particular case is of interest to you or anyone else then I suggest
you take the patches, re-propose and see it finished.  If you are
interested in this general category of issue, I think this is a case
study in how costly even our seemingly light weight proposals process
is in terms of proposer time investment.

Cheers,
Thomas

[1] http://hackage.haskell.org/trac/ghc/ticket/2717

>
> 2012/5/21 Ertugrul Söylemez <[hidden email]>
>>
>> Ryan Newton <[hidden email]> wrote:
>>
>> > I do think we have the opposite problem, however, in much Haskell code
>> > -- people are using the clean, obviously correct, but inefficient code
>> > even in standard library functions that really should be optimized
>> > like crazy!
>>
>> Not necessarily.  For example the 'nub' function from Data.List could be
>> much faster.  Unfortunately this would also change its type.  O(n²)
>> complexity is really the best you can get with the Eq constraint.  You
>> have to change to Ord for better performance.
>>
>> In other words:  Some optimizations change the semantics, and semantics
>> is taken very seriously in Haskell, for which I'm grateful.
>>
>>
>> Greets,
>> Ertugrul
>>
>> --
>> Key-ID: E5DD8D11 "Ertugrul Soeylemez <[hidden email]>"
>> FPrint: BD28 3E3F BE63 BADD 4157  9134 D56A 37FA E5DD 8D11
>> Keysrv: hkp://subkeys.pgp.net/
>>
>> _______________________________________________
>> 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
>

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Can Haskell outperform C++?

Sam Martin-2
In reply to this post by Ryan Newton

> Yes, this seems to be a separate disease.  Not just using low-level langs, per se,
> but using them for *everything*.  I have worked at places in industry where teams
> automatically use C++ for everything.  For example, they use it for building all
> complete GUI applications, which surprises me a little bit.  I would have thought
> in recent years that almost everyone was using *something* else (Java,Python,
> whatever) to do much of the performance-non-critical portions of their application logic.

I think "disease" might be overstating this somewhat :) In defence of using C++ for everything: Interfacing different languages is not exactly trivial, and in some cases, impossible.

If you are writing a program or system that has significant performance requirements, you might just be better off doing the whole thing in C/C++ and living with the annoyance of doing GUIs, or whatever, in C++. The overhead of pulling in another language may simply outweigh the convenience.

In addition, it's pretty much impossible for me to use Haskell to write portions (or all of) a game that would include a console version. This is largely for build system and platform support issues. Doing everything in C++ is nearly the only option here.

This situation could be improved though, by making it far easier to embed Haskell within C/C++. It's not difficult by design, but there are large engineering obstacles in the way, and it's hard to see where the effort to remove these could come from. But then it would be more plausible to argue that people are missing out by not using a mix of C++ and Haskell.

Cheers,
Sam


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Can Haskell outperform C++?

Yves Parès-3
> If you are writing a program or system that has significant performance requirements, you might just be better off doing the whole thing in C/C++ and living with the annoyance of doing GUIs

I fail to see how the GUI part would suffer from lack of performance if the rest of the system is fine. I would hate to be bold, but to me this case sounds a little bit like "MVC done wrong" if the breaking GUI apart from the rest of the software is really that impossible.
Anyway only benchmarks could tell if in such case the coding of the GUI in Haskell and the integration with the rest burns the performances to the ground.

> In addition, it's pretty much impossible for me to use Haskell to write portions (or all of) a game that would include a console version. This is largely for build system and platform support issues. Doing everything in C++ is nearly the only option here.

I worked in a video game company too (I refered to it when I answered to Ryan about companies automatically using C++), and I agree, the first unbreakable obstacle to the implementation of some parts of the application in Haskell (or in anything else than C/C++) that comes to mind is the fact that in the end it must run not only on personal computers.
The main issue is that those systems are way too closed by their manufacturers. Second issue may be RAM (way scarcer than on PCs: e.g. 512Mo in all for the PS3), but --again-- benchmarks wrt that would be more enlightening than my own opinion.

2012/5/21 Sam Martin <[hidden email]>

> Yes, this seems to be a separate disease.  Not just using low-level langs, per se,
> but using them for *everything*.  I have worked at places in industry where teams
> automatically use C++ for everything.  For example, they use it for building all
> complete GUI applications, which surprises me a little bit.  I would have thought
> in recent years that almost everyone was using *something* else (Java,Python,
> whatever) to do much of the performance-non-critical portions of their application logic.

I think "disease" might be overstating this somewhat :) In defence of using C++ for everything: Interfacing different languages is not exactly trivial, and in some cases, impossible.

If you are writing a program or system that has significant performance requirements, you might just be better off doing the whole thing in C/C++ and living with the annoyance of doing GUIs, or whatever, in C++. The overhead of pulling in another language may simply outweigh the convenience.

In addition, it's pretty much impossible for me to use Haskell to write portions (or all of) a game that would include a console version. This is largely for build system and platform support issues. Doing everything in C++ is nearly the only option here.

This situation could be improved though, by making it far easier to embed Haskell within C/C++. It's not difficult by design, but there are large engineering obstacles in the way, and it's hard to see where the effort to remove these could come from. But then it would be more plausible to argue that people are missing out by not using a mix of C++ and Haskell.

Cheers,
Sam


_______________________________________________
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
Reply | Threaded
Open this post in threaded view
|

Re: Can Haskell outperform C++?

Stephen Tetley-2
On 21 May 2012 17:27, Yves Parès <[hidden email]> wrote:

> I fail to see how the GUI part would suffer from lack of performance if the
> rest of the system is fine. I would hate to be bold, but to me this case
> sounds a little bit like "MVC done wrong" if the breaking GUI apart from the
> rest of the software is really that impossible.

A few years ago one of the architects at Adobe published some slides
on the software engineering aspects of PhotoShop, unfortunately I
couldn't find them on the web when I tried recently but I believe it
stated the codebase was well over 1 million lines of C++ and the GUI
(including Adobe's own frameworks) accounted for more than half of
that...

GUI's often *are* the program rather than a way in to use it.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Can Haskell outperform C++?

Isaac Gouy
> From: Stephen Tetley <[hidden email]>

> Sent: Monday, May 21, 2012 10:08 AM
> Subject: Re: [Haskell-cafe] Can Haskell outperform C++?
>
> On 21 May 2012 17:27, Yves Parès <[hidden email]> wrote:
>
>>  I fail to see how the GUI part would suffer from lack of performance if the
>>  rest of the system is fine. I would hate to be bold, but to me this case
>>  sounds a little bit like "MVC done wrong" if the breaking GUI
>> apart from the rest of the software is really that impossible.
>
> A few years ago one of the architects at Adobe published some slides
> on the software engineering aspects of PhotoShop, unfortunately I
> couldn't find them on the web when I tried recently but I believe it
> stated the codebase was well over 1 million lines of C++ and the GUI
> (including Adobe's own frameworks) accounted for more than half of
> that...
>
> GUI's often *are* the program rather than a way in to use it.


What about a more recent code base, this is from a 2008 presentation on Adobe Lightroom 2:

- "63% of the main Lightroom-team authored code is Lua"
- "16% C++"
- "12% ObjC"
- "9% C"

http://www.troygaul.com/LrExposedC4.html

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Can Haskell outperform C++?

wren ng thornton
In reply to this post by Yves Parès-3
On 5/21/12 10:51 AM, Yves Parès wrote:

>> I do think we have the opposite problem, however, in much Haskell code --
> people are using the clean, obviously correct, but inefficient code even in
> standard library functions that really should be optimized like crazy!
>
> And even before optimizing "like crazy", I think the functions that are
> "more often" good should be emphasized: Prelude should export foldl'
> together with/instead of foldl, sum should have its sum' counterpart (or
> even be rewritten to use foldl'), and so on...
> It baffles me that functions that are said to be more efficient in the
> majority of cases are not the default.

Part of this is due to legacy and the Haskell Report. For example, the
definition of sum is specified by the Report. And unfortunately there
exist (rare) cases where the semantics of sum and sum' differ: namely
when the type supports lazy addition (e.g., Peano numbers) and therefore
can return a partial answer to an infinite summation.

That said, the GHC philosophy in most of these cases has been to:

(a) use their own definitions with a CPP flag USE_REPORT_PRELUDE in case
you *really* want the Report's definition[1], and

(b) to "secretly" replace foldl by foldl' in cases where it can
determine the function argument to be strict (and therefore that the
change doesn't alter the semantics).

That doesn't fix everything, and it's no justification for not having
the newer Reports give more sane definitions, but it's better than nothing.

Part of the issue re fixing the Report is that there's a tension between
correctness and expediency, as well as between different notions of
"correctness". By and large, Haskell has managed to stay out of
theoretical arguments about choosing what "correct" means when it is
still controversial in mathematics. (Whence many of the complaints about
the non-mathematical nature of the numeric type classes.) But which of
the foldr vs foldl vs foldl' definitions of summation is the "correct"
definition? Mathematically, infinite summations should be allowed, and
summations of infinite quantities should be allowed. However,
pragmatically, infinite summations are of a different nature than finite
summations; e.g., when they converge it'd be nice to evaluate them in
finite time. So on the one hand, a naive view of "correctness" suggests
that we ought to allow these summations as just more of the same; but on
the other hand, an alternative notion of "correctness" suggests that
while infinite sums and sums of infinites should be handled, they should
be handled by different means than traditional finite sums of finite values.

The foldl' definition of summation only allows finite summations of
finite[2] values; the foldl definition only allows finite summations,
but they can be summations of infinite values; the foldr definition
allows both infinite values and infinitely many summands, though it's
not especially useful for handling infinite summations[3]. We can
probably exclude foldr with all fairness, and tell folks to handle
infinite summations in another way. But between foldl and foldl' there's
(room for) a lot more debate about which should be blessed by the
Prelude. Do we want to support lazy numbers out of the box, or do we
want to support performance for strict numbers out of the box? While
there's been a growing strictification of Haskell for performance
reasons, do recall that laziness was one of the initial reasons for
defining Haskell in the first place. Hence the old Report's definition.
The role of Haskell as a research engine has moved on since then, but
the decision to codify that is still non-trivial.


[1]
http://hackage.haskell.org/packages/archive/base/4.5.0.0/doc/html/src/Data-List.html#sum

[2] For the purpose of discussion, I'm considering the Float and Double
values for infinities to be "finite", because they are identical to the
finite values with respect to strictness and size of representation.

[3] It could take infinitely long to return, even for types which allow
lazily returning partial values. For example,

     data Peano = Z | S Peano
     instance Num Peano where ...

     zeros = Z : zeros

     -- Has to traverse the whole list, just in case there's a (S _) in
     -- there somewhere, before it knows whether to return Z or (S _).
     main = print (foldr (+) Z zeros)

--
Live well,
~wren

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Can Haskell outperform C++?

Yves Parès-3
I understand your concerns about modifying the current ideology, it's fair enough.
Actually I'm myself more in favor of adding strict couterparts, and export them conjointly, to support both the mathematical roots and the performances of the operations that are done most of time (Which kind of numbers do developers work with more often? Regular Ints and Doubles or Peano lazy numbers?)


2012/5/23 wren ng thornton <[hidden email]>
On 5/21/12 10:51 AM, Yves Parès wrote:
I do think we have the opposite problem, however, in much Haskell code --
people are using the clean, obviously correct, but inefficient code even in
standard library functions that really should be optimized like crazy!

And even before optimizing "like crazy", I think the functions that are
"more often" good should be emphasized: Prelude should export foldl'
together with/instead of foldl, sum should have its sum' counterpart (or
even be rewritten to use foldl'), and so on...
It baffles me that functions that are said to be more efficient in the
majority of cases are not the default.

Part of this is due to legacy and the Haskell Report. For example, the definition of sum is specified by the Report. And unfortunately there exist (rare) cases where the semantics of sum and sum' differ: namely when the type supports lazy addition (e.g., Peano numbers) and therefore can return a partial answer to an infinite summation.

That said, the GHC philosophy in most of these cases has been to:

(a) use their own definitions with a CPP flag USE_REPORT_PRELUDE in case you *really* want the Report's definition[1], and

(b) to "secretly" replace foldl by foldl' in cases where it can determine the function argument to be strict (and therefore that the change doesn't alter the semantics).

That doesn't fix everything, and it's no justification for not having the newer Reports give more sane definitions, but it's better than nothing.

Part of the issue re fixing the Report is that there's a tension between correctness and expediency, as well as between different notions of "correctness". By and large, Haskell has managed to stay out of theoretical arguments about choosing what "correct" means when it is still controversial in mathematics. (Whence many of the complaints about the non-mathematical nature of the numeric type classes.) But which of the foldr vs foldl vs foldl' definitions of summation is the "correct" definition? Mathematically, infinite summations should be allowed, and summations of infinite quantities should be allowed. However, pragmatically, infinite summations are of a different nature than finite summations; e.g., when they converge it'd be nice to evaluate them in finite time. So on the one hand, a naive view of "correctness" suggests that we ought to allow these summations as just more of the same; but on the other hand, an alternative notion of "correctness" suggests that while infinite sums and sums of infinites should be handled, they should be handled by different means than traditional finite sums of finite values.

The foldl' definition of summation only allows finite summations of finite[2] values; the foldl definition only allows finite summations, but they can be summations of infinite values; the foldr definition allows both infinite values and infinitely many summands, though it's not especially useful for handling infinite summations[3]. We can probably exclude foldr with all fairness, and tell folks to handle infinite summations in another way. But between foldl and foldl' there's (room for) a lot more debate about which should be blessed by the Prelude. Do we want to support lazy numbers out of the box, or do we want to support performance for strict numbers out of the box? While there's been a growing strictification of Haskell for performance reasons, do recall that laziness was one of the initial reasons for defining Haskell in the first place. Hence the old Report's definition. The role of Haskell as a research engine has moved on since then, but the decision to codify that is still non-trivial.


[1] http://hackage.haskell.org/packages/archive/base/4.5.0.0/doc/html/src/Data-List.html#sum

[2] For the purpose of discussion, I'm considering the Float and Double values for infinities to be "finite", because they are identical to the finite values with respect to strictness and size of representation.

[3] It could take infinitely long to return, even for types which allow lazily returning partial values. For example,

   data Peano = Z | S Peano
   instance Num Peano where ...

   zeros = Z : zeros

   -- Has to traverse the whole list, just in case there's a (S _) in
   -- there somewhere, before it knows whether to return Z or (S _).
   main = print (foldr (+) Z zeros)

--
Live well,
~wren


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