Re: Haskell's efficiency
As one of the authors of this paper, I'd like to echo Manuel's warning
about quoting out of context. The paper is about Haskell as a tool in
designing and presenting algorithms, not about performance. The Haskell
program was written for clarity, to explain a fairly tricky algorithm. The
figures are there to show that in spite of that clarity-first style, the
program is still suitable for sizable experiments.
The sources (both Haskell and C++) are on my home page at
http://www.comlab.ox.ac.uk/oucl/users/oege.demoor/homepage.htm
-O
On 23 Sep 1999, Marcin 'Qrczak' Kowalczyk wrote:
Thu, 23 Sep 1999 14:19:54 +0900, Manuel M. T. Chakravarty [EMAIL PROTECTED]
pisze:
The fact that the given URL simply produces a "not found" error
message on my machine,
I am sorry, I didn't know it was no longer there. I am putting it in
http://kki.net.pl/qrczak/bridging.ps.gz
PS: I am sorry for the impatient tone. In the Linux
community, posting, such as the cited on, are called
FUD: They spread Fear, Uncertainty, and Doubt, but miss
enough detail to be easy to refute.
I didn't want to repeat what is in the article. Sorry again.
Their intents are certainly pro-Haskell.
--
__("Marcin Kowalczyk * [EMAIL PROTECTED] http://kki.net.pl/qrczak/
\__/ GCS/M d- s+:-- a22 C++$ UL++$ P+++ L++$ E-
^^W++ N+++ o? K? w(---) O? M- V? PS-- PE++ Y? PGP-+ t
QRCZAK 5? X- R tv-- b+++ DI D- G+ e h! r--%++ y-
Re: Haskell's efficiency
"Jonathan" == Jonathan King [EMAIL PROTECTED] writes: Jonathan On Thu, 23 Sep 1999, Manuel M. T. Chakravarty wrote: [EMAIL PROTECTED] (Marcin 'Qrczak' Kowalczyk) wrote, S.D.Mechveliani [EMAIL PROTECTED] pisze: So far, no clear progrm example appeared in this list to demonstrate Haskell's in-efficiency in comparison to other languages. I have not done benchmarking myself yet, but in http://www.brookes.ac.uk/~p0071749/papers/bridging.ps.gz they describe an algorithm for text formatting. | lines | chars | size(KB) | time(s) | memory(KB) | --+---+---+--+-++ Haskell | 163 | 4640 | 410 |45.2 | 4505 | Modula-2 | 551 | 10005 | 74 |18.6 |356 | C++ | 389 | 5832 | 328 | 3.9 |368 | It is not quite fair because in Modula-2 and C++ all data structures were of fixed size, but... This may lead to a number of different conclusions: * Haskell is hopeless, * the author of the program has no clue about Haskell, * the Haskell compiler is hopeless, * the Haskell interpreter is really only an interpreter, or * the author forgot to pass -O when calling the Haskell compiler. Jonathan The original URL cited by Kowalczyk seems to be dead, but you can get Jonathan what I believe is an incarnation of the same work in: Jonathan http://www.brookes.ac.uk/~p0071749/publications.html#para Jonathan Please note that this paper does not actually concentrate on a "Haskell Jonathan vs.the world" comparison, but on the derivation of a new, linear time Jonathan paragraph formatting algorithm. The date on it was September 9, 1999, so Jonathan this is pretty much "hot off the press". Jonathan This version of the paper drops the Modula-2 line and the memory size Jonathan column; the rest of the new table would look like this: Jonathan | lines | chars | size(KB) | time(s) | Jonathan -+---+---+--+--+ Jonathan Haskell ghc 4.01 | 183 | 4676 | 453 | 4.72 | Jonathan Haskell hbc 0..4 | 183 | 4676 | 196 |10.34 | Jonathan C++ g++ 2.90.27 | 416 | 6310 |8 | 0.43 | Jonathan The C++ code was a direct (by hand) translation of the haskell, except Jonathan that they did things the way a C++ programmer would do them: using Jonathan destructive array updates, and data structures that were of fixed size Jonathan for a given problem. The code size of the C++ version suggests it was Jonathan dynamically linked to the usual stuff. Jonathan The text they formatted was the ASCII version of _Far from the Madding Jonathan Crowd_; clearly a problem of decent size. Jonathan You can probably learn a lot more from reading the whole paper, and Jonathan presumably from playing with the code. But that's still a factor of 10 Jonathan speed difference between the ghc version and the C++ version. This is Jonathan actually a bit encouraging, I think, but does point out some possible room Jonathan for improvement. If I had to make a wild guess, I'd bet the major source Jonathan of performance loss is in the haskell data structures used. While the Jonathan pedagogical niceness of defining String to be [Char] is obvious, I know Jonathan that (at least in Hugs98) this can really ruin your day. Jonathan (Some of you might like to try doing: Jonathan strace -c your_favorite_standalone_hugs_texthack Jonathan and note what you see. Then write the equivalent 5-line perl script (:-)) Jonathan and do the strace exercise again. Ouch. But since the next version of Jonathan Hugs98 is apparently due out imminently, this situation may well have Jonathan improved in the new version.) Jonathan But, man, things are getting *this close*; if it were really Jonathan true that all ghc needs right now to get in line with C++ on Jonathan text-formatting problems is a kicking string library and a Jonathan way for the compiler to know when to use it, then the Jonathan arguments usually used in favor become much more compelling Jonathan to a far larger audience. In his masters thesis, http://www.ki.informatik.uni-frankfurt.de/data/klose_diplom.ps.gz Norbert Klose implemented an packing transformation as a Haskell preprocessor. It transforms the list data structure by adding an additional constructor for packs of elements and then transforms all code using lists to use the new data structure and to keep data as packed as possible. This included using packing prelude functions for IO etc. He compared the running times of some programs when packing from one (like list) to 6 elements together. Almost in every case there is an improvement in running time, e.g. for `wc` the running time of the 4-pack version takes 36% of the running time of the 1-pack version. For some tests though, HBCs native lists were still better than the n-packs. E.g. for his length and filter tests while 6-packs reduced
Re: Haskell's efficiency
[EMAIL PROTECTED] (Marcin 'Qrczak' Kowalczyk) wrote, S.D.Mechveliani [EMAIL PROTECTED] pisze: So far, no clear progrm example appeared in this list to demonstrate Haskell's in-efficiency in comparison to other languages. I have not done benchmarking myself yet, but in http://www.brookes.ac.uk/~p0071749/papers/bridging.ps.gz they describe an algorithm for text formatting. | lines | chars | size(KB) | time(s) | memory(KB) | --+---+---+--+-++ Haskell | 163 | 4640 | 410 |45.2 | 4505 | Modula-2 | 551 | 10005 | 74 |18.6 |356 | C++ | 389 | 5832 | 328 | 3.9 |368 | It is not quite fair because in Modula-2 and C++ all data structures were of fixed size, but... This may lead to a number of different conclusions: * Haskell is hopeless, * the author of the program has no clue about Haskell, * the Haskell compiler is hopeless, * the Haskell interpreter is really only an interpreter, or * the author forgot to pass -O when calling the Haskell compiler. I am sure, you will find some more alternatives. The fact that the given URL simply produces a "not found" error message on my machine, doesn't help either. However, as this is apparently the Web page of Jeremy Gibbons, I am willing to exclude the second of the above options. In other words: If you give numbers, please put them in context. Otherwise, they are useless. I might also remark that it is not particularly enlightening to claim that it is possible to write inefficient programs in Haskell - I do this every day. The interesting question is, is it possible to write efficient programs? If not, why? If so, how difficult is it to do so? Manuel PS: I am sorry for the impatient tone. In the Linux community, posting, such as the cited on, are called FUD: They spread Fear, Uncertainty, and Doubt, but miss enough detail to be easy to refute. http://www.tuxedo.org/~esr/jargon/html/entry/FUD.html
Re: Haskell's efficiency
Thu, 23 Sep 1999 14:19:54 +0900, Manuel M. T. Chakravarty [EMAIL PROTECTED]
pisze:
The fact that the given URL simply produces a "not found" error
message on my machine,
I am sorry, I didn't know it was no longer there. I am putting it in
http://kki.net.pl/qrczak/bridging.ps.gz
PS: I am sorry for the impatient tone. In the Linux
community, posting, such as the cited on, are called
FUD: They spread Fear, Uncertainty, and Doubt, but miss
enough detail to be easy to refute.
I didn't want to repeat what is in the article. Sorry again.
Their intents are certainly pro-Haskell.
--
__("Marcin Kowalczyk * [EMAIL PROTECTED] http://kki.net.pl/qrczak/
\__/ GCS/M d- s+:-- a22 C++$ UL++$ P+++ L++$ E-
^^W++ N+++ o? K? w(---) O? M- V? PS-- PE++ Y? PGP-+ t
QRCZAK 5? X- R tv-- b+++ DI D- G+ e h! r--%++ y-
Re: Haskell's efficiency
On Thu, 23 Sep 1999, Manuel M. T. Chakravarty wrote: [EMAIL PROTECTED] (Marcin 'Qrczak' Kowalczyk) wrote, S.D.Mechveliani [EMAIL PROTECTED] pisze: So far, no clear progrm example appeared in this list to demonstrate Haskell's in-efficiency in comparison to other languages. I have not done benchmarking myself yet, but in http://www.brookes.ac.uk/~p0071749/papers/bridging.ps.gz they describe an algorithm for text formatting. | lines | chars | size(KB) | time(s) | memory(KB) | --+---+---+--+-++ Haskell | 163 | 4640 | 410 |45.2 | 4505 | Modula-2 | 551 | 10005 | 74 |18.6 |356 | C++ | 389 | 5832 | 328 | 3.9 |368 | It is not quite fair because in Modula-2 and C++ all data structures were of fixed size, but... This may lead to a number of different conclusions: * Haskell is hopeless, * the author of the program has no clue about Haskell, * the Haskell compiler is hopeless, * the Haskell interpreter is really only an interpreter, or * the author forgot to pass -O when calling the Haskell compiler. The original URL cited by Kowalczyk seems to be dead, but you can get what I believe is an incarnation of the same work in: http://www.brookes.ac.uk/~p0071749/publications.html#para Please note that this paper does not actually concentrate on a "Haskell vs.the world" comparison, but on the derivation of a new, linear time paragraph formatting algorithm. The date on it was September 9, 1999, so this is pretty much "hot off the press". This version of the paper drops the Modula-2 line and the memory size column; the rest of the new table would look like this: | lines | chars | size(KB) | time(s) | -+---+---+--+--+ Haskell ghc 4.01 | 183 | 4676 | 453 | 4.72 | Haskell hbc 0..4 | 183 | 4676 | 196 |10.34 | C++ g++ 2.90.27 | 416 | 6310 |8 | 0.43 | The C++ code was a direct (by hand) translation of the haskell, except that they did things the way a C++ programmer would do them: using destructive array updates, and data structures that were of fixed size for a given problem. The code size of the C++ version suggests it was dynamically linked to the usual stuff. The text they formatted was the ASCII version of _Far from the Madding Crowd_; clearly a problem of decent size. You can probably learn a lot more from reading the whole paper, and presumably from playing with the code. But that's still a factor of 10 speed difference between the ghc version and the C++ version. This is actually a bit encouraging, I think, but does point out some possible room for improvement. If I had to make a wild guess, I'd bet the major source of performance loss is in the haskell data structures used. While the pedagogical niceness of defining String to be [Char] is obvious, I know that (at least in Hugs98) this can really ruin your day. (Some of you might like to try doing: strace -c your_favorite_standalone_hugs_texthack and note what you see. Then write the equivalent 5-line perl script (:-)) and do the strace exercise again. Ouch. But since the next version of Hugs98 is apparently due out imminently, this situation may well have improved in the new version.) But, man, things are getting *this close*; if it were really true that all ghc needs right now to get in line with C++ on text-formatting problems is a kicking string library and a way for the compiler to know when to use it, then the arguments usually used in favor become much more compelling to a far larger audience. jking
Haskell's efficiency
Juergen Pfitzenmaier [EMAIL PROTECTED] wrote P I dont't care very much how fast a program runs. I care about how P long it takes me to write it. If you take a programming task of P reasonable complexity you will finish *months* earlier using a P --good-- functional language instead of C++. P P Use a functional language and buy a faster computer with the saved P money/time. Marcin Qrczak Kowalczyk [EMAIL PROTECTED] responded K I have to care how fast my programs run. I like writing in Haskell K very much, it's my favorite general-purpose language, but one of the K biggest weak points of Haskell for me is poor efficiency (at least K with ghc, I don't know how fast are other compilers). K [..] So far, no clear progrm example appeared in this list to demonstrate Haskell's in-efficiency in comparison to other languages. Do i mistake? Thus, the recent example with the Cryptarithm solver was a very in-correct comparison, due to the unknown permutation generating order. K "Only 10 times slower than C" may be unacceptable. Most usually, people write programs that are 1000 times slower or faster - depending on the algorithm details, not on the language or system. I would say, 10 times difference in the compiler efficiency costs nothing relatively to the cost of "occasional" algorithmic details. P Use a functional language and buy a faster computer with the saved P money/time. I would rather propose to skip the "money, computer" part, and instead to spend this won time in thinking over the algorithm. This would increase the performance much more. -- Sergey Mechveliani [EMAIL PROTECTED]
Re: Haskell's efficiency
Wed, 22 Sep 1999 14:26:03 +0400 (MSD), S.D.Mechveliani [EMAIL PROTECTED] pisze:
So far, no clear progrm example appeared in this list to demonstrate
Haskell's in-efficiency in comparison to other languages.
I have not done benchmarking myself yet, but in
http://www.brookes.ac.uk/~p0071749/papers/bridging.ps.gz
they describe an algorithm for text formatting.
| lines | chars | size(KB) | time(s) | memory(KB) |
--+---+---+--+-++
Haskell | 163 | 4640 | 410 |45.2 | 4505 |
Modula-2 | 551 | 10005 | 74 |18.6 |356 |
C++ | 389 | 5832 | 328 | 3.9 |368 |
It is not quite fair because in Modula-2 and C++ all data structures
were of fixed size, but...
--
__("Marcin Kowalczyk * [EMAIL PROTECTED] http://kki.net.pl/qrczak/
\__/ GCS/M d- s+:-- a22 C++$ UL++$ P+++ L++$ E-
^^W++ N+++ o? K? w(---) O? M- V? PS-- PE++ Y? PGP-+ t
QRCZAK 5? X- R tv-- b+++ DI D- G+ e h! r--%++ y-
Re: Haskell's efficiency
S.D.Mechveliani wrote: Thus, the recent example with the Cryptarithm solver was a very in-correct comparison, due to the unknown permutation generating order. I did not study the problem in detail, but I think giving it an unsolvable puzzle would force it to try *all* permutations, thus eliminating the order problem. Ralf
