Re: Fw: speed of compiled Haskell code.
Hi, very slow. After we made the insert operation in the AVL tree hyperstrict and a few similar changes, our program behaved very well and is surely faster than if written in C using naive data structures and algorithms. We used combinators like strict2 f x y = strict (strict f x) y to achieve a simple code. Jan I find this interesting. It would be nice if you would like to Jan explain me what you mean by " hyperstrict" I agree with the definition of hyperstrictness, that a function is hyperstrict if it evaluates its arguments completely. What I meant concerning the AVL tree was not complete hyperstrictness but, that all parts which influence the structure of the tree are evaluated when a new element is inserted. The crucial point is that the application of the tree constructors must be strict to guarantee that the restructuring balancing operation is performed immediately. The comparison operators and the condition in if-then-else are strict anyway and, thus, will force sufficient evaluation. However, data stored in the tree that is not used for the operations on the tree need not be evaluated. Cheers Christoph
Re: speed of compiled Haskell code.
"D. Tweed" [EMAIL PROTECTED] writes: "Ch. A. Herrmann" wrote: I believe that if as much research were spent on Haskell compilation as on C compilation, Haskell would outperform C. Unless I've got a dramatically distorted view of the amount of research that goes on for imperative vs functional languages, and C vs haskell it seems that they get, to an order of magnitude, the same amount of research. I think a more appropriate term (and more directly responsible for C performance) would be "engineering effort". Having a well-performing C compiler is a sine qua non for most computer manufacturers. (We really need to get a Haskell program into SPEC.) -kzm -- If I haven't seen further, it is by standing in the footprints of giants
Re: speed of compiled Haskell code.
"Jan Brosius" [EMAIL PROTECTED] writes: But this example task was chosen as unlucky for Haskell. In other, average case, I expect the ratio of 6-10. This seems that Haskell cannot be considered as a language for real world applications but merely as a toy for researchers . Yeah. Let's just lump Haskell in with Perl, Python, Java, Lisp and all those other toy languages, completely useless in the "real world". The only argument against Haskell's performance that IMHO carries any real weight, is that GHC is dog slow as a compiler[0]. No other Haskell programs I've used or written[1] have been slow enough for me to notice it. -kzm [0] almost as bad as Microsoft's C++ compiler, imagine that. [1] admittedly not many. Are people using Haskell having problems getting good enough performance? Enough to regret choosing it as a language? (This is not a rhetoric question!) -- If I haven't seen further, it is by standing in the footprints of giants
Re: speed of compiled Haskell code.
[1] admittedly not many. Are people using Haskell having problems getting good enough performance? Enough to regret choosing it as a language? (This is not a rhetoric question!) No and yes. I use Haskell mainly for combinational problems in research. I would love to get higher performance without much effort. For one result I had to wait for over a week, the process used over 800MB main mem on our Sun Enterprise. GHC-compiled over Hugs gave approximately a factor 3. Haskell allows me to use smarter algorithms with small effort, I never had implemented the stuff at all in C. I did not yet try to use parHaskell so we have nice parallel systems here (e.g. cluster with 96 Pentiums). Andreas --- Andreas C. Doering Medizinische Universitaet zu Luebeck Institut fuer Technische Informatik Ratzeburger Allee 160 D-23538 Luebeck Germany Tel.: +49 451 500-3741, Fax: -3687 Email: [EMAIL PROTECTED] Home: http://www.iti.mu-luebeck.de/~doering quiz, papers, VHDL, music "The fear of the LORD is the beginning of ... science" (Proverbs 1.7)
Fw: speed of compiled Haskell code.
- Original Message - From: Ketil Malde [EMAIL PROTECTED] To: Jan Brosius [EMAIL PROTECTED] Cc: [EMAIL PROTECTED]; S.D.Mechveliani [EMAIL PROTECTED] Sent: Tuesday, March 21, 2000 10:14 AM Subject: Re: speed of compiled Haskell code. "Jan Brosius" [EMAIL PROTECTED] writes: But this example task was chosen as unlucky for Haskell. In other, average case, I expect the ratio of 6-10. This seems that Haskell cannot be considered as a language for real world applications but merely as a toy for researchers . Yeah. Let's just lump Haskell in with Perl, Python, Java, Lisp and all those other toy languages, completely useless in the "real world". The only argument against Haskell's performance that IMHO carries any real weight, is that GHC is dog slow as a compiler[0]. No other Haskell programs I've used or written[1] have been slow enough for me NO, NO and NO , please read only what I have written. E.g. I believe that Ocaml is certainly not toy language, it gives as far as people have communicated to me fast compact native code. My question about the speed of Haskell is not meant to upset people. On the contrary Haskell does attract me by its elegance. I just wanted to know what to expect of the code produced. I thought some people could give me some honest answers about it. Recent (really recent ) benchmarks are not available ont the Haskell website as far as I know Friendly Jan Brosius (a lazy wanting to use Haskell ) to notice it. -kzm [0] almost as bad as Microsoft's C++ compiler, imagine that. [1] admittedly not many. Are people using Haskell having problems getting good enough performance? Enough to regret choosing it as a language? (This is not a rhetoric question!) -- If I haven't seen further, it is by standing in the footprints of giants
Re: Fw: speed of compiled Haskell code.
"Jan Brosius" [EMAIL PROTECTED] writes: NO, NO and NO , please read only what I have written. You mean, apart from This seems that Haskell cannot be considered as a language for real world applications but merely as a toy for researchers . ? I could have sworn you were saying here that Haskell was unsuitable for "real" work, due to the cited performance loss of factor of 6-10. My point was that there's plenty of work being done in languages a lot slower than Haskell. There may be reasons for not using Haskell in the "real" world, performance is IMHO not an important one. -kzm -- If I haven't seen further, it is by standing in the footprints of giants
Re: Fw: speed of compiled Haskell code.
In the vein of benchmarking,
For those of you who follow comp.arch (or am I the only one?), you
have probably noticed the discussion about Stalin vs. C compilers.
For those who don't, it's basically one particular Scheme program
where compiled Scheme beats a naïve rewrite in C with orders of
magnitude (5s vs 30s was cited).
When rewriting in Haskell, I got some rather interesting results, hugs
apparently runs the program about as fast as compiled Scheme (!) (I
get 8 seconds on a P150, while the numbers above were from a PPro200),
and a compilation with GHC brings it down to about zero (0.7s to be
exact), but returns 0 instead of some large number.
This puzzles me, so I thought I'd turn to the list to see if anybody
here can shed light on my practices. Am I committing some grave error
in my translations? Have I inadvertently performed source code
optimization? Is there a bug in GHC? Or is it just damned good at
figuring out things analytically?
The source code is as follows, with most of the original Scheme code
submitted in comments. (The missing Scheme is the integrate*
functions, which are rather trivially translated. If anybody asks,
I'll dig them up). Here goes:
-8
integrate1D :: Double - Double - (Double-Double) - Double
integrate1D l u f =
let d = (u-l)/8.0 in
d * sum
[ (f l)*0.5,
f (l+d),
f (l+(2.0*d)),
f (l+(3.0*d)),
f (l+(4.0*d)),
f (u-(3.0*d)),
f (u-(2.0*d)),
f (u-d),
(f u)*0.5]
integrate2D l1 u1 l2 u2 f = integrate1D l2 u2
(\y-integrate1D l1 u1
(\x-f x y))
zark u v = integrate2D 0.0 u 0.0 v (\x-(\y-x*y))
{-
(define (r-total N)
(do ((I 1 (+ I 1))
(Sum 0.0 (+ Sum (zark (* I 1.0) (* I 2.0)
(( I N) Sum)))
-}
ints = [1.0..]
zarks = zipWith zark ints (map (2.0*) ints)
rtotals = head zarks : zipWith (+) (tail zarks) rtotals
rtotal n = rtotals!!n
{-
(define (i-total N)
(do ((I 1 (+ I 1))
(Sum 0.0 (+ Sum (let ((I2 (* (* I I) 1.0))) (* I2 I2)
(( I N) Sum)))
-}
is = map (^4) ints
itotals = head is : zipWith (+) (tail is) itotals
itotal n = itotals!!n
{-
(define (error-sum-of-squares N)
(do ((I 1 (+ I 1))
(Sum 0.0 (+ Sum (let ((E (- (r-total I) (i-total I (* E E)
(( I N) Sum)))
(begin (display (error-sum-of-squares 1000)) (newline))
-}
es = map (^2) (zipWith (-) rtotals itotals)
etotal n = sum (take n es)
main = putStrLn (show (etotal 1000))
8
Re: speed of compiled Haskell code.
On 21 Mar 2000, Ketil Malde wrote: "Jan Brosius" [EMAIL PROTECTED] writes: But this example task was chosen as unlucky for Haskell. In other, average case, I expect the ratio of 6-10. This seems that Haskell cannot be considered as a language for real world applications but merely as a toy for researchers . Yeah. Let's just lump Haskell in with Perl, Python, Java, Lisp and all those other toy languages, completely useless in the "real world". Not sure I understand this statement. Compiled common lisp and scheme are pretty competitive with C at this point for a great many things. Java is designed to be portable as byte codes, which is a different aim than the others. On the string/text processing programs where it excels, performance of both perl and C (at least in my hands :-)) tend to be I/O bound, and perl is waaay easier to get written. I know less about python, but I do know they've got a version (jpython) that produces java bytecodes, while there is also an effort going on to introduce stronger type-checking into the language (to improve its performance). I'm not sure there is any pair of these 6 languages I would lump together other than possibly perl and python. A more reasonable question might be: what real world applications would you use choose Haskell for today? And other people have given better answers here than I could. Which I guess is a cue to bring up my hunch that hugs/ghc *could* end up being a language that could eventually "out-perl perl" in some applications, since it's a good choice for parsing, and many text-filtering applications look like good matches for a functional programming language. In that regard, I think the biggest problems remaining are the lack of a standard "fast" string type, and some remaining warts in hugs. These are maybe easiest to see when you do something like "strace -c" on a hugs program and the comparable perl program. So, in my naive version of "hello world", the hugs version generates 803 calls to 'lstat', 102 calls to 'stat', and a performance-killing 13 calls to 'write'; yup, that's one for every character. :-( throw most of those out, and you're within shouting distance of perl. And that would be something to shout about. Oh yeah: my code. :-) #!/usr/bin/runhugs module Main where main = putStr "Hello, world\n" --- #!/usr/bin/perl print "Hello, world\n"; jking
Re: Fw: speed of compiled Haskell code.
Hi All, I find this interesting. It would be nice if you would like to explain me what you mean by " hyperstrict" I think hyperstrict means that a function completely evaluates *all* of its arguments before the body of the function, as opposed to only some of them. A function f taking n arguments is strict in its i'th argument if f a_1 .. a_i-1 _|_ a_i+1 .. a_n = _|_ E.g. const is strict in its first argument but not in its second. f is strict in all arguments if f a_1 .. a_n = _|_ whenever one of the a_i's is _|_. multOrAdd x y z = if x then y * z else y + z is strict in all of it arguments. Hyperstrict has, in my view at least, also an annotation of completely evaluating all arguments before the body of the function - something else than (eventually) evaluating them all. I'm not sure about this though, maybe someone can shed more light on this matter. Hope this helps (or leads to someone else giving a better definition :-) Jan de Wit
RE: speed of compiled Haskell code.
| In that regard, I think the biggest problems remaining are the lack of a | standard "fast" string type, and some remaining warts in hugs. These are | maybe easiest to see when you do something like "strace -c" on a hugs | program and the comparable perl program. So, in my naive version of | "hello world", the hugs version generates 803 calls to 'lstat', 102 calls | to 'stat', and a performance-killing 13 calls to 'write'; yup, that's | one for every character. :-( throw most of those out, and you're within | shouting distance of perl. And that would be something to shout about. I see big problems in using Hugs as an example in discussions about the speed of compiled code. Hugs derives from Gofer, which was designed to fit on a 16 bit machine with a fairly small memory (several times smaller than the PDAs, digital cameras, and video cards in use today). It was also designed, from the beginning, to be an interactive system based around a simple read-eval-print loop. Performance was never the priority. After all, there were a couple of other places you could turn for a compiler if you did want performance, and those folks had spent a lot of time and effort on building their systems. Hugs was intended to complement rather than compete with them. Because interactivity was a goal, Hugs, by default, does indeed call fflush after every character, which causes the repeated calls to write that you see. If it didn't do that, then programs on slow machines or with expensive underlying computations might have behavior that is counter- intuitive and confusing, especially to beginners. We are, after all, talking about a lazy language, and so you wouldn't think that you'd have to wait for a whole line of output before you saw the first character. Surprisingly, perhaps, the performance of Hugs turned out to be good enough for many tasks, particularly on the machines that we use today, and so tools like runhugs have become a viable option for some purposes. But you should always remember that Hugs came before runhugs, and that the default distribution is tuned primarily for use as an interactive environment. There is, in fact, a compile-time setting that you can use to prevent Hugs from calling fflush after every character (I think it's FLUSHEVERY, but you should check). If you set that appropriately, then Hugs I/O will (or should) run a little more quickly. All the best, Mark [EMAIL PROTECTED] Pacific Software Research Center, Oregon Graduate Institute Looking for a PhD or PostDoc? Interested in joining PacSoft? Let us know!
Re: speed of compiled Haskell code.
"Andreas C. Doering" [EMAIL PROTECTED] wrote, [1] admittedly not many. Are people using Haskell having problems getting good enough performance? Enough to regret choosing it as a language? (This is not a rhetoric question!) No and yes. I use Haskell mainly for combinational problems in research. I would love to get higher performance without much effort. For one result I had to wait for over a week, the process used over 800MB main mem on our Sun Enterprise. GHC-compiled over Hugs gave approximately a factor 3. Did you ever try (space) profiling the program? IMHO if you have applications were performance matters, profiling is imperative. Manuel
Re: speed of compiled Haskell code.
Sergey Mechveliani [EMAIL PROTECTED] wrote: [..] E.g. if one uses GHC to compile Haskell code into native code what speed performance can be expected versus a same program written in C [..] My experience with the program of generating permutations on [1..10] showed that the code produced by ghc-4.04 is 22 times slower than certain specially written C program. Only the C program algorithm was taken very different from Haskell's one. For each system has its own best algorithm and appropriate data structure. But this example task was chosen as unlucky for Haskell. In other, average case, I expect the ratio of 6-10. This seems that Haskell cannot be considered as a language for real world applications but merely as a toy for researchers . Do Ocaml or MLTon (SML) beat Haskell by a factorof 3? See e.g. What is MLton's efficience versus C? Here are the times in seconds for a few small benchmarks on my 400 MhZ Pentium II. For benchmarks that use arrays, I have also included the time when compiling with the -unsafe flag, which turns off bounds checking. gcc -O2 mlton mlton -unsafe --- - - fft 18.69 31.66 28.69 fib 7.44 9.97 matrix mult 2.65 13.27 6.15 quicksort 17.69 27.80 20.94 tak 15.86 21.99 As you can see mlton -unsafe is within a factor of 2 on all the benchmarks except matrix multiply, which is 2.3 times slower. P.S. As I understand the CPS (continuation passing style ) used to implement SML/NJ will be abandoned as it did not produce small and fast standalone executables I don't think that CPS is entirely the cause of this. Although, I do believe that their use of the heap for allocating stack frames does slow them down. As to size, I think they just haven't gone to enough effort to clean up the exported heaps. Is MLton portable to other OSes? Yes, but it hasn't been done yet. Right now, there is a Windows port underway by [EMAIL PROTECTED], using a crosscompiler from Linux (http://www.devolution.com/~slouken/SDL/Xmingw32/). He just started, so I'm not sure how it will turn out. I am not aware of any other porting efforts. The current focus of our development efforts are improving the performance with an X86 native backend and adding functionality. ### But I am not so sure. It is easy to mistake with such comparison. Cheers Jan Brosius
Re: speed of compiled Haskell code.
Dear Haskellites, My experience with the program of generating permutations on [1..10] showed that the code produced by ghc-4.04 is 22 times slower than certain specially written C program. Only the C program algorithm was taken very different from Haskell's one. For each system has its own best algorithm and appropriate data structure. But this example task was chosen as unlucky for Haskell. In other, average case, I expect the ratio of 6-10. Jan This seems that Haskell cannot be considered as a language for Jan real world applications but merely as a toy for researchers . some people from the FORTRAN community could say: "C is far too slow, use FORTRAN! Many computationally expensive problems do not need dynamic data structures!" In my opinion, the speed argument has to be relativated: - Not all applications require full speed. - Haskell programming saves you a lot of development time compared with C. You can use Haskell as an executable specification language and, if really necessary, charge some programmers with the task to convert it to C. - You need not use exclusively either Haskell or C. Time critical, interactive, or hardware accessing parts can be implemented in C, but your sophisticated algorithms are programmed in Haskell. - The ratio 6-10 is the state of the art today. I believe that if as much research were spent on Haskell compilation as on C compilation, Haskell would outperform C. Haskell has the advantage to C that due to referential transparency more powerful optimization rules can be applied. Thus, giving up referential transparency would mean to get a small improvement now but sacrifice the chances of the future. Cheers -- Christoph Herrmann E-mail: [EMAIL PROTECTED] WWW: http://brahms.fmi.uni-passau.de/cl/staff/herrmann.html
RE: speed of compiled Haskell code.
Bravo! I would only add that if the same development effort were expended optimizing Haskell code, as is spent just getting C or C++ code to work, the 6-10 factor would be dramatically reduced. --PeterD -Original Message- From: Ch. A. Herrmann [mailto:[EMAIL PROTECTED]] Sent: Monday, March 20, 2000 10:46 AM To: [EMAIL PROTECTED] Subject: Re: speed of compiled Haskell code. Dear Haskellites, My experience with the program of generating permutations on [1..10] showed that the code produced by ghc-4.04 is 22 times slower than certain specially written C program. Only the C program algorithm was taken very different from Haskell's one. For each system has its own best algorithm and appropriate data structure. But this example task was chosen as unlucky for Haskell. In other, average case, I expect the ratio of 6-10. Jan This seems that Haskell cannot be considered as a language for Jan real world applications but merely as a toy for researchers . some people from the FORTRAN community could say: "C is far too slow, use FORTRAN! Many computationally expensive problems do not need dynamic data structures!" In my opinion, the speed argument has to be relativated: - Not all applications require full speed. - Haskell programming saves you a lot of development time compared with C. You can use Haskell as an executable specification language and, if really necessary, charge some programmers with the task to convert it to C. - You need not use exclusively either Haskell or C. Time critical, interactive, or hardware accessing parts can be implemented in C, but your sophisticated algorithms are programmed in Haskell. - The ratio 6-10 is the state of the art today. I believe that if as much research were spent on Haskell compilation as on C compilation, Haskell would outperform C. Haskell has the advantage to C that due to referential transparency more powerful optimization rules can be applied. Thus, giving up referential transparency would mean to get a small improvement now but sacrifice the chances of the future. Cheers -- Christoph Herrmann E-mail: [EMAIL PROTECTED] WWW: http://brahms.fmi.uni-passau.de/cl/staff/herrmann.html
Re: speed of compiled Haskell code.
"Ch. A. Herrmann" wrote: I believe that if as much research were spent on Haskell compilation as on C compilation, Haskell would outperform C. I wish I could say I believed that. The big thing you aren't going to be able to optimise away is laziness, which means you are going to have unevaluated thunks rather than values all over the place. Of course you can put strictness annotations in all over the place if you want to, but then that rather spoils the point of Haskell. On the other hand Haskell may start looking more favourable in a few years. It seems to me that the Von Neumann architecture (one processor sitting in the middle, sending out messages when it wants data) is really creaking at the seams right now. Multiple caches and pipelining are becoming ever more important, but there's only so much that can be done with conventional programming languages. (Hence claims of processor speed, which usually assume zero CPU wait time and the sort of scheduling only available with hand-tuned assembler, bear less and less resemblance to reality every year.) However Haskell is much easier to reason about and should be much easier to parallelise, so its time may come even where performance is important. I hope.
RE: speed of compiled Haskell code.
Laziness is a great advantage in some cases. When, at compile time, you do not know what needs to be evaluated at run time, you can a) evaluate everything that may need to be evaluated (and waste a great deal of time) b) write your own system to determine what needs to be evaluated at run-time c) use a lazy language imho, for complex problems c) is often faster than a) and c) usually involves less development effort than b) -Original Message- From: George Russell [mailto:[EMAIL PROTECTED]] Sent: Monday, March 20, 2000 10:58 AM To: Ch. A. Herrmann Cc: [EMAIL PROTECTED] Subject: Re: speed of compiled Haskell code. "Ch. A. Herrmann" wrote: I believe that if as much research were spent on Haskell compilation as on C compilation, Haskell would outperform C. I wish I could say I believed that. The big thing you aren't going to be able to optimise away is laziness, which means you are going to have unevaluated thunks rather than values all over the place. Of course you can put strictness annotations in all over the place if you want to, but then that rather spoils the point of Haskell. On the other hand Haskell may start looking more favourable in a few years. It seems to me that the Von Neumann architecture (one processor sitting in the middle, sending out messages when it wants data) is really creaking at the seams right now. Multiple caches and pipelining are becoming ever more important, but there's only so much that can be done with conventional programming languages. (Hence claims of processor speed, which usually assume zero CPU wait time and the sort of scheduling only available with hand-tuned assembler, bear less and less resemblance to reality every year.) However Haskell is much easier to reason about and should be much easier to parallelise, so its time may come even where performance is important. I hope.
Re: speed of compiled Haskell code.
"Ch. A. Herrmann" wrote: I believe that if as much research were spent on Haskell compilation as on C compilation, Haskell would outperform C. Unless I've got a dramatically distorted view of the amount of research that goes on for imperative vs functional languages, and C vs haskell it seems that they get, to an order of magnitude, the same amount of research. Haskell doesn't do as well as C in spite of this because compiling a functional program to run on well on current hardware is much harder than compiling C to run well on current hardware. From my understanding this is because to do well for Haskell like languages requires deducing run-time behaviour from a program that abstracts away from it (eg figuring update analysis, fold-build transformation,etc) whereas C programs are have much more of this done by the person writing the program. Of course, that's why the C is likely to be less adaptable than the Haskell, which is why all Right-Thinking Programmers (TM) think Haskell is a better programming vehicle :-) ___cheers,_dave www.cs.bris.ac.uk/~tweed/pi.htm|ALERT: you are communicating with an email: [EMAIL PROTECTED] |unsavoury individual with a copy of gdb work tel: (0117) 954-5253 |who reverse-engineered a file format.
RE: speed of compiled Haskell code.
Ok, So lazy Haskell (GHC 4.0...) is 10 times slower than a same program coded in C (let forget about Fortran). imperative functional programs like OCaml (or MLTon (SML 97) are 2.5 times slower than C , for any sort of program. Haskell code optimised by strictnes annotions in functions or in datastructures are ? times slower than C. Please correct me where I am wrong and fill in the required number for the ? sign above Friendly Jan Brosius
RE: speed of compiled Haskell code.
Hi, Jan Haskell code optimised by strictnes annotions in functions or Jan in datastructures are ? times slower than C. Jan Please correct me where I am wrong and fill in the required Jan number for the ? sign above I cannot give you a number, but I like to report about some experience we made in our programming project. We used lists to store a symbol table for a compiler. Later, we felt the need to switch to AVL trees and so we did. As the programs got bigger we discovered that our program used more than 200MB heap and became very slow. After we made the insert operation in the AVL tree hyperstrict and a few similar changes, our program behaved very well and is surely faster than if written in C using naive data structures and algorithms. We used combinators like strict2 f x y = strict (strict f x) y to achieve a simple code. Cheers -- Christoph Herrmann E-mail: [EMAIL PROTECTED] WWW: http://brahms.fmi.uni-passau.de/cl/staff/herrmann.html
speed of compiled Haskell code. Reply
Jan Brosius [EMAIL PROTECTED] writes on 16 Mar 2000 on speed and size of compiled Haskell code [..] E.g. if one uses GHC to compile Haskell code into native code what speed performance can be expected versus a same program written in C [..] My experience with the program of generating permutations on [1..10] showed that the code produced by ghc-4.04 is 22 times slower than certain specially written C program. Only the C program algorithm was taken very different from Haskell's one. For each system has its own best algorithm and appropriate data structure. But this example task was chosen as unlucky for Haskell. In other, average case, I expect the ratio of 6-10. But I am not so sure. It is easy to mistake with such comparison. Is lazyness as good as strictness. It helps to write simpler programs, but brings certain average cost overhead. The average practical cost difference does not seem great, and it looks like it is a matter of taste, what to choose. -- Sergey Mechveliani [EMAIL PROTECTED]
