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

On 31/10/2007, Don Stewart 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

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

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

Hi Bryan, I wrote the current regex API, so your suggestions are interesting to me. The also goes for anyone else's regex API opinions, of course. Bryan O'Sullivan wrote:

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.

True, the pure Haskell library is not as fast as a C library. In particular, the current regex-tdfa handles lazy bytestring in a sub-optimal manner. This may eventually be fixed. But the native code libraries have also been wrapped in the same API, and they are quite fast when combined with strict ByteStrings.

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.

The (=~) operator uses many return types provided by the instances of RegexContext. These are all thin wrappers around the unpolymorphic return types of the RegexLike class. So (=~) could be avoided altogether, or another API created.

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.

The (=~~) is the monadic wrapper for (=~) to allow for different failure behaviors. So using (=~~) with Maybe is already possible, and gives Nothing whenever there are zero matches. But more interesting to me is learning what API you would like to see. What would you like the code that uses the API to be? Could you sketch either the definition or usage of your RegexMatch class suggestion? I don't use my own regex API much, so external feedback and ideas would be wonderful. -- Chris

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/

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, Bulat mailto:Bulat.Ziganshin@gmail.com

"Sebastian Sylvan" 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

On 10/31/07, Neil Mitchell 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

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.

On 10/31/07, ajb@spamcop.net 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

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

On 10/31/07, Neil Mitchell 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

Yes, of course. But they don't do partial evaluation. On 11/1/07, Bulat Ziganshin 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, Bulat mailto:Bulat.Ziganshin@gmail.com

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

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

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

http://hackage.haskell.org/trac/ghc/wiki/Commentary | -----Original Message----- | From: pocmatos@gmail.com [mailto:pocmatos@gmail.com] On Behalf Of Paulo J. Matos | Sent: 01 November 2007 13:42 | To: Simon Peyton-Jones | Cc: Neil Mitchell; Stefan O'Rear; Jeff.Harper@handheld.com; haskell-cafe@haskell.org | Subject: Re: [Haskell-cafe] Re: Why can't Haskell be faster? | | On 01/11/2007, Simon Peyton-Jones 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

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

Stefan Holdermans wrote:

Exposing uniqueness types is, in that sense, just an alternative to monadic encapsulation of side effects.

While *World -> (a, *World) seems to work in practice, I wonder what its (denotational) semantics are. I mean, the two programs loop, loop' :: *World -> ((),*World) loop w = loop w loop' w = let (_,w') = print "x" w in loop' w' both have denotation _|_ but are clearly different in terms of side effects. (The example is from SPJs awkward-squad tutorial.) Any pointers? Regards, apfelmus

On Nov 2, 2007, at 6:35 , apfelmus wrote:

during function evaluation. Then, we'd need a "purity lemma" that states that any function not involving the type *World as in- and output is indeed pure, which may be a bit tricky to prove in the presence of higher-order functions and polymorphism. I mean, the function arrows are "tagged" for side effects in a strange way, namely by looking like *World -> ... -> (*World, ...).

I don't quite see that; the Clean way looks rather suspiciously like my "unwrapped I/O in GHC" example from a couple weeks ago, so I have trouble seeing where any difficulty involving functions not using *World / RealWorld# creeps in. I will grant that hiding *World / RealWorld# inside IO is cleaner from a practical standpoint, though. Just not from a semantic one. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH

On Fri, 2007-11-02 at 08:35 -0400, Brandon S. Allbery KF8NH wrote:

On Nov 2, 2007, at 6:35 , apfelmus wrote:

...

during function evaluation. Then, we'd need a "purity lemma" that states that any function not involving the type *World as in- and output is indeed pure, which may be a bit tricky to prove in the presence of higher-order functions and polymorphism. I mean, the function arrows are "tagged" for side effects in a strange way, namely by looking like *World -> ... -> (*World, ...).

I don't quite see that; the Clean way looks rather suspiciously like my "unwrapped I/O in GHC" example from a couple weeks ago, so I have trouble seeing where any difficulty involving functions not using *World / RealWorld# creeps in.

I will grant that hiding *World / RealWorld# inside IO is cleaner from a practical standpoint, though. Just not from a semantic one.

On the contrary. GHC's IO newtype isn't an implementation of IO in Haskell at all. It's an implementation in a language that has a Haskell-compatible subset, but that also has semantically bad constructs like unsafePerformIO and unsafeInterleaveIO that give side effects to operations of pure, non-RealWorld#-involving types. Clean's type system is specified in a way that eliminates both functions from the language, which recovers purity. But proving that is harder than I'd like to attempt. jcc

On Fri, 2007-11-02 at 11:56 -0400, Brandon S. Allbery KF8NH wrote:

On Nov 2, 2007, at 11:51 , Jonathan Cast wrote:

...

...

I will grant that hiding *World / RealWorld# inside IO is cleaner from a practical standpoint, though. Just not from a semantic one.

On the contrary. GHC's IO newtype isn't an implementation of IO in Haskell at all. It's an implementation in a language that has a Haskell-compatible subset, but that also has semantically bad constructs

Differing viewpoints, I guess; from my angle, Clean's "uniqueness constraint" looks like a hack hidden in the compiler.

Yeah. After all, the "uniqueness constraint" has a theory with an excellent pedigree (IIUC linear logic, whose proof theory Clean uses here, goes back at least to the 60s, and Wadler proposed linear types for IO before anybody had heard of monads). It's not some random hack somebody happened to notice would work, any more than existential types are. jcc

On Fri, 2007-11-02 at 14:41 -0400, Jeff Polakow wrote:

Hello,

Just a bit of minor academic nitpicking...

...

Yeah. After all, the "uniqueness constraint" has a theory with an excellent pedigree (IIUC linear logic, whose proof theory Clean uses here, goes back at least to the 60s, and Wadler proposed linear types for IO before anybody had heard of monads).

Linear logic/typing does not quite capture uniqueness types since a term with a unique type can always be copied to become non-unique, but a linear type cannot become unrestricted.

Can I write a Clean program with a function that duplicates World?

As a historical note, the first paper on linear logic was published by Girard in 1987; but the purely linear core of linear logic has (non-commutative) antecedents in a system introduced by Lambek in a 1958 paper titled "The Mathematics of Sentence Structure".

OK then. Correction accepted. jcc

On Fri, 2007-11-02 at 15:43 -0400, Jeff Polakow wrote:

Hello,

...

...

Just a bit of minor academic nitpicking...

...

Yeah. After all, the "uniqueness constraint" has a theory with an excellent pedigree (IIUC linear logic, whose proof theory Clean uses here, goes back at least to the 60s, and Wadler proposed linear types for IO before anybody had heard of monads).

Linear logic/typing does not quite capture uniqueness types since a term with a unique type can always be copied to become non-unique, but a linear type cannot become unrestricted.

Can I write a Clean program with a function that duplicates World?

Clean won't let you duplicate the World. My comment on the mismatch with linear logic is aimed more at general uniqueness type systems (e.g. recent work by de Vries, Plasmeijer, and Abrahamson such as https://www.cs.tcd.ie/~devriese/pub/ifl06-paper.pdf). Sorry for the confusion.

Ah. I see. jcc