I offer up the following example:
mean xs = sum xs / length xs
Now try, say, "mean [1.. 1e9]", and watch GHC eat several GB of RAM. (!!)
But you know why, don't you?
sat down and spent the best part of a day writing an MD5 implementation. Eventually I got it so that all the test vectors work right. (Stupid little-endian nonsense... mutter mutter...) When I tried it on a file containing more than 1 MB of data... ooooohhhh dear...
Did you use Data.Binary or the other libraries for efficient access to gigabytes of data?
Of course, the first step in any serious attempt at performance improvement is to actually profile the code to figure out where the time is being spent.
Well, actually, for our 'mean()' case, it means just using the right structures. Arrays for example: import Data.Array.Vector import Text.Printf mean :: UArr Double -> Double mean arr = b / fromIntegral a where k (n :*: s) a = n+1 :*: s+a a :*: b = foldlU k (0 :*: 0) arr :: (Int :*: Double) main = printf "%f\n" . mean $ enumFromToFracU 1 1e9 For example, $ time ./A 5.00000000067109e8 ./A 3.53s user 0.00s system 99% cpu 3.532 total Try allocating an array of doubles in C, and getting similar results. (The compiler is optimising this to: Main_zdszdwfold_info: leaq 32(%r12), %rax cmpq %r15, %rax movq %rax, %r12 ja .L10 movsd .LC0(%rip), %xmm0 ucomisd %xmm5, %xmm0 jae .L12 movq %rsi, (%rax) movq $base_GHCziFloat_Dzh_con_info, -24(%rax) movsd %xmm6, -16(%rax) movq $base_GHCziBase_Izh_con_info, -8(%rax) leaq -7(%rax), %rbx leaq -23(%rax), %rsi jmp *(%rbp) .L12: movapd %xmm6, %xmm0 addq $1, %rsi subq $32, %r12 addsd %xmm5, %xmm0 addsd .LC2(%rip), %xmm5 movapd %xmm0, %xmm6 jmp Main_zdszdwfold_info Note even any garbage collection. This should be pretty much the same performance-wise as unoptimised C.
almost any nontrivial program you write spends 60% or more of its time doing GC rather than actual work.
Ok, you're doing something very wrong. GC time is typically less than 15% of the running time of typical work programs I hack on. I bet you're using lists inappropriately?
I find it completely impossibly to write code that doesn't crawl along at a snail's pace. Even when I manage to make it faster, I usually have no clue why.
I think there is a problem that few people are taking the time to understand the compilation model of Haskell, while they've had the C runtime behaviour drilled into their brains since college. Until you sit down and understand what your Haskell code means, it will be very hard to reason about optimisations, unfortunately. GHC does what it does well, and its predictable. As long as you understand the operations your trying to make predictions about. I suggest installing ghc-core, and looking at how your code is compiled. Try many examples, and have a good knowledge of the STG paper. -- Don
Don Stewart wrote:
Now try, say, "mean [1.. 1e9]", and watch GHC eat several GB of RAM. (!!)
But you know why, don't you?
What I'm trying to say [and saying very badly] is that Haskell is an almost terrifyingly subtle language. Seemingly insignificant chages can have drastic consequences. (Ever tried to run a program and find it goes into an infinite loop or a deadlock because you accidentally made some function slightly stricter than it needs to be?) I can't find it right now, but some paper I was reading showed two example programs, one of which is dramatically less performant than the other, and yet they look like they should be exactly equivilent, "and one might even expect a good compiler to 'optimise' one to the other [in the wrong direction]". After studying that chapter for about half an hour, I *still* can't wrap my brain around what the difference is. But I assume SPJ knows what he's talking about.
sat down and spent the best part of a day writing an MD5 implementation. Eventually I got it so that all the test vectors work right. (Stupid little-endian nonsense... mutter mutter...) When I tried it on a file containing more than 1 MB of data... ooooohhhh dear...
Did you use Data.Binary or the other libraries for efficient access to gigabytes of data?
Data.ByteString for all I/O. The rest is just moving data around one byte at a time. Difficult to see how you'd do it any different. [I'll check to see if I still have the code, maybe somebody can do something to it.] And we're not talking about "gigabytes" of data - we're talking about the program completely choking on a 5 MB file. Even plain String I/O couldn't possibly take *minutes* to read 5 MB!
Of course, the first step in any serious attempt at performance improvement is to actually profile the code to figure out where the time is being spent.
Well, actually, for our 'mean()' case, it means just using the right structures. Arrays for example:
Doesn't that mean all the data has to be present in memory at once? I would expect [optimistically?] that if you have a definition for "mean" that performs only 1 traversal of the list, you'd end up with something approximating x = 0 for n = 1 to 1e9 x = x + n return x If you allocate an array, you're limited to what will fit into RAM at once.
(The compiler is optimising this to:
Main_zdszdwfold_info: leaq 32(%r12), %rax cmpq %r15, %rax movq %rax, %r12 ja .L10 movsd .LC0(%rip), %xmm0 ucomisd %xmm5, %xmm0 jae .L12 movq %rsi, (%rax) movq $base_GHCziFloat_Dzh_con_info, -24(%rax) movsd %xmm6, -16(%rax) movq $base_GHCziBase_Izh_con_info, -8(%rax) leaq -7(%rax), %rbx leaq -23(%rax), %rsi jmp *(%rbp) .L12: movapd %xmm6, %xmm0 addq $1, %rsi subq $32, %r12 addsd %xmm5, %xmm0 addsd .LC2(%rip), %xmm5 movapd %xmm0, %xmm6 jmp Main_zdszdwfold_info
Note even any garbage collection. This should be pretty much the same performance-wise as unoptimised C.
Uh... I can't actually read x86 assembly, but I'll take your word. ;-) I guess it was kind of a bad example.
almost any nontrivial program you write spends 60% or more of its time doing GC rather than actual work.
Ok, you're doing something very wrong. GC time is typically less than 15% of the running time of typical work programs I hack on.
I bet you're using lists inappropriately?
No offense, but from what I can tell, you're a super-ultra-hyper expert in Haskell hacking. It's not surprising that *you* can write fast code. What I'm debating is how easy it is for relative beginners to write performant code. Certainly I'm not attempting to suggest that Haskell programs cannot be fast - this is manifestly false. What I'm contesting is how easy it is to make them fast. I guess because Haskell is such an implicit language, it's very easy to end up implicitly doing a hell of a lot of work without realising you're doing it. Certainly when I first started with Haskell, a lot of non-trivial programs I wrote were *horrifyingly* slow, or ate astonishing amounts of RAM. (My favourite one was that time I tried to use the "length" function to decide when to switch from quick-sort to insert sort. I'll leave you to guess what this did to the performance levels...) Today, my programs generally work better - but there's still a long, long way from being "fast".
I think there is a problem that few people are taking the time to understand the compilation model of Haskell, while they've had the C runtime behaviour drilled into their brains since college.
Until you sit down and understand what your Haskell code means, it will be very hard to reason about optimisations, unfortunately.
You're probably right about all that. I would humbly suggest that what is somewhat lacking is a good, introductory, high-level text on what makes Haskell go fast and what makes it go slow. As with many things in the Haskell world, there are bits and pieces of information out there, but it's difficult to track them all down and present a coherant picture. We've got a section on the wiki containing scraps and snippets of information. There are various GHC-related papers [if you can find them online]. GHC has various profiling possibilities, but thus far I've found it difficult to digest the results. We need a good, thorough body of text on this subject, I feel. [Of course, that still means somebody has to write one...] Maybe Real World Haskell will contain such a thing. Certainly making your code not crawl is a very significant real-world issue! ;-)
GHC does what it does well
Not contesting that. ;-)
and it's predictable. As long as you understand the operations you're trying to make predictions about.
That's the part I'm contesting. I feel I have a pretty solid basic understanding of what's going on, and yet benchmark results continue to astonish me...
I suggest installing ghc-core, and looking at how your code is compiled. Try many examples, and have a good knowledge of the STG paper.
1. What is "ghc-core"? 2. Does anybody know how to actually read GHC's Core output anyway? To me, it looks almost exactly like very, very complicated Haskell source with a suspicious concentration of case expressions - but I understand that in the Core language, many constructs actually mean something quite different. 3. Any idea where the STG paper is? Is it still an accurate reflection of GHC's current technology?
Andrew Coppin
You're probably right about all that. I would humbly suggest that what is somewhat lacking is a good, introductory, high-level text on what makes Haskell go fast and what makes it go slow. As with many things in the Haskell world, there are bits and pieces of information out there, but it's difficult to track them all down and present a coherant picture. We've got a section on the wiki containing scraps and snippets of information. There are various GHC-related papers [if you can find them online]. GHC has various profiling possibilities, but thus far I've found it difficult to digest the results. We need a good, thorough body of text on this subject, I feel. [Of course, that still means somebody has to write one...]
Something like the history paper but concentrating on algorithms, techniques & tricks would be great, yes. And, most importantly, less buzzwords where you're lucky if you find a definition of it by googling.
1. What is "ghc-core"?
An intermediate language, I'm quoting from memory: First comes a Syntax tree, then the type checker, then the translation to core, then optimisations on core (, then the printout) and finally c/assembly.
2. Does anybody know how to actually read GHC's Core output anyway? To me, it looks almost exactly like very, very complicated Haskell source with a suspicious concentration of case expressions - but I understand that in the Core language, many constructs actually mean something quite different.
I found it rather easy to parse... as long as you succeed in finding what you're looking for behind all that inlining. Types ending in # mean they're unboxed. It's particularly useful to find out how much ghc specialises your code.
3. Any idea where the STG paper is? Is it still an accurate reflection of GHC's current technology?
http://research.microsoft.com/~simonpj/Papers/papers.html Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine, SL Peyton Jones, Journal of Functional Programming 2(2), Apr 1992, pp127-202. while googling for it, I stumbled across http://citeseer.ist.psu.edu/reid98putting.html which might be more actual, but I neither read it yet or have any idea whatsoever. -- (c) this sig last receiving data processing entity. Inspect headers for past copyright information. All rights reserved. Unauthorised copying, hiring, renting, public performance and/or broadcasting of this signature prohibited.
Hi
1. What is "ghc-core"?
You actually answer this question as part of question 2. Think of it as simple Haskell with some additional bits.
2. Does anybody know how to actually read GHC's Core output anyway? To me, it looks almost exactly like very, very complicated Haskell source with a suspicious concentration of case expressions - but I understand that in the Core language, many constructs actually mean something quite different.
There is one different from standard Haskell I am aware of. In Core, case x of _ -> 1 will evaluate x, in Haskell it won't. Other than that, its just Haskell, but without pattern matching and only cases - hence the rather high number of cases. Thanks Neil
ndmitchell:
Hi
1. What is "ghc-core"?
You actually answer this question as part of question 2. Think of it as simple Haskell with some additional bits.
2. Does anybody know how to actually read GHC's Core output anyway? To me, it looks almost exactly like very, very complicated Haskell source with a suspicious concentration of case expressions - but I understand that in the Core language, many constructs actually mean something quite different.
There is one different from standard Haskell I am aware of. In Core, case x of _ -> 1 will evaluate x, in Haskell it won't. Other than that, its just Haskell, but without pattern matching and only cases - hence the rather high number of cases.
Well, 'let's too, which bind either unlifted or lifted values. If they're binding lifted things, that's a thunk being allocated. -- Don
Don Stewart wrote:
ndmitchell:
2. Does anybody know how to actually read GHC's Core output anyway?
There is one different from standard Haskell I am aware of. In Core, case x of _ -> 1 will evaluate x, in Haskell it won't. Other than that, its just Haskell, but without pattern matching and only cases - hence the rather high number of cases.
Well, 'let's too, which bind either unlifted or lifted values.
If they're binding lifted things, that's a thunk being allocated.
See, somebody needs to write all this down - in language comprehensible to people who don't already know what an "unlifed value" is. ;-)
Neil Mitchell wrote:
Hi
1. What is "ghc-core"?
You actually answer this question as part of question 2. Think of it as simple Haskell with some additional bits.
I rephrase: I know what GHC's Core language is. But Dons said "I suggest you install ghc-core", which suggests the existence of an item of software named "ghc-core". This I know nothing about...
On 2008 May 14, at 14:23, Andrew Coppin wrote:
Neil Mitchell wrote:
1. What is "ghc-core"?
You actually answer this question as part of question 2. Think of it as simple Haskell with some additional bits.
I rephrase: I know what GHC's Core language is. But Dons said "I suggest you install ghc-core", which suggests the existence of an item of software named "ghc-core". This I know nothing about...
Any time someone mentions something that sounds like a Haskell package, http://hackage.haskell.org is your friend. And there I find, in the Development category:
ghc-core program: Display GHC's core and assembly output in a pager
IIRC it's just a prettyprinter/colorizer to make it easier to follow and understand GHC Core. -- 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
Andrew Coppin wrote:
2. Does anybody know how to actually read GHC's Core output anyway? To me, it looks almost exactly like very, very complicated Haskell source with a suspicious concentration of case expressions - but I understand that in the Core language, many constructs actually mean something quite different.
I can read most of GHC Core. I was never taught, and I never asked. I did not read GHC's source code. I just guessed. I agree with your assessment about the domination by case expressions. They spell out the evaluation order. You need truckloads of them. I slightly agree with your assessment about "complicated", but I call it detailed and tedious. This is an assembly language for functional programming. If it weren't detailed and tedious, it would have no right to exist.
On 14 May 2008, at 8:58 am, Andrew Coppin wrote:
What I'm trying to say [and saying very badly] is that Haskell is an almost terrifyingly subtle language.
Name me a useful programming language that isn't. Simply interchanging two for-loops, from for (i = 0; i < N; i++) for (j = 0; j < N; j++) to for (j = 0; j < N; j++) for (i = 0; i < N; i++) when marching over an array, can easily slow you down by nearly two orders of magnitude in C. [Hint: read "What every computer scientist needs to know about memory".] For a real shock, take a look at what your C++ templates are doing... There's one big difference between Haskell and language T (my other preferred language). Seemingly insignificant changes in Haskell can kill performance, but seemingly insignificant changes in language T can take you into territory the library designers never thought of where there are lions, tigers, and bears in abundance. "Unexpectedly slow" is better than "inexplicably buggy".
Richard A. O'Keefe wrote:
On 14 May 2008, at 8:58 am, Andrew Coppin wrote:
What I'm trying to say [and saying very badly] is that Haskell is an almost terrifyingly subtle language.
Name me a useful programming language that isn't. Simply interchanging two for-loops, from for (i = 0; i < N; i++) for (j = 0; j < N; j++) to for (j = 0; j < N; j++) for (i = 0; i < N; i++) when marching over an array, can easily slow you down by nearly two orders of magnitude in C. [Hint: read "What every computer scientist needs to know about memory".]
OK, well *that* is news... :-o I would suggest that for heap-allocated data that isn't an array, both cases will be equally unperformant. I can't prove that though...
"Unexpectedly slow" is better than "inexplicably buggy".
+184 o_O
On Mon, 2008-05-12 at 19:30 -0700, Don Stewart wrote:
I offer up the following example:
mean xs = sum xs / length xs
Now try, say, "mean [1.. 1e9]", and watch GHC eat several GB of RAM. (!!)
But you know why, don't you?
sat down and spent the best part of a day writing an MD5 implementation. Eventually I got it so that all the test vectors work right. (Stupid little-endian nonsense... mutter mutter...) When I tried it on a file containing more than 1 MB of data... ooooohhhh dear...
Did you use Data.Binary or the other libraries for efficient access to gigabytes of data?
Of course, the first step in any serious attempt at performance improvement is to actually profile the code to figure out where the time is being spent.
Well, actually, for our 'mean()' case, it means just using the right structures. Arrays for example:
import Data.Array.Vector import Text.Printf
mean :: UArr Double -> Double mean arr = b / fromIntegral a where k (n :*: s) a = n+1 :*: s+a a :*: b = foldlU k (0 :*: 0) arr :: (Int :*: Double)
main = printf "%f\n" . mean $ enumFromToFracU 1 1e9
For example,
$ time ./A 5.00000000067109e8 ./A 3.53s user 0.00s system 99% cpu 3.532 total
Try allocating an array of doubles in C, and getting similar results. (The compiler is optimising this to:
Main_zdszdwfold_info: leaq 32(%r12), %rax cmpq %r15, %rax movq %rax, %r12 ja .L10 movsd .LC0(%rip), %xmm0 ucomisd %xmm5, %xmm0 jae .L12 movq %rsi, (%rax) movq $base_GHCziFloat_Dzh_con_info, -24(%rax) movsd %xmm6, -16(%rax) movq $base_GHCziBase_Izh_con_info, -8(%rax) leaq -7(%rax), %rbx leaq -23(%rax), %rsi jmp *(%rbp) .L12: movapd %xmm6, %xmm0 addq $1, %rsi subq $32, %r12 addsd %xmm5, %xmm0 addsd .LC2(%rip), %xmm5 movapd %xmm0, %xmm6 jmp Main_zdszdwfold_info
Note even any garbage collection. This should be pretty much the same performance-wise as unoptimised C.
almost any nontrivial program you write spends 60% or more of its time doing GC rather than actual work.
Ok, you're doing something very wrong. GC time is typically less than 15% of the running time of typical work programs I hack on.
I bet you're using lists inappropriately?
I find it completely impossibly to write code that doesn't crawl along at a snail's pace. Even when I manage to make it faster, I usually have no clue why.
I think there is a problem that few people are taking the time to understand the compilation model of Haskell, while they've had the C runtime behaviour drilled into their brains since college.
Until you sit down and understand what your Haskell code means, it will be very hard to reason about optimisations, unfortunately.
GHC does what it does well, and its predictable. As long as you understand the operations your trying to make predictions about.
I suggest installing ghc-core, and looking at how your code is compiled. Try many examples, and have a good knowledge of the STG paper.
My experience has been that simply understanding lazy/normal order evaluation is enough to catch most of the "big performance problems" beginners complain about. If you can't evaluate Haskell by hand at the source level, you have no hope of understanding performance issues. For going more for C-like speed, your advice seems more appropriate.
derek.a.elkins:
On Mon, 2008-05-12 at 19:30 -0700, Don Stewart wrote:
I offer up the following example:
mean xs = sum xs / length xs
Now try, say, "mean [1.. 1e9]", and watch GHC eat several GB of RAM. (!!)
But you know why, don't you?
sat down and spent the best part of a day writing an MD5 implementation. Eventually I got it so that all the test vectors work right. (Stupid little-endian nonsense... mutter mutter...) When I tried it on a file containing more than 1 MB of data... ooooohhhh dear...
Did you use Data.Binary or the other libraries for efficient access to gigabytes of data?
Of course, the first step in any serious attempt at performance improvement is to actually profile the code to figure out where the time is being spent.
Well, actually, for our 'mean()' case, it means just using the right structures. Arrays for example:
import Data.Array.Vector import Text.Printf
mean :: UArr Double -> Double mean arr = b / fromIntegral a where k (n :*: s) a = n+1 :*: s+a a :*: b = foldlU k (0 :*: 0) arr :: (Int :*: Double)
main = printf "%f\n" . mean $ enumFromToFracU 1 1e9
For example,
$ time ./A 5.00000000067109e8 ./A 3.53s user 0.00s system 99% cpu 3.532 total
Try allocating an array of doubles in C, and getting similar results. (The compiler is optimising this to:
Main_zdszdwfold_info: leaq 32(%r12), %rax cmpq %r15, %rax movq %rax, %r12 ja .L10 movsd .LC0(%rip), %xmm0 ucomisd %xmm5, %xmm0 jae .L12 movq %rsi, (%rax) movq $base_GHCziFloat_Dzh_con_info, -24(%rax) movsd %xmm6, -16(%rax) movq $base_GHCziBase_Izh_con_info, -8(%rax) leaq -7(%rax), %rbx leaq -23(%rax), %rsi jmp *(%rbp) .L12: movapd %xmm6, %xmm0 addq $1, %rsi subq $32, %r12 addsd %xmm5, %xmm0 addsd .LC2(%rip), %xmm5 movapd %xmm0, %xmm6 jmp Main_zdszdwfold_info
Note even any garbage collection. This should be pretty much the same performance-wise as unoptimised C.
almost any nontrivial program you write spends 60% or more of its time doing GC rather than actual work.
Ok, you're doing something very wrong. GC time is typically less than 15% of the running time of typical work programs I hack on.
I bet you're using lists inappropriately?
I find it completely impossibly to write code that doesn't crawl along at a snail's pace. Even when I manage to make it faster, I usually have no clue why.
I think there is a problem that few people are taking the time to understand the compilation model of Haskell, while they've had the C runtime behaviour drilled into their brains since college.
Until you sit down and understand what your Haskell code means, it will be very hard to reason about optimisations, unfortunately.
GHC does what it does well, and its predictable. As long as you understand the operations your trying to make predictions about.
I suggest installing ghc-core, and looking at how your code is compiled. Try many examples, and have a good knowledge of the STG paper.
My experience has been that simply understanding lazy/normal order evaluation is enough to catch most of the "big performance problems" beginners complain about. If you can't evaluate Haskell by hand at the source level, you have no hope of understanding performance issues.
For going more for C-like speed, your advice seems more appropriate.
Yes, I agree. You must first be able to reason about the evaluation strategy on paper. If you want to get C like speed, you should understand Core. Thankfully, the knowledge of how to do this, and tools to help, are improving. -- Don
participants (8)
-
Achim Schneider -
Albert Y. C. Lai -
Andrew Coppin -
Brandon S. Allbery KF8NH -
Derek Elkins -
Don Stewart -
Neil Mitchell -
Richard A. O'Keefe