On 06.05.2012 10:44, Ivan Lazar Miljenovic wrote:

On 6 May 2012 16:40, 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. How about http://donsbot.wordpress.com/2007/11/29/use-those-extra-cores-and-beat-c-tod... ?

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.

It is not tail-recursive. * Yves Parès [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

...

On 06.05.2012 10:44, Ivan Lazar Miljenovic wrote:

...

On 6 May 2012 16:40, 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.

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

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@haskell.org http://www.haskell.org/**mailman/listinfo/haskell-cafehttp://www.haskell.org/mailman/listinfo/haskell-cafe

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

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

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

It is not tail-recursive.

* Yves Parès [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

...

On 06.05.2012 10:44, Ivan Lazar Miljenovic wrote:

...

On 6 May 2012 16:40, 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.

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

 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@haskell.org http://www.haskell.org/**mailman/listinfo/haskell-cafehttp://www.haskell.org/mailman/listinfo/haskell-cafe

...

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

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

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

-- Regards, Austin

* Artur [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/

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

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/662fa05b2839c8a0a6473dc490ead8dd5... We have the types; we've got strictness (for this loop); but the C version was 6X faster when I tested it. -Ryan

Ryan Newton wrote:

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.

I'm sorry for the rough words. I didn't mean to overgeneralize. Of course in certain domains a reasonable performance is desirable, but the first question you should ask is whether you want high level or low level performance. Haskell performs amazingly at the high level and suboptimal at the low level. My point is: If you need C-like performance at a certain spot there is really no excuse for writing the entire application in C. Haskell has a working, powerful enough FFI. Also idiomatic Haskell code nowadays performs close to C. If your code doesn't, chances are that it's not even idiomatic. Sorting a list is easy and beautiful in code. But it's far from idiomatic. Using ST with destructive update is also not idiomatic. One of my performance masterpieces is the "instinct" AI library (see Hackage). It uses only immutable vectors and performs very heavy Double calculations, yet performs better than the same code with mutable arrays did. With a few years of Haskell experience in my backpack I know how to utilize laziness to get amazing performance for code that most people would feel must be written with destructively updating loop. And the resulting code is just beautiful to read and watch at work, a great demonstration of the wonders the GHC developers have created.

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/662fa05b2839c8a0a6473dc490ead8dd5...

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

Well, if it's "in many ways the same as C", then again it's probably not idiomatic Haskell. I don't know what a Mandel kernel is, so I can't really tell you how I would write the code without further study. However, I'm doing a lot of number crunching and my code usually gets really close to C, and especially for Integer-heavy calculations actually outperforms C. I have done the comparison. Using GMP with all the features it provides in the mpz_* family of functions is in fact slower than the same in Haskell (GHC 7.4.1 on Intel i5 64 bits here), and from my C times I have experience using GMP properly including smart allocation, etc. If you want high performance Haskell, writing C in Haskell is /not/ the solution. It /will/ result in suboptimal code, likely considerably slower than the same code in C. Greets, Ertugrul -- Key-ID: E5DD8D11 "Ertugrul Soeylemez " FPrint: BD28 3E3F BE63 BADD 4157 9134 D56A 37FA E5DD 8D11 Keysrv: hkp://subkeys.pgp.net/

On Sat, May 12, 2012 at 12:41 AM, Gregg Lebovitz wrote:

I would find it useful to pull all this information together into a single document that discusses all the performance issues in one place and shares the real life experience is dealing with each issue. I see this as a best practice paper rather than a research document.

Does such a document exist? If not, I am willing try and start one.

http://www.haskell.org/haskellwiki/Performance ;)

Yet this resource seems a little outdated: http://www.haskell.org/haskellwiki/Performance/Strings does not speak about Text http://www.haskell.org/haskellwiki/Performance/Arrays about Vector And what's the status of the Streams IO approach detailed in http://www.haskell.org/haskellwiki/Performance/IO ? Has it evolved into enumerators/conduits, or was that an unrelated approach? 2012/5/12 Chris Wong

On Sat, May 12, 2012 at 12:41 AM, Gregg Lebovitz wrote:

...

I would find it useful to pull all this information together into a single document that discusses all the performance issues in one place and shares the real life experience is dealing with each issue. I see this as a best practice paper rather than a research document.

Does such a document exist? If not, I am willing try and start one.

http://www.haskell.org/haskellwiki/Performance

;)

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

On 05/11/2012 07:53 AM, Ertugrul Söylemez wrote:

My point is: If you need C-like performance at a certain spot there is really no excuse for writing the entire application in C. Haskell has a working, powerful enough FFI. Also idiomatic Haskell code nowadays performs close to C. If your code doesn't, chances are that it's not even idiomatic. Sorting a list is easy and beautiful in code. But it's far from idiomatic. Using ST with destructive update is also not idiomatic. One of my performance masterpieces is the "instinct" AI library (see Hackage). It uses only immutable vectors and performs very heavy Double calculations, yet performs better than the same code with mutable arrays did. With a few years of Haskell experience in my backpack I know how to utilize laziness to get amazing performance for code that most people would feel must be written with destructively updating loop. And the resulting code is just beautiful to read and watch at work, a great demonstration of the wonders the GHC developers have created. Hello Ertugrul,

Out of the curios, did you compare the performance of Instinct with implementations in languages, associated with numerical computations, like Octave?

Well, if it's "in many ways the same as C", then again it's probably not idiomatic Haskell.

It's just a recursive equation for mandelbrot fractals. I should have been precise, I didn't mean that the source is literally the *same* as the C source (i.e. there's no for loop, no mutable variables), rather that it presents the compiler backend with the same advantages as the C backend would have with the equivalent loop. That is, there's no control flow obfuscation (dictionaries, calls to unknown targets), no problems with laziness, and the data representations are completely known. mandel :: Int -> Complex Double -> Int mandel max_depth c = loop 0 0 where loop i !z | i == max_depth = i | magnitude z >= 2.0 = i | otherwise = loop (i+1) (z*z + c) It's also a loop that is readily recognized as a loop. Now, to my knowledge, GHC doesn't explicitly recognize loops in any stage of the compiler (so as to perform loop optimizations), something which other functional compilers sometimes do. But, anyway, it turns out that my example above *is easily transformed from a bad GHC performance story into a good one*. If you'll bear with me, I'll show how below. First, Manuel makes a good point about the LLVM backend. My "6X" anecdote was from a while ago and I didn't use llvm [1]. I redid it just now with 7.4.1+LLVM, results below. (The below table should read correctly in fixed width font, but you can also see the data in the spreadsheet herehttps://docs.google.com/spreadsheet/ccc?key=0AvzAHqQmHo87dHU0T0lCb1I4MFJmM2s... .) Time (ms) Compiled File size Comple+Runtime (ms) GHC 7.4.1 O0 2444 1241K GHC 7.4.1 O2 925 1132K 1561 GHC 7.4.1 O2 llvm 931 1133K GHC 7.0.4 O2 via-C 684 974K So LLVM didn't help [1]. And in fact the deprecated via-C backend did the best! Compare with GCC: G++ O0 300 9K 531 G++ O3 110 7K 347 G++ O3 recursive 116 9K Uh oh, the "6X" gap I mentioned is now closer to 9X. And, in fact, performing a mini "language shootout" on the above code, reveals that GHC is doing worse than not only OCaml, but Chez Scheme, in spite of dynamic type checks, and a necessarily boxed representation of complex numbers: Chez Scheme 8.4 284 2.7K notStandalone 372 OCaml 166 180K 301 At least Python does worse! Python 2.6 1973 NA 1973 *So here's the catch:* If you check the Core and STG GHC 7.4 is actually compiling the above loop very well. This microbenchmark turns into just a "magnitude" microbenchmark. The implementation of Data.Complex uses an EXTREMELY expensive method to avoid overflowhttps://github.com/ghc/packages-base/blob/master/Data/Complex.hs#L115 [2]. Since OCaml did well above, I took a look at their standard library's implementation, on line 51 herehttp://caml.inria.fr/cgi-bin/viewvc.cgi/ocaml/trunk/stdlib/complex.ml?revision=11156&view=markup. They use a nice little math trick (the extra division) that is also mentioned on Wikipedia. By implementing the same trick in Haskell, replacing the standard "magnitude" functionhttps://github.com/rrnewton/MandelMicrobench/blob/97c3275ad94cbce57a68881733..., we get the following results. GHC 7.4.1 No Overflow Avoidance 39 1127K 674 GHC 741, OCaml-style Overflow avoidance 74 1127K Wow, now not only is the Haskell version faster than OCaml/Scheme, *but it is 48% faster than C++*, which is appropriate to the title of this email! Of course, this probably means that C++'s abs is also doing something overly expensive for overflow avoidance (or that their representation of complex numbers is not fully unpacked and stored in registers) I haven't tracked it down yet. But in any case, I'll be submitting a library patch. *The moral, I think, is that community members could do a great deal to help "Haskell" performance by simply microbenchmarking and optimizing library routines in base!* Cheers, -Ryan P.S. You can check out the above benchmarks from here: https://github.com/rrnewton/MandelMicrobenchhttps://github.com/rrnewton/MandelMicrobench [1] P.P.S. Most concerning to me about Haskell/C++ comparisons are David Peixotto's findings that LLVM optimizations are not very effective on Haskell-generated LLVM compared with typical clang-generated LLVM. [2] P.P.P.S. It turns out there was already a ticket ( http://hackage.haskell.org/trac/ghc/ticket/2450) regarding magnitude's performance. But it still has bad performance even after a small refactoring was performed.

On 5/10/12 8:44 PM, Ryan Newton wrote:

...

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

Well, yes and no. 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). But on the other hand, there are quite a lot of people who focus excessively on "optimization" when the actual differences for the code they're writing are either negligible (e.g., because of I/O bottlenecks) or uninteresting (e.g., a 2x slowdown is a nuisance rather than a crisis). For those who focus on optimization when the benefits are negligible or uninteresting, I think it's fair to characterize that focus as "simple-minded". This focus seems especially common when people start talking about "which language is faster"--- as opposed to, say, which library is faster, or which implementation of a given algorithm is faster. In some cases the question of language speed is legitimate, but IME it's far more often used to prop up prejudices about which language is "better"--- i.e., which group of human beings (defined by their choice of programming language) is "better". I agree that, as a community, we need to come to a realistic understanding of the performance characteristics of Haskell compared to C etc. I don't like prejudice and propaganda for Haskell any more than I like prejudice and propaganda for C etc. In some cases it's true that Haskell out-performs C (or C++, or Java); but in many cases it does not, and we need to acknowledge that. The real problem, I feel, is that it's not always clear which category any given program falls into. In some cases the "idiomatic" Haskell is the fast one, in some cases its the slow one; but in all cases, what is meant by "idiomatic Haskell" is a moving target with poorly specified meaning. The advent of ByteStrings was a major coup in figuring out exactly where and why Haskell is slow and how to fix it. Iteratees are another one, though the details are still being worked out. However, things like strictness annotations on (non-accumulator) function arguments, the choice whether to use ST or not, the choice whether to CPS-transform or not, etc, are still very much a black art. Even with a thorough understanding of the STG-machine and the GHC compilation pipeline, it's not always clear whether they will help or hurt. ST in particular is especially finicky, to the point where I wonder if it's ever a win (outside of in-place updates on arrays). So while I think most language performance comparisons are dubious to begin with, I don't think the comparison of Haskell to C++ (or C, or Java,...) can even be construed as something with a meaningful answer. Haskell is just too different, and its in-the-large cost model is too poorly understood. I'm not even aware of any helpful generalizations over comparing two specific programs. Even when restricting to things like parsing or compute-intensive numeric code, the comparison comes back with mixed answers. -- Live well, ~wren

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

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

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

Ryan Newton 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 " FPrint: BD28 3E3F BE63 BADD 4157 9134 D56A 37FA E5DD 8D11 Keysrv: hkp://subkeys.pgp.net/

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

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

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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

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

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#**sumhttp://hackage.haskell.org/packages/archive/base/4.5.0.0/doc/html/src/Data-L...

[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 Haskell-Cafe@haskell.org http://www.haskell.org/**mailman/listinfo/haskell-cafehttp://www.haskell.org/mailman/listinfo/haskell-cafe

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

In addition, it's pretty much impossible for me to use Haskell to write

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

...

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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

From: Stephen Tetley

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

On Wed, May 16, 2012 at 8:40 AM, Gregg Lebovitz wrote:

1) Does Haskell and its libraries need performance improvements? Probably yes. Some of the performance issues seem to be related to the way the language is implemented and others by how it is defined. Developers really do run into performance issues with Haskell and either learn to work around the issue or try to fix the offending implementation. The wiki performance page gives insight into some of the performance issues and how address them.

I think there is a closely-related issue: that you'll need to learn how to debug subtle performance problems *early* in your Haskell programming career. In particular - you will have space leaks and related performance problems in naively-written programs - you will consequently need to learn how to use strictness annotations and other related language features, and how to use the profiler to determine where they're needed For example, imagine you're new to the language, and as an exercise decide to write a program that counts the characters on standard input and writes the count to standard output. A naive program in, say, Python will probably use constant space and be fairly fast. A naive program in Haskell stands a good chance of having a space leak, building a long chain of thunks that isn't forced until it needs to write the final answer. On small inputs, you won't notice. The nasty surprise comes when your co-worker says "cool, let's run it on this 100 MB log file!" and your program dies a horrible death. If your friend is a sceptic, she'll arch an eyebrow and secretly think your program -- and Haskell -- are a bit lame. The example is contrived, but it's a very common task to consume some big stream of input and produce a much smaller summary of it. I think it's fair to say that you have to be a slightly sophisticated Haskell programmer to do those kinds of things correctly, at least compared to more mainstream languages. My experience is that this is perhaps the most important 'problem' with Haskell performance. Not so much that it's typically two or three or ten times slower than language X, but that it's easy to have a bad experience *early on*, one that seems inconsistent with the language shoot-out and other performance comparisons. Kevin -- Kevin Charter kevin.charter@acm.org

On Wed, May 16, 2012 at 1:17 PM, Gregg Lebovitz wrote:

Also interesting is that in all my interviews, GHC performance was never raised. No one said "I have to drop into C to solve that performance problem."

That's been my experience too. I've so far been able to get acceptable performance with GHC when I've made good use of the tools for finding space and time leaks. And it hasn't been hard, just something I had to learn to do.

Gregg

Kevin -- Kevin Charter kevin.charter@acm.org

Ben, This is precisely the kind of problem I am currently thinking about and why I asked for pointers to documents on best practices. The current model for gaining the necessary experience to use Haskell effectively does not scale well. Here are some ideas on how to address the knowledge issue: 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. 2) Training presentations derived from #1 that provides lots of examples. 3) Online Training Videos based on #2 above 4) Profiling tools that uses the captured knowledge above, highlights problem areas, and provides guidance on correcting them. As I mentioned in a previous email. I am willing to take on organization #1, but I will need help from people on this list. I can start with the performance wiki, but we will still need examples of where people get into trouble and the ways around them. Gregg On 5/16/2012 4:00 PM, Ben Gamari wrote:

Kevin Charter writes:

snip

...

For example, imagine you're new to the language, and as an exercise decide to write a program that counts the characters on standard input and writes the count to standard output. A naive program in, say, Python will probably use constant space and be fairly fast. A naive program in Haskell stands a good chance of having a space leak, building a long chain of thunks that isn't forced until it needs to write the final answer. On small inputs, you won't notice. The nasty surprise comes when your co-worker says "cool, let's run it on this 100 MB log file!" and your program dies a horrible death. If your friend is a sceptic, she'll arch an eyebrow and secretly think your program -- and Haskell -- are a bit lame.

I, for one, can say that my initial impressions of Haskell were quite scarred by exactly this issue. Being in experimental physics, I often find myself writing data analysis code doing relatively simple manipulations on large(ish) data sets. My first attempt at tackling a problem in Haskell took nearly three days to get running with reasonable performance. I can only thank the wonderful folks in #haskell profusely for all of their help getting through that period. That being said, it was quite frustrating at the time and I often wondered how I could tackle a reasonably large project if I couldn't solve even a simple problem with halfway decent performance. If it weren't for #haskell, I probably would have given up on Haskell right then and there, much to my deficit.

While things have gotten easier, even now, nearly a year after writing my first line of Haskell, I still occassionally find a performance issue^H^H^H^H surprise. I'm honestly not really sure what technical measures could be taken to ease this learning curve. The amazing community helps quite a bit but I feel that this may not be a sustainable approach if Haskell gains greater acceptance. The profiler is certainly useful (and much better with GHC 7.4), but there are still cases where the performance hit incurred by the profiling instrumentation precludes this route of investigation without time consuming guessing at how to pare down my test case. It's certainly not an easy problem.

Cheers,

- Ben

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

The profiler is certainly useful (and much better with GHC 7.4)

What are the improvements in that matter? (I just noticed that some GHC flags wrt profiling have been renamed) 2012/5/16 Ben Gamari

Kevin Charter writes:

...

For example, imagine you're new to the language, and as an exercise decide to write a program that counts the characters on standard input and writes the count to standard output. A naive program in, say, Python will

snip probably

...

use constant space and be fairly fast. A naive program in Haskell stands a good chance of having a space leak, building a long chain of thunks that isn't forced until it needs to write the final answer. On small inputs, you won't notice. The nasty surprise comes when your co-worker says "cool, let's run it on this 100 MB log file!" and your program dies a horrible death. If your friend is a sceptic, she'll arch an eyebrow and secretly think your program -- and Haskell -- are a bit lame.

I, for one, can say that my initial impressions of Haskell were quite scarred by exactly this issue. Being in experimental physics, I often find myself writing data analysis code doing relatively simple manipulations on large(ish) data sets. My first attempt at tackling a problem in Haskell took nearly three days to get running with reasonable performance. I can only thank the wonderful folks in #haskell profusely for all of their help getting through that period. That being said, it was quite frustrating at the time and I often wondered how I could tackle a reasonably large project if I couldn't solve even a simple problem with halfway decent performance. If it weren't for #haskell, I probably would have given up on Haskell right then and there, much to my deficit.

While things have gotten easier, even now, nearly a year after writing my first line of Haskell, I still occassionally find a performance issue^H^H^H^H surprise. I'm honestly not really sure what technical measures could be taken to ease this learning curve. The amazing community helps quite a bit but I feel that this may not be a sustainable approach if Haskell gains greater acceptance. The profiler is certainly useful (and much better with GHC 7.4), but there are still cases where the performance hit incurred by the profiling instrumentation precludes this route of investigation without time consuming guessing at how to pare down my test case. It's certainly not an easy problem.

Cheers,

- Ben

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

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