Re: [Haskell-cafe] Re: Why can't Haskell be faster?
Isaac Gouy <[EMAIL PROTECTED]> writes: > Ketil Malde wrote: >> [LOC vs gz as a program complexity metric] > Do either of those make sense as a "program /complexity/ metric"? Sorry, bad choice of words on my part. -k -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
On Nov 3, 2007 5:00 AM, Ryan Dickie <[EMAIL PROTECTED]> wrote: > Lossless File compression, AKA entropy coding, attempts to maximize the > amount of information per bit (or byte) to be as close to the entropy as > possible. Basically, gzip is measuring (approximating) the amount of > "information" contained in the code. Hmmm, interesting idea. > > I think it would be interesting to compare the ratios between raw file size > its entropy (we can come up with a precise metric later). This would show us > how concise the language and code actually is. Yeah, let's all write in bytecode using a hex editor :-D ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
On 11/2/07, Sterling Clover <[EMAIL PROTECTED]> wrote: > > As I understand it, the question is what you want to measure for. > gzip is actually pretty good at, precisely because it removes > boilerplate, reducing programs to something approximating their > complexity. So a higher gzipped size means, at some level, a more > complicated algorithm (in the case, maybe, of lower level languages, > because there's complexity that's not lifted to the compiler). LOC > per language, as I understand it, has been somewhat called into > question as a measure of productivity, but there's still a > correlation between programmers and LOC across languages even if it > wasn't as strong as thought -- on the other hand, bugs per LOC seems > to have been fairly strongly debunked as something constant across > languages. If you want a measure of the language as a language, I > guess LOC/gzipped is a good ratio for how much "noise" it introduces > -- but if you want to measure just pure speed across similar > algorithmic implementations, which, as I understand it, is what the > shootout is all about, then gzipped actually tends to make some sense. > > --S > ___ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > Lossless File compression, AKA entropy coding, attempts to maximize the amount of information per bit (or byte) to be as close to the entropy as possible. Basically, gzip is measuring (approximating) the amount of "information" contained in the code. I think it would be interesting to compare the ratios between raw file size its entropy (we can come up with a precise metric later). This would show us how concise the language and code actually is. --ryan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
As I understand it, the question is what you want to measure for. gzip is actually pretty good at, precisely because it removes boilerplate, reducing programs to something approximating their complexity. So a higher gzipped size means, at some level, a more complicated algorithm (in the case, maybe, of lower level languages, because there's complexity that's not lifted to the compiler). LOC per language, as I understand it, has been somewhat called into question as a measure of productivity, but there's still a correlation between programmers and LOC across languages even if it wasn't as strong as thought -- on the other hand, bugs per LOC seems to have been fairly strongly debunked as something constant across languages. If you want a measure of the language as a language, I guess LOC/gzipped is a good ratio for how much "noise" it introduces -- but if you want to measure just pure speed across similar algorithmic implementations, which, as I understand it, is what the shootout is all about, then gzipped actually tends to make some sense. --S ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
--- Greg Fitzgerald <[EMAIL PROTECTED]> wrote: > >> while LOC is not perfect, gzip is worse. > > the gzip change didn't significantly alter the rankings > > Currently the gzip ratio of C++ to Python is 2.0, which at a glance, > wouldn't sell me on a "less code" argument. a) you're looking at an average, instead try http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&lang=python&lang2=gpp b) we're not trying to sell you on a "less code" argument - it's whatever it is > Although the rank stayed the > same, did the change reduce the magnitude of the victory? c) that will have varied program to program, and do you care which way "the magnitude of victory" moved or do you care that where it moved to makes more sense? For fun, 2 meteor-contest programs, ratios to the python-2 program LOC GZ WC ghc-3 0.981.401.51 gpp-4 3.764.144.22 Look at the python-2 and ghc-3 source and tell us if LOC gave a reasonable indication of relative program size - is ghc-3 really the smaller program? :-) http://shootout.alioth.debian.org/gp4/benchmark.php?test=meteor&lang=all&sort=gz __ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
On Friday 02 November 2007 23:53, Isaac Gouy wrote: > > > Best case you'll end up concluding that the added complexity had > > > no adverse effect on the results. > > Best case would be seeing that the results were corrected against bias > in favour of long-lines, and ranked programs in a way that looks-right > when we look at the program source code side-by-side. Why would you want to subjectively "correct" for "bias" in favour of long lines? > > Or, as has been suggested, count the number of words in the program. > > Again, not perfect (it's possible in some languages to write things > > which has no whitespace, but is still lots of tokens). > > Wouldn't that be "completely arbitrary"? That is not an argument in favour of needlessly adding extra complexity and adopting a practically-irrelevant metric. Why not use the byte count of a PNG encoding of a photograph of the source code written out by hand in blue ballpoint pen? -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/products/?e ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
>> while LOC is not perfect, gzip is worse. > the gzip change didn't significantly alter the rankings Currently the gzip ratio of C++ to Python is 2.0, which at a glance, wouldn't sell me on a "less code" argument. Although the rank stayed the same, did the change reduce the magnitude of the victory? Thanks, Greg ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
On Friday 02 November 2007 20:29, Isaac Gouy wrote: > ...obviously LOC doesn't tell you anything > about how much stuff is on each line, so it doesn't tell you about the > amount of code that was written or the amount of code the developer can > see whilst reading code. Code is almost ubiquitously visualized as a long vertical strip. The width is limited by your screen. Code is then read by scrolling vertically. This is why LOC is a relevant measure: because the area of the code is given by LOC * screen width and is largely unrelated to the subjective "amount of stuff on each line". As you say, imperative languages like C are often formatted such that a lot of right-hand screen real estate is wasted. LOC penalizes such wastage. The same cannot be said for gzipped bytes, which is an entirely irrelevant metric... -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/products/?e ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
igouy2: > > --- Sebastian Sylvan <[EMAIL PROTECTED]> wrote: > -snip- > > It still tells you how much content you can see on a given amount of > > vertical space. > > And why would we care about that? :-) > > > > I think the point, however, is that while LOC is not perfect, gzip is > > worse. > > How do you know? > > > > > Best case you'll end up concluding that the added complexity had > > > no adverse effect on the results. > > Best case would be seeing that the results were corrected against bias > in favour of long-lines, and ranked programs in a way that looks-right > when we look at the program source code side-by-side. > > > > It's completely arbitrary and favours languages wich requires > > you to write tons of book keeping (semantic noise) as it will > > compress down all that redundancy quite a bit (while the programmer > > would still has to write it, and maintain it). > > So gzip is even less useful than LOC, as it actively *hides* the very > > thing you're trying to meassure! You might as well remove it > > alltogether. > > I don't think you've looked at any of the gz rankings, or compared the > source code for any of the programs :-) > > > > Or, as has been suggested, count the number of words in the program. > > Again, not perfect (it's possible in some languages to write things > > which has no whitespace, but is still lots of tokens). > > Wouldn't that be "completely arbitrary"? > I follow the shootout changes fairly often, and the gzip change didn't significantly alter the rankings, though iirc, it did cause perl to drop a few places. Really, its a fine heuristic, given its power/weight ratio. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
--- Sebastian Sylvan <[EMAIL PROTECTED]> wrote: -snip- > It still tells you how much content you can see on a given amount of > vertical space. And why would we care about that? :-) > I think the point, however, is that while LOC is not perfect, gzip is > worse. How do you know? > > Best case you'll end up concluding that the added complexity had > > no adverse effect on the results. Best case would be seeing that the results were corrected against bias in favour of long-lines, and ranked programs in a way that looks-right when we look at the program source code side-by-side. > It's completely arbitrary and favours languages wich requires > you to write tons of book keeping (semantic noise) as it will > compress down all that redundancy quite a bit (while the programmer > would still has to write it, and maintain it). > So gzip is even less useful than LOC, as it actively *hides* the very > thing you're trying to meassure! You might as well remove it > alltogether. I don't think you've looked at any of the gz rankings, or compared the source code for any of the programs :-) > Or, as has been suggested, count the number of words in the program. > Again, not perfect (it's possible in some languages to write things > which has no whitespace, but is still lots of tokens). Wouldn't that be "completely arbitrary"? __ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
On 11/2/07, Isaac Gouy <[EMAIL PROTECTED]> wrote: > How strange that you've snipped out the source code shape comment that > would undermine what you say - obviously LOC doesn't tell you anything > about how much stuff is on each line, so it doesn't tell you about the > amount of code that was written or the amount of code the developer can > see whilst reading code. It still tells you how much content you can see on a given amount of vertical space. I think the point, however, is that while LOC is not perfect, gzip is worse. It's completely arbitrary and favours languages wich requires you to write tons of book keeping (semantic noise) as it will compress down all that redundancy quite a bit (while the programmer would still has to write it, and maintain it). So gzip is even less useful than LOC, as it actively *hides* the very thing you're trying to meassure! You might as well remove it alltogether. Or, as has been suggested, count the number of words in the program. Again, not perfect (it's possible in some languages to write things which has no whitespace, but is still lots of tokens). -- Sebastian Sylvan +44(0)7857-300802 UIN: 44640862 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
--- Jon Harrop <[EMAIL PROTECTED]> wrote: > On Friday 02 November 2007 19:03, Isaac Gouy wrote: > > It's slightly interesting that, while we're happily opining about > LOCs > > and gz, no one has even tried to show that switching from LOCs to > gz > > made a big difference in those "program bulk" rankings, or even > > provided a specific example that they feel shows how gz is > > misrepresentative - all opinion, no data. > > Why gzip and not run-length encoding, Huffman coding, arithmetic > coding, block > sorting, PPM etc.? > > Choosing gzip is completely subjective and there is no logical reason > to think > that gzipped byte count reflects anything of interest. Why waste any > time > studying results in such an insanely stupid metric? Best case you'll > end up > concluding that the added complexity had no adverse effect on the > results. > > In contrast, LOC has obvious objective merits: it reflects the amount > of code > the developer wrote and the amount of code the developer can see > whilst > reading code. How strange that you've snipped out the source code shape comment that would undermine what you say - obviously LOC doesn't tell you anything about how much stuff is on each line, so it doesn't tell you about the amount of code that was written or the amount of code the developer can see whilst reading code. __ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
On Friday 02 November 2007 19:03, Isaac Gouy wrote: > It's slightly interesting that, while we're happily opining about LOCs > and gz, no one has even tried to show that switching from LOCs to gz > made a big difference in those "program bulk" rankings, or even > provided a specific example that they feel shows how gz is > misrepresentative - all opinion, no data. Why gzip and not run-length encoding, Huffman coding, arithmetic coding, block sorting, PPM etc.? Choosing gzip is completely subjective and there is no logical reason to think that gzipped byte count reflects anything of interest. Why waste any time studying results in such an insanely stupid metric? Best case you'll end up concluding that the added complexity had no adverse effect on the results. In contrast, LOC has obvious objective merits: it reflects the amount of code the developer wrote and the amount of code the developer can see whilst reading code. -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/products/?e ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
On 11/2/07, Isaac Gouy <[EMAIL PROTECTED]> wrote: > Ketil Malde wrote: > > > [LOC vs gz as a program complexity metric] > > Do either of those make sense as a "program /complexity/ metric"? You're right! We should be using Kolmogorov complexity instead! I'll go write a program to calculate it for the shootout. Oh wait... Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Why can't Haskell be faster?
Ketil Malde wrote: > [LOC vs gz as a program complexity metric] Do either of those make sense as a "program /complexity/ metric"? Seems to me that's reading a lot more into those measurements than we should. It's slightly interesting that, while we're happily opining about LOCs and gz, no one has even tried to show that switching from LOCs to gz made a big difference in those "program bulk" rankings, or even provided a specific example that they feel shows how gz is misrepresentative - all opinion, no data. (Incidentally LOC measures source code "shape" as much as anything else - programs in statement heavy languages tend to be longer and thinner, and expression heavy languages tend to be shorter and wider.) __ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: [Haskell-cafe] Re: Why can't Haskell be faster?
On 02/11/2007, Bulat Ziganshin <[EMAIL PROTECTED]> wrote: > Hello Sebastian, > > Thursday, November 1, 2007, 9:58:45 PM, you wrote: > > > the ideal. Token count would be good, but then we'd need a parser for > > each language, which is quite a bit of work to do... > > i think that wc (word count) would be good enough approximation > Yes, as long as you police abuse ( eg "if(somevar)somfunccall(foo,bar,baz)"shouldn't be treated as a single word)). -- Sebastian Sylvan +44(0)7857-300802 UIN: 44640862 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: [Haskell-cafe] Re: Why can't Haskell be faster?
Hello Sebastian, Thursday, November 1, 2007, 9:58:45 PM, you wrote: > the ideal. Token count would be good, but then we'd need a parser for > each language, which is quite a bit of work to do... i think that wc (word count) would be good enough approximation -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
"Sebastian Sylvan" <[EMAIL PROTECTED]> writes: [LOC vs gz as a program complexity metric] >> Obviously no simple measure is going to satisfy everyone, but I think the >> gzip measure is more even handed across a range of languages. >> It probably more closely aproximates the amount of mental effort [..] I'm not sure I follow that reasoning? At any rate, I think the ICFP contest is much better as a measure of productivity. But, just like for performance, LOC for the shootout can be used as a micro-benchmark. > Personally I think syntactic noise is highly distracting, and semantic > noise is even worse! This is important - productivity doesn't depend so much on the actual typing, but the ease of refactoring, identifying and fixing bugs, i.e *reading* code. Verbosity means noise, and also lower information content in a screenful of code. I think there were some (Erlang?) papers where they showed a correlation between program size (in LOC), time of development, and possibly number of bugs?) - regardless of language. > Token count would be good, but then we'd need a parser for > each language, which is quite a bit of work to do... Whatever you do, it'll be an approximation, so why not 'wc -w'? With 'wc -c' for J etc where programs can be written as spaceless sequences of symbols. Or just average chars, words and lines? -k -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
Quoting Justin Bailey <[EMAIL PROTECTED]>: Done: http://www.haskell.org/haskellwiki/RuntimeCompilation . Please update it as needed. Thanks! Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: [Haskell-cafe] Re: Why can't Haskell be faster?
Yes, of course. But they don't do partial evaluation. On 11/1/07, Bulat Ziganshin <[EMAIL PROTECTED]> wrote: > > Hello Lennart, > > Thursday, November 1, 2007, 2:45:49 AM, you wrote: > > > But yeah, a code generator at run time is a very cool idea, and one > > that has been studied, but not enough. > > vm-based languages (java, c#) has runtimes that compile bytecode to > the native code at runtime > > -- > Best regards, > Bulatmailto:[EMAIL PROTECTED] > > ___ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
On 01/11/2007, Tim Newsham <[EMAIL PROTECTED]> wrote: > > Unfortunately, they replaced line counts with bytes of gzip'ed code -- > > while the former certainly has its problems, I simply cannot imagine > > what relevance the latter has (beyond hiding extreme amounts of > > repetitive boilerplate in certain languages). > > Sounds pretty fair to me. Programming is a job of compressing a solution > set. Excessive boilerplate might mean that you have to type a lot, but > doesn't necessarily mean that you have to think a lot. I think the > previous line count was skewed in favor of very terse languages like > haskell, especially languages that let you put many ideas onto a single > line. At the very least there should be a constant factor applied when > comparing haskell line counts to python line counts, for example. > (python has very strict rules about putting multiple things on the same > line). > > Obviously no simple measure is going to satisfy everyone, but I think the > gzip measure is more even handed across a range of languages. It probably > more closely aproximates the amount of mental effort and hence time it > requires to construct a program (ie. I can whip out a lot of lines of code > in python very quickly, but it takes a lot more of them to do the same > work as a single, dense, line of haskell code). > > > When we compete against Python and its ilk, we do so for programmer > > productivity first, and performance second. LOC was a nice measure, > > and encouraged terser and more idiomatic programs than the current > > crop of performance-tweaked low-level stuff. > > The haskell entries to the shootout are very obviously written for speed > and not elegance. If you want to do better on the LoC measure, you can > definitely do so (at the expense of speed). > Personally I think syntactic noise is highly distracting, and semantic noise is even worse! Gzip'd files don't show you that one language will require you to do 90% book-keeping for 10% algorithm, while the other lets you get on with the job, it may make it look as if both languages are roughly equally good at letting the programmer focus on the important bits. I'm not sure what metric to use, but actively disgusing noisy languages using compression sure doesn't seem like anywhere close to the ideal. Token count would be good, but then we'd need a parser for each language, which is quite a bit of work to do... -- Sebastian Sylvan +44(0)7857-300802 UIN: 44640862 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
Unfortunately, they replaced line counts with bytes of gzip'ed code -- while the former certainly has its problems, I simply cannot imagine what relevance the latter has (beyond hiding extreme amounts of repetitive boilerplate in certain languages). Sounds pretty fair to me. Programming is a job of compressing a solution set. Excessive boilerplate might mean that you have to type a lot, but doesn't necessarily mean that you have to think a lot. I think the previous line count was skewed in favor of very terse languages like haskell, especially languages that let you put many ideas onto a single line. At the very least there should be a constant factor applied when comparing haskell line counts to python line counts, for example. (python has very strict rules about putting multiple things on the same line). Obviously no simple measure is going to satisfy everyone, but I think the gzip measure is more even handed across a range of languages. It probably more closely aproximates the amount of mental effort and hence time it requires to construct a program (ie. I can whip out a lot of lines of code in python very quickly, but it takes a lot more of them to do the same work as a single, dense, line of haskell code). When we compete against Python and its ilk, we do so for programmer productivity first, and performance second. LOC was a nice measure, and encouraged terser and more idiomatic programs than the current crop of performance-tweaked low-level stuff. The haskell entries to the shootout are very obviously written for speed and not elegance. If you want to do better on the LoC measure, you can definitely do so (at the expense of speed). -k Tim Newsham http://www.thenewsh.com/~newsham/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
On 10/31/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote: > I didn't keep a copy, but if someone wants to retrieve it from the Google > cache and put it on the new wiki (under the new licence, of course), please > do so. > > Cheers, > Andrew Bromage Done: http://www.haskell.org/haskellwiki/RuntimeCompilation . Please update it as needed. Justin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
Ketil Malde wrote: Python used to do pretty well here compared to Haskell, with rather efficient hashes and text parsing, although I suspect ByteString IO and other optimizations may have changed that now. It still does just fine. For typical "munge a file with regexps, lists, and maps" tasks, Python and Perl remain on par with comparably written Haskell. This because the scripting-level code acts as a thin layer of glue around I/O, regexps, lists, and dicts, all of which are written in native code. The Haskell regexp libraries actually give us something of a leg down with respect to Python and Perl. The aggressive use of polymorphism in the return type of (=~) makes it hard to remember which of the possible return types gives me what information. Not only did I write a regexp tutorial to understand the API in the first place, I have to reread it every time I want to match a regexp. A suitable solution would be a return type of RegexpMatch a => Maybe a (to live alongside the existing types, but aiming to become the one that's easy to remember), with appropriate methods on a, but I don't have time to write up a patch. http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Re: Why can't Haskell be faster?
http://hackage.haskell.org/trac/ghc/wiki/Commentary | -Original Message- | From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Paulo J. Matos | Sent: 01 November 2007 13:42 | To: Simon Peyton-Jones | Cc: Neil Mitchell; Stefan O'Rear; [EMAIL PROTECTED]; haskell-cafe@haskell.org | Subject: Re: [Haskell-cafe] Re: Why can't Haskell be faster? | | On 01/11/2007, Simon Peyton-Jones <[EMAIL PROTECTED]> wrote: | > Yes, that's right. We'll be doing a lot more work on the code generator in the rest of this year and 2008. | Here "we" includes Norman Ramsey and John Dias, as well as past interns Michael Adams and Ben Lippmeier, so we | have real muscle! | > | | That's very good to know. I wonder where could I read more about | current state of the art on Haskell compilation techniques and about | the implementation of ghc in general? | Is there a book on it or maybe some group of papers that would aid me | to understand it? | | Cheers, | | Paulo Matos | | > Simon | > | > | > I don't think the register allocater is being rewritten so much as it is | > | > being written: | > | | > | >From talking to Ben, who rewrote the register allocator over the | > | summer, he said that the new graph based register allocator is pretty | > | good. The thing that is holding it back is the CPS conversion bit, | > | which was also being rewritten over the summer, but didn't get | > | finished. I think these are both things which are likely to be done | > | for 6.10. | > | | > | Thanks | > | | > | Neil | > | ___ | > | Haskell-Cafe mailing list | > | Haskell-Cafe@haskell.org | > | http://www.haskell.org/mailman/listinfo/haskell-cafe | > ___ | > Haskell-Cafe mailing list | > Haskell-Cafe@haskell.org | > http://www.haskell.org/mailman/listinfo/haskell-cafe | > | > | > | | | -- | Paulo Jorge Matos - pocm at soton.ac.uk | http://www.personal.soton.ac.uk/pocm | PhD Student @ ECS | University of Southampton, UK ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
On 01/11/2007, Simon Peyton-Jones <[EMAIL PROTECTED]> wrote: > Yes, that's right. We'll be doing a lot more work on the code generator in > the rest of this year and 2008. Here "we" includes Norman Ramsey and John > Dias, as well as past interns Michael Adams and Ben Lippmeier, so we have > real muscle! > That's very good to know. I wonder where could I read more about current state of the art on Haskell compilation techniques and about the implementation of ghc in general? Is there a book on it or maybe some group of papers that would aid me to understand it? Cheers, Paulo Matos > Simon > > | > I don't think the register allocater is being rewritten so much as it is > | > being written: > | > | >From talking to Ben, who rewrote the register allocator over the > | summer, he said that the new graph based register allocator is pretty > | good. The thing that is holding it back is the CPS conversion bit, > | which was also being rewritten over the summer, but didn't get > | finished. I think these are both things which are likely to be done > | for 6.10. > | > | Thanks > | > | Neil > | ___ > | Haskell-Cafe mailing list > | Haskell-Cafe@haskell.org > | http://www.haskell.org/mailman/listinfo/haskell-cafe > ___ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > > > -- Paulo Jorge Matos - pocm at soton.ac.uk http://www.personal.soton.ac.uk/pocm PhD Student @ ECS University of Southampton, UK ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
Neil wrote: The Clean and Haskell languages both reduce to pretty much the same Core language, with pretty much the same type system, once you get down to it - so I don't think the difference between the performance is a language thing, but it is a compiler thing. The uniqueness type stuff may give Clean a slight benefit, but I'm not sure how much they use that in their analyses. From what I know from the Nijmegen team, having the uniqueness information available and actually using it for code generation does allow for an impressive speed-up. The thing is: in principle, there is, I think, no reason why we can't do the same thing for Haskell. Of course, the Clean languages exposes uniqueness types at its surface level, but that is in no way essential to the underlying analysis. Exposing uniqueness types is, in that sense, just an alternative to monadic encapsulation of side effects. So, a Haskell compiler could just implement a uniqueness analysis under the hood and use the results for generating code that does in-place updates that are guaranteed to maintain referential transparency. Interestingly---but now I'm shamelessly plugging a paper of Jurriaan Hage, Arie Middelkoop, and myself, presented at this year's ICFP [*]---such an analysis is very similar to sharing analysis, which may be used by compilers for lazy languages to avoid unnecessary thunk updates. Cheers, Stefan [*] Jurriaan Hage, Stefan Holdermans, and Arie Middelkoop. A generic usage analysis with subeffect qualifiers. In Ralf Hinze and Norman Ramsey, editors, Proceedings of the 12th ACM SIGPLAN International Conference on Functional Programming, ICFP 2007, Freiburg, Germany, October 1–-3, pages 235–-246. ACM Press, 2007. http://doi.acm.org/ 10.1145/1291151.1291189. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
Bernie wrote: I discussed this with Rinus Plasmeijer (chief designer of Clean) a couple of years ago, and if I remember correctly, he said that the native code generator in Clean was very good, and a significant reason why Clean produces (relatively) fast executables. I think he said that they had an assembly programming guru on their team. (Apologies to Rinus if I am mis-remembering the conversation). That guru would be John van Groningen... If I understood correctly, and I think I did, John is now working on a Haskell front end for the Clean compiler---which is actually quite interesting in the light of the present discussion. Cheers, Stefan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Re: Why can't Haskell be faster?
Yes, that's right. We'll be doing a lot more work on the code generator in the rest of this year and 2008. Here "we" includes Norman Ramsey and John Dias, as well as past interns Michael Adams and Ben Lippmeier, so we have real muscle! Simon | > I don't think the register allocater is being rewritten so much as it is | > being written: | | >From talking to Ben, who rewrote the register allocator over the | summer, he said that the new graph based register allocator is pretty | good. The thing that is holding it back is the CPS conversion bit, | which was also being rewritten over the summer, but didn't get | finished. I think these are both things which are likely to be done | for 6.10. | | Thanks | | Neil | ___ | Haskell-Cafe mailing list | Haskell-Cafe@haskell.org | http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
I assume the reason the switched away from LOC is to prevent programmers artificially reducing their LOC count, e.g. by using a = 5; b = 6; rather than a = 5; b = 6; in languages where newlines aren't syntactically significant. When gzipped, I guess that the ";\n" string will be represented about as efficiently as just the single semi-colon. On 01/11/2007, Ketil Malde <[EMAIL PROTECTED]> wrote: > Don Stewart <[EMAIL PROTECTED]> writes: > > > goalieca: > > >>So in a few years time when GHC has matured we can expect performance to > >>be on par with current Clean? So Clean is a good approximation to peak > >>performance? > > If I remember the numbers, Clean is pretty close to C for most > benchmarks, so I guess it is fair to say it is a good approximation to > practical peak performance. > > Which proves that it is possible to write efficient low-level code in > Clean. > > > And remember usually Haskell is competing against 'high level' languages > > like python for adoption, where we're 5-500x faster anyway... > > Unfortunately, they replaced line counts with bytes of gzip'ed code -- > while the former certainly has its problems, I simply cannot imagine > what relevance the latter has (beyond hiding extreme amounts of > repetitive boilerplate in certain languages). > > When we compete against Python and its ilk, we do so for programmer > productivity first, and performance second. LOC was a nice measure, > and encouraged terser and more idiomatic programs than the current > crop of performance-tweaked low-level stuff. > > BTW, Python isn't so bad, performance wise. Much of what I do > consists of reading some files, building up some hashes (associative > arrays or finite maps, depending on where you come from :-), and > generating some output. Python used to do pretty well here compared > to Haskell, with rather efficient hashes and text parsing, although I > suspect ByteString IO and other optimizations may have changed that > now. > > -k > -- > If I haven't seen further, it is by standing in the footprints of giants > ___ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: [Haskell-cafe] Re: Why can't Haskell be faster?
Hello Lennart, Thursday, November 1, 2007, 2:45:49 AM, you wrote: > But yeah, a code generator at run time is a very cool idea, and one > that has been studied, but not enough. vm-based languages (java, c#) has runtimes that compile bytecode to the native code at runtime -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
Don Stewart <[EMAIL PROTECTED]> writes: > goalieca: >>So in a few years time when GHC has matured we can expect performance to >>be on par with current Clean? So Clean is a good approximation to peak >>performance? If I remember the numbers, Clean is pretty close to C for most benchmarks, so I guess it is fair to say it is a good approximation to practical peak performance. Which proves that it is possible to write efficient low-level code in Clean. > And remember usually Haskell is competing against 'high level' languages > like python for adoption, where we're 5-500x faster anyway... Unfortunately, they replaced line counts with bytes of gzip'ed code -- while the former certainly has its problems, I simply cannot imagine what relevance the latter has (beyond hiding extreme amounts of repetitive boilerplate in certain languages). When we compete against Python and its ilk, we do so for programmer productivity first, and performance second. LOC was a nice measure, and encouraged terser and more idiomatic programs than the current crop of performance-tweaked low-level stuff. BTW, Python isn't so bad, performance wise. Much of what I do consists of reading some files, building up some hashes (associative arrays or finite maps, depending on where you come from :-), and generating some output. Python used to do pretty well here compared to Haskell, with rather efficient hashes and text parsing, although I suspect ByteString IO and other optimizations may have changed that now. -k -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
G'day all. Quoting Derek Elkins <[EMAIL PROTECTED]>: Probably RuntimeCompilation (or something like that and linked from the Knuth-Morris-Pratt implementation on HaWiki) written by Andrew Bromage. I didn't keep a copy, but if someone wants to retrieve it from the Google cache and put it on the new wiki (under the new licence, of course), please do so. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
On 01/11/2007, at 2:37 AM, Neil Mitchell wrote: My guess is that the native code generator in Clean beats GHC, which wouldn't be too surprising as GHC is currently rewriting its CPS and Register Allocator to produce better native code. I discussed this with Rinus Plasmeijer (chief designer of Clean) a couple of years ago, and if I remember correctly, he said that the native code generator in Clean was very good, and a significant reason why Clean produces (relatively) fast executables. I think he said that they had an assembly programming guru on their team. (Apologies to Rinus if I am mis-remembering the conversation). At the time I was impressed by how fast Clean could recompile itself. Cheers, Bernie. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
On Thu, Nov 01, 2007 at 02:30:17AM +, Neil Mitchell wrote: > Hi > > > I don't think the register allocater is being rewritten so much as it is > > being written: > > >From talking to Ben, who rewrote the register allocator over the > summer, he said that the new graph based register allocator is pretty > good. The thing that is holding it back is the CPS conversion bit, > which was also being rewritten over the summer, but didn't get > finished. I think these are both things which are likely to be done > for 6.10. Oh, that's good news. I look forward to a massive increase in the performance of GHC-compiled programs, most specifically GHC itself. Stefan signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
Hi > I don't think the register allocater is being rewritten so much as it is > being written: >From talking to Ben, who rewrote the register allocator over the summer, he said that the new graph based register allocator is pretty good. The thing that is holding it back is the CPS conversion bit, which was also being rewritten over the summer, but didn't get finished. I think these are both things which are likely to be done for 6.10. Thanks Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
On Wed, Oct 31, 2007 at 03:37:12PM +, Neil Mitchell wrote: > Hi > > I've been working on optimising Haskell for a little while > (http://www-users.cs.york.ac.uk/~ndm/supero/), so here are my thoughts > on this. The Clean and Haskell languages both reduce to pretty much > the same Core language, with pretty much the same type system, once > you get down to it - so I don't think the difference between the > performance is a language thing, but it is a compiler thing. The > uniqueness type stuff may give Clean a slight benefit, but I'm not > sure how much they use that in their analyses. > > Both Clean and GHC do strictness analysis - I don't know which one > does better, but both do quite well. I think Clean has some > generalised fusion framework, while GHC relies on rules and short-cut > deforestation. GHC goes through C-- to C or ASM, while Clean has been > generating native code for a lot longer. GHC is based on the STG > machine, while Clean is based on the ABC machine - not sure which is > better, but there are differences there. > > My guess is that the native code generator in Clean beats GHC, which > wouldn't be too surprising as GHC is currently rewriting its CPS and > Register Allocator to produce better native code. I don't think the register allocater is being rewritten so much as it is being written: [EMAIL PROTECTED]:/tmp$ cat X.hs module X where import Foreign import Data.Int memset :: Ptr Int32 -> Int32 -> Int -> IO () memset p v i = p `seq` v `seq` case i of 0 -> return () _ -> poke p v >> memset (p `plusPtr` sizeOf v) v (i - 1) [EMAIL PROTECTED]:/tmp$ ghc -fbang-patterns -O2 -c -fforce-recomp -ddump-asm X.hs ... X_zdwa_info: movl 8(%ebp),%eax testl %eax,%eax jne .LcH6 movl $base_GHCziBase_Z0T_closure+1,%esi addl $12,%ebp jmp *(%ebp) .LcH6: movl 4(%ebp),%ecx movl (%ebp),%edx movl %ecx,(%edx) movl (%ebp),%ecx addl $4,%ecx decl %eax movl %eax,8(%ebp) movl %ecx,(%ebp) jmp X_zdwa_info ... Admittedly that's better than it used to be (I recall 13 memory references last time I tested it), but still... the reason for your performance woes should be quite obvious in that snippet. Stefan signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
On Wed, 2007-10-31 at 23:44 +0100, Henning Thielemann wrote: > On Wed, 31 Oct 2007, Dan Piponi wrote: > > > But every day, while coding at work (in C++), I see situations where > > true partial evaluation would give a big performance payoff, and yet > > there are so few languages that natively support it. Of course it > > would require part of the compiler to be present in the runtime. But > > by generating code in inner loops specialised to the data at hand it > > could easily outperform C code in a wide variety of real world code. I > > know there has been some research in this area, and some commercial > > C++ products for partial evaluation have appeared, so I'd love to see > > it in an easy to use Haskell form one day. > > I weakly remember an article on Hawiki about that ... Probably RuntimeCompilation (or something like that and linked from the Knuth-Morris-Pratt implementation on HaWiki) written by Andrew Bromage. > > If you write > > foo :: X -> Y -> Z > foo x = > let bar y = ... x ... y ... > in bar > > would this give you true partial evaluation? No. Partial evaluation (usually) implies a heck of a lot more than what you are trying to do. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
There are many ways to implement currying. And even with GHC you can get it to do some work given one argument if you write the function the right way. I've used this in some code where it was crucial. But yeah, a code generator at run time is a very cool idea, and one that has been studied, but not enough. -- Lennart On 10/31/07, Dan Piponi <[EMAIL PROTECTED]> wrote: > > On 10/31/07, Neil Mitchell <[EMAIL PROTECTED]> wrote: > > in the long run Haskell should be aiming for equivalence with highly > > optimised C. > > Really, that's not very ambitious. Haskell should be setting its > sights higher. :-) > > When I first started reading about Haskell I misunderstood what > currying was all about. I thought that if you provided one argument to > a two argument function, say, then it'd do partial evaluation. Very I > soon I was sorely let down as I discovered that it simply made a > closure that waits for the second argument to arrive so the reduction > can be carried out. > > But every day, while coding at work (in C++), I see situations where > true partial evaluation would give a big performance payoff, and yet > there are so few languages that natively support it. Of course it > would require part of the compiler to be present in the runtime. But > by generating code in inner loops specialised to the data at hand it > could easily outperform C code in a wide variety of real world code. I > know there has been some research in this area, and some commercial > C++ products for partial evaluation have appeared, so I'd love to see > it in an easy to use Haskell form one day. > > Just dreaming, I know... > -- > Dan > ___ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Why can't Haskell be faster?
I'd like to see Supero and Jhc - compiled examples in the language shootout. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Why can't Haskell be faster?
The site claims it is quite up to date: about Haskell GHC The Glorious Glasgow Haskell Compilation System, version 6.6 Examples are compiled mostly in the middle of this year and at least -O was used. Each test has a log available. They are good at documenting what they do. Peter. Peter Verswyvelen wrote: Are these benchmarks still up-to-date? When I started learning FP, I had to choose between Haskell and Clean, so I made a couple of little programs in both. GHC 6.6.1 with -O was faster in most cases, sometimes a lot faster... I don't have the source code anymore, but it was based on the book "The Haskell road to math & logic". However, the Clean compiler itself is really fast, which is nice, it reminds me to the feeling I had with Turbo Pascal under DOS :-) I find GHC rather slow in compilation. But that is another topic of course. Peter ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
On Wed, 31 Oct 2007, Dan Piponi wrote: > But every day, while coding at work (in C++), I see situations where > true partial evaluation would give a big performance payoff, and yet > there are so few languages that natively support it. Of course it > would require part of the compiler to be present in the runtime. But > by generating code in inner loops specialised to the data at hand it > could easily outperform C code in a wide variety of real world code. I > know there has been some research in this area, and some commercial > C++ products for partial evaluation have appeared, so I'd love to see > it in an easy to use Haskell form one day. I weakly remember an article on Hawiki about that ... If you write foo :: X -> Y -> Z foo x = let bar y = ... x ... y ... in bar would this give you true partial evaluation? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
On 10/31/07, Neil Mitchell <[EMAIL PROTECTED]> wrote: > in the long run Haskell should be aiming for equivalence with highly > optimised C. Really, that's not very ambitious. Haskell should be setting its sights higher. :-) When I first started reading about Haskell I misunderstood what currying was all about. I thought that if you provided one argument to a two argument function, say, then it'd do partial evaluation. Very I soon I was sorely let down as I discovered that it simply made a closure that waits for the second argument to arrive so the reduction can be carried out. But every day, while coding at work (in C++), I see situations where true partial evaluation would give a big performance payoff, and yet there are so few languages that natively support it. Of course it would require part of the compiler to be present in the runtime. But by generating code in inner loops specialised to the data at hand it could easily outperform C code in a wide variety of real world code. I know there has been some research in this area, and some commercial C++ products for partial evaluation have appeared, so I'd love to see it in an easy to use Haskell form one day. Just dreaming, I know... -- Dan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
Hi > So in a few years time when GHC has matured we can expect performance to be > on par with current Clean? So Clean is a good approximation to peak > performance? No. The performance of many real world programs could be twice as fast at least, I'm relatively sure. Clean is a good short term target, but in the long run Haskell should be aiming for equivalence with highly optimised C. Thanks Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
On 31/10/2007, Don Stewart <[EMAIL PROTECTED]> wrote: > goalieca: > >So in a few years time when GHC has matured we can expect performance to > >be on par with current Clean? So Clean is a good approximation to peak > >performance? > > > > The current Clean compiler, for micro benchmarks, seems to be rather > good, yes. Any slowdown wrt. the same program in Clean could be > considered a bug in GHC... > > And remember usually Haskell is competing against 'high level' languages > like python for adoption, where we're 5-500x faster anyway... Not so sure about that last thing. I'd love to use Haskell for performance, in other words use it because it makes it easier to write parallel and concurrent programs (NDP and STM mainly, though I wouldn't mind some language support for message passing, and perhaps Sing#-style static protocol specifications, with some high degree of inference). Anyway, in order for that to be reasonable I think it's important that even the sequential code (where actual data dependencies enforce evaluation sequence) runs very quickly, otherwise we'll lose out to some C-based language (written with 10x the effort) again when we start bumping into the wall of Almdahls law... -- Sebastian Sylvan +44(0)7857-300802 UIN: 44640862 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
goalieca: >So in a few years time when GHC has matured we can expect performance to >be on par with current Clean? So Clean is a good approximation to peak >performance? > The current Clean compiler, for micro benchmarks, seems to be rather good, yes. Any slowdown wrt. the same program in Clean could be considered a bug in GHC... And remember usually Haskell is competing against 'high level' languages like python for adoption, where we're 5-500x faster anyway... -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
So in a few years time when GHC has matured we can expect performance to be on par with current Clean? So Clean is a good approximation to peak performance? --ryan On 10/31/07, Don Stewart <[EMAIL PROTECTED]> wrote: > > ndmitchell: > > Hi > > > > I've been working on optimising Haskell for a little while > > (http://www-users.cs.york.ac.uk/~ndm/supero/), so here are my thoughts > > on this. The Clean and Haskell languages both reduce to pretty much > > the same Core language, with pretty much the same type system, once > > you get down to it - so I don't think the difference between the > > performance is a language thing, but it is a compiler thing. The > > uniqueness type stuff may give Clean a slight benefit, but I'm not > > sure how much they use that in their analyses. > > > > Both Clean and GHC do strictness analysis - I don't know which one > > does better, but both do quite well. I think Clean has some > > generalised fusion framework, while GHC relies on rules and short-cut > > deforestation. GHC goes through C-- to C or ASM, while Clean has been > > generating native code for a lot longer. GHC is based on the STG > > machine, while Clean is based on the ABC machine - not sure which is > > better, but there are differences there. > > > > My guess is that the native code generator in Clean beats GHC, which > > wouldn't be too surprising as GHC is currently rewriting its CPS and > > Register Allocator to produce better native code. > > Yes, this was my analysis too -- its in the native code gen. Which is > perhaps the main GHC bottleneck now. > > -- Don > ___ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
ndmitchell: > Hi > > I've been working on optimising Haskell for a little while > (http://www-users.cs.york.ac.uk/~ndm/supero/), so here are my thoughts > on this. The Clean and Haskell languages both reduce to pretty much > the same Core language, with pretty much the same type system, once > you get down to it - so I don't think the difference between the > performance is a language thing, but it is a compiler thing. The > uniqueness type stuff may give Clean a slight benefit, but I'm not > sure how much they use that in their analyses. > > Both Clean and GHC do strictness analysis - I don't know which one > does better, but both do quite well. I think Clean has some > generalised fusion framework, while GHC relies on rules and short-cut > deforestation. GHC goes through C-- to C or ASM, while Clean has been > generating native code for a lot longer. GHC is based on the STG > machine, while Clean is based on the ABC machine - not sure which is > better, but there are differences there. > > My guess is that the native code generator in Clean beats GHC, which > wouldn't be too surprising as GHC is currently rewriting its CPS and > Register Allocator to produce better native code. Yes, this was my analysis too -- its in the native code gen. Which is perhaps the main GHC bottleneck now. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
Hi I've been working on optimising Haskell for a little while (http://www-users.cs.york.ac.uk/~ndm/supero/), so here are my thoughts on this. The Clean and Haskell languages both reduce to pretty much the same Core language, with pretty much the same type system, once you get down to it - so I don't think the difference between the performance is a language thing, but it is a compiler thing. The uniqueness type stuff may give Clean a slight benefit, but I'm not sure how much they use that in their analyses. Both Clean and GHC do strictness analysis - I don't know which one does better, but both do quite well. I think Clean has some generalised fusion framework, while GHC relies on rules and short-cut deforestation. GHC goes through C-- to C or ASM, while Clean has been generating native code for a lot longer. GHC is based on the STG machine, while Clean is based on the ABC machine - not sure which is better, but there are differences there. My guess is that the native code generator in Clean beats GHC, which wouldn't be too surprising as GHC is currently rewriting its CPS and Register Allocator to produce better native code. Thanks Neil On 10/31/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote: > > Peter Hercek wrote: > > * it is easy to mark stuff strict (even in function signatures > > etc), so it is possible to save on unnecessary CAF creations > > Also, the Clean compiler has a strictness analyzer. The compiler will > analyze code and find many (but not all) cases where a function argument can > be made strict without changing the behavior of the program. > > ___ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > > ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Why can't Haskell be faster?
Peter Hercek wrote: > * it is easy to mark stuff strict (even in function signatures > etc), so it is possible to save on unnecessary CAF creations Also, the Clean compiler has a strictness analyzer. The compiler will analyze code and find many (but not all) cases where a function argument can be made strict without changing the behavior of the program. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
Robin Green wrote: On Wed, 31 Oct 2007 14:17:13 + Jules Bean <[EMAIL PROTECTED]> wrote: Specifically, clean's uniqueness types allow for a certain kind of zero-copy mutation optimisation which is much harder for a haskell compiler to automatically infer. It's not clear to me that it's actually worth it, but I think that's the point at issue. I can *imagine* algorithms in which copying is actually faster than mutation, if copying gives you better locality. If you want in-place update in Haskell, you can use the ST monad, or IORefs. Yes, you have to refactor code, but anecdotally, uniqueness types aren't without problems either - you can make one small change and your code no longer satisfies the uniqueness condition. IORefs don't give you in-place update. They give you mutation, but new values are still allocated in new heap. foo <- newIORef "hi" writeIORef foo "bye" -- "bye" is a new string, allocated in new heap. the only thing that got -- mutated was a pointer. STArrays and certain IO Arrays give you in-place update, though. Jules ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
On Wed, 31 Oct 2007 14:17:13 + Jules Bean <[EMAIL PROTECTED]> wrote: > Specifically, clean's uniqueness types allow for a certain kind of > zero-copy mutation optimisation which is much harder for a haskell > compiler to automatically infer. It's not clear to me that it's > actually worth it, but I think that's the point at issue. I can > *imagine* algorithms in which copying is actually faster than > mutation, if copying gives you better locality. If you want in-place update in Haskell, you can use the ST monad, or IORefs. Yes, you have to refactor code, but anecdotally, uniqueness types aren't without problems either - you can make one small change and your code no longer satisfies the uniqueness condition. -- Robin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
Paulo J. Matos wrote: type system? Why is that? Shouldn't type system in fact speed up the generated code, since it will know all types at compile time? The *existence* of a type system is helpful to the compiler. Peter was referring to the differences between haskell and clean. Specifically, clean's uniqueness types allow for a certain kind of zero-copy mutation optimisation which is much harder for a haskell compiler to automatically infer. It's not clear to me that it's actually worth it, but I think that's the point at issue. I can *imagine* algorithms in which copying is actually faster than mutation, if copying gives you better locality. Jules ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
Paulo J. Matos wrote: So the slowness of Haskell (compared to Clean) is consequence of its type system. OK, I'll stop, I did not write Clean nor Haskell optimizers or stuff like that :-D type system? Why is that? Shouldn't type system in fact speed up the generated code, since it will know all types at compile time? Yes, but apparently the Clean type system gives more information to the compiler than the Haskell system does. The Haskell type system doesn't say that a certain value can be updated in-place or that a certain value should not be boxed (not counting the GHC extension for unboxed types). Reinier ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
On 31/10/2007, Peter Hercek <[EMAIL PROTECTED]> wrote: > Add to that better unbox / box annotations, this may make even > bigger difference than the strictness stuff because it allows > you to avoid a lot of indirect references do data. > > Anyway, if Haskell would do some kind of whole program analyzes > and transformations it probably can mitigate all the problems > to a certain degree. > So, I might assert that it is not a problem of the Haskell language itself, it is a problem with the compiler. Which means that with enough effort it would be possible for the compiler to generate compiled code with performance as good as Clean. > So the slowness of Haskell (compared to Clean) is consequence of > its type system. OK, I'll stop, I did not write Clean nor Haskell > optimizers or stuff like that :-D > type system? Why is that? Shouldn't type system in fact speed up the generated code, since it will know all types at compile time? > Peter. > > Peter Hercek wrote: > > I'm curious what experts think too. > > > > So far I just guess it is because of clean type system getting > > better hints for optimizations: > > > > * it is easy to mark stuff strict (even in function signatures > > etc), so it is possible to save on unnecessary CAF creations > > > > * uniqueness types allow to do in-place modifications (instead > > of creating a copy of an object on heap and modifying the copy), > > so you save GC time and also improve cache hit performance > > > > Peter. > > ___ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > > > -- Paulo Jorge Matos - pocm at soton.ac.uk http://www.personal.soton.ac.uk/pocm PhD Student @ ECS University of Southampton, UK ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why can't Haskell be faster?
On 31/10/2007, Peter Hercek <[EMAIL PROTECTED]> wrote: > Anyway, if Haskell would do some kind of whole program analyzes > and transformations it probably can mitigate all the problems > to a certain degree. > I think JHC is supposed to do whole-program optimisations. Rumour has it that its Hello World examples are the fastest around - I have heard it has problems with larger code bases though. ;-) What's the current state of play on this? D. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Why can't Haskell be faster?
Add to that better unbox / box annotations, this may make even bigger difference than the strictness stuff because it allows you to avoid a lot of indirect references do data. Anyway, if Haskell would do some kind of whole program analyzes and transformations it probably can mitigate all the problems to a certain degree. So the slowness of Haskell (compared to Clean) is consequence of its type system. OK, I'll stop, I did not write Clean nor Haskell optimizers or stuff like that :-D Peter. Peter Hercek wrote: I'm curious what experts think too. So far I just guess it is because of clean type system getting better hints for optimizations: * it is easy to mark stuff strict (even in function signatures etc), so it is possible to save on unnecessary CAF creations * uniqueness types allow to do in-place modifications (instead of creating a copy of an object on heap and modifying the copy), so you save GC time and also improve cache hit performance Peter. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Why can't Haskell be faster?
I'm curious what experts think too. So far I just guess it is because of clean type system getting better hints for optimizations: * it is easy to mark stuff strict (even in function signatures etc), so it is possible to save on unnecessary CAF creations * uniqueness types allow to do in-place modifications (instead of creating a copy of an object on heap and modifying the copy), so you save GC time and also improve cache hit performance Peter. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe